Ìóðìàíñêèé ôèëèàë Ïåòðîâñêîãî Êîëëåäæà
Êóðñîâàÿ
ïî äèñöèïëèíå
«Êîìïüþòåðíîå ìîäåëèðîâàíèå»
íà òåìó
«Òðàíñïîðòíàÿ çàäà÷à»
Âûïîëíèë: Îøêèí Å.Ñ.
Ïðîâåðèë: Ñåðãååâ À.Â.
Ìóðìàíñê
2002ã.
Îïèñàíèå Àëãîðèòìà ïðîãðàììû
ÏÐÎÃÐÀÌÌÀ ÍÀÏÈÑÀÍÀ ÍÀ BORLAND Ñ++ âåðñèè 3.1
Ïðîãðàììà ðåøàåò Òðàíñïîðòíóþ Çàäà÷ó (ÒÇ) 3 ìåòîäàìè:
1. Ñåâåðî-çàïàäíûì óãëîì
2. Ñåâåðî-âîñòî÷íûì óãëîì
3. Ìåòîäîì ìèíèìàëüíîãî ýëåìåíòà â ñòðîêå.
Ïðîãðàììà ñîñòîèò èç ôóíêöèé:
1. Main()
2. Data()
3. Opplan()
4. Sohran()
5. Bas()
6. Kost()
7. Potenzial()
8. Optim()
9. Plmi()
10. Abcikl()
11. Cikl()
12. Prpoisk()
13. Levpoisk()
14. Verpoisk()
15. Nizpoisk()
16. Pr()
Ãëàâíàÿ ôóíêöèÿ main() íåâåëèêà, íî â íåé ïðîèñõîäèò îáðàùåíèå ôóíêöèÿì, âûïîëíÿþùèì îïðåäåëåííûå äåéñòâèÿ â ïðîöåññå ðåøåíèÿ ÒÇ. Çäåñü ñëåäóåò îáðàòèòü îñîáîå âíèìàíèå íà ñòðîêó ïðîãðàììû if(!z) break; - åñëè áû íå îíà (îíà ïîêàçûâàåò, ÷òî ïîñëå î÷åðåäíîé ïðîâåðêè áàçèñíîãî ïëàíà, åñëè îí îïòèìàëåí, âîçâðàùàåìîå çíà÷åíèå èç ôóíêöèè optim() ðàâíî 0, ÷òî ïðèâîäèò ê âûõîäó èç áåñêîíå÷íîãî öèêëà óëó÷øåíèÿ áàçèñíûõ ïëàíîâ). Èíîãäà âîçíèêàåò ñèòóàöèÿ, êîãäà áàçèñíàÿ ïåðåìåííàÿ(îäíà èëè íåñêîëüêî) ðàâíà íóëþ, è åå ñëåäóåò îòëè÷àòü îò äðóãèõ áàçèñíûõ ïåðåìåííûõ.  ìàòðèöå matr() òàêèå ýëåìåíòû ÿ ïîìåòèë êàê –2. Îñíîâíûå ïåðåìåííûå ÿ îïèñàë â êîììåíòàðèÿõ â ïðîãðàììå.
Ôóíêöèÿ data() ïðîèçâîäèò ââîä äàííûõ íà ÒÇ.
Ôóíêöèÿ opplan() âûïîëíÿåò çàäà÷è ïî ñîñòàâëåíèþ ïåðâîíà÷àëüíîãî áàçèñíîãî ïëàíà ìåòîäîì ñåâåðî-çàïîäíîãî óãëà.  ýòîé ôóíêöèè èñïîëüçóþòñÿ ñëåäóþùèå ïåðåìåííûå:
Int *matr óêàçàòåëü íà ìàòðèöó áàçèñíûõ ïåðåìåííûõ
Int *po óêàçàòåëü íà âåêòîð ïóíêòîâ îòïðàâëåíèÿ
Int *pn óêàçàòåëü íà âåêòîð ïóíêòîâ íàçíà÷åíèÿ
Int m êîëè÷åñòâî ïóíêòîâ îòïðàâëåíèÿ
Int n êîëè÷åñòâî ïóíêòîâ íàçíà÷åíèÿ
Ôóíêöèÿ kost() ïðîèçâîäèò âûâîä ñóììàðíîé ñòîèìîñòè ïåðåâîçîê ïî òåêóùåìó áàçèñíîìó ïëàíó. Èñïîëüçóþòñÿ ñëåäóþùèå ïåðåìåííûå:
Int *matr, m,n;
Int *st óêàçàòåëü íà ìàòðèöó ñòîèìîñòåé.
Ôóíêöèÿ potenzial() âûïîëíÿåò ïîäñ÷åò ïîòåíöèàëîâ.
Èñïîëüçóåò ñëåäóþùèå ïåðåìåííûå:
Int *pu óêàçàòåëü íà âåêòîð ïîòåíöèàëîâ ñòðîê
Int *pv óêàçàòåëü íà âåêòîð ïîòåíöèàëîâ ñòîëáöîâ
Int matr, m, n, *st;
Ïåðâîíà÷àëüíî ýëåìåíòû âåêòîðîâ ïîòåíöèàëîâ *(pu+i) è *(pv+j) çàïîëíÿþòñÿ ìèíèìàëüíûìè çíà÷åíèÿìè äëÿ öåëûõ ïåðåìåííûõ = 32768, îïðåäåëåííûõ ïðåäïðîöåññîðíûì îïåðàòîðîì define MIN – 32768. Äàëåå ïîëîãàÿ, ÷òî *pu=0, è èñïîëüçóÿ ñòðóêòóðó struct poten{…}, ýëåìåíòû âåêòîðîâ ïîòåíöèàëîâ ïðèîáðåòàþò ñâîè ðåàëüíûå çíà÷åíèÿ.
Ðàáîòó ýòîãî ìîäóëÿ ÿ áû ðàçäåëèë íà ýòè ýòàïû:
· Âûäåëåíèå ïàìÿòè ïîä ýëåìåíò ñòðóêòóðû top = (struct poten*)malloc(sizeof(struct poten)); çàïîëíåíèå ïîëåé ýëåìåíòà ñòðóêòóðû íåîáõîäèìîé èíôîðìàöèåé; óñòàíîâëåíèå ñâÿçåé ìåæäó ýëåìåíòàìè ñòðóêòóðû;
· Âû÷èñëåíèå ïîòåíöèàëîâ ñòðîê è ñòîëáöîâ ñ çàíåñåíèåì èíôîðìàöèè â ñåêòîðû pu è pv;
· Ïðîâåðêà ïðàâèëüíîñòè çàïîëíåíèÿ âåêòîðîâ pu è pv, ò.å. óñòàíîâëåíèå íå ñîäåðæàò ëè ýëåìåíòû ýòèõ âåêòîðîâ çíà÷åíèÿ MIN. Ïðè íåîáõîäèìîñòè, åñëè ñóùåñòâóþò òàêèå ýëåìåíòû âåêòîðîâ, ïðîèçâîäÿòñÿ äîïîëíèòåëüíûå âû÷èñëåíèÿ;
· Âûâîä âåêòîðîâ pu è pv;
Ôóíêöèÿ optim() ïðîâåðÿåò ïëàí íà îïòèìàëüíîñòü, åñëè îí îïòèìàëåí, òî ôóíêöèÿ îòïðàâëÿåò â ãëàâíóþ ôóíêöèþ main() çíà÷åíèå 0, â ïðîòèâíîì ñëó÷àå, åñëè îí íå îïòèìàëåí, òî óïðàâëåíèå ïåðåäàåòñÿ ôóíêöèè abcikl() è âîçâðàò ãëàâíîé ôóíêöèè main() çíà÷åíèå –1. Ôóíêöèÿ optim() èñïîëüçóåò ïåðåìåííûå:
Int m,n,*pu,*pv, *matr, *st. Öåïü ñòðîèòñÿ îòíîñèòåëüíî ïåðâîé ïîïàâøåéñÿ ãðàôîêëåòêè, äëÿ êîòîðîé ui + vj =cij , à íå îòíîñèòåëüíîé õàðàêòåðèñòèêè.  õîäå ðåøåíèÿ ÒÇ ïðîìåæóòî÷íûå áàçèñíûå ïëàíû îòëè÷àþòñÿ îò òåõ, êîòîðûå ÿ ïîñòðîèë, íà÷èíàÿ ñ êîîðäèíàò ãðàôîêëåòêè ñ ìèíèìàëüíûì çíà÷åíèåì îòðèöàòåëüíîé õàðàêòåðèñòèêè, íî âðåçóëüòàòå îïòèìàëüíûé ïëàí áóäåò òîò æå.
Ôóíêöèÿ abcicl() – èñïîëüçóåò ñëåäóþùèå ïåðåìåííûå
Int *matr, m, n;
Int *matr2 //óêàçàòåëü íà ðàáî÷óþ (èçìåíÿåìóþ) ìàòðèöó, ïî íà÷àëó îíà ÿâëÿåòñÿ êîïèåé îðèãèíàëüíîé.
Int ik,jk; // êîîðäèíàòû ãðàôîêëåòêè, ñ êîòîðîé íà÷èíàåò ñòðîèòüñÿ öåïü.  ýòîé ôóíêöèè ïðèñâàèâàåòñÿ ãðàôîêëåòêè, ñ êîòîðîé áóäåò ïðîèñõîäèòü ïîèñê öèêëà(öåïü), çíà÷åíèå -1.
Ôóíêöèÿ cikl() ïðîèçâîäèò ïîèñê îòíîñèòåëüíî ãðàôîêëåòêè ñî çíà÷åíèåì –1. Îíà èñïîëüçóåò ñëåäóþùèå ïåðåìåííûå:
Int *matr2, ik, jk;
Int ch; // ñ÷åò÷èê êîëè÷åñòâà ýëåìåíòîâ â ìàññèâàõ *zi è *zj
Int *zi, *zj // óêàçàòåëè íà ìàññèâû èíäåêñîâ. Õðàíÿò èíäåêñû ýëåìåíòîâ matr, ïîäëåæàùèõ ïåðåðàñïðåäåëåíèþ.
Ôóíêöèè prpoisk(), levpoisk(), verpoisk(), nizpoisk()-ïîèñê, ñîîòâåòñòâåííî, âïðàâî, âëåâî, ââåðõ, âíèç – îòíîñèòåëüíî òåêóùåé ãðàôîêëåòêè. Ïîèñê ïðîèñõîäèò â ìàññèâå *matr2. Åñëè èçâåñòíà ñòðîêà, òî âûïîëíÿåòñÿ ïîèñê ñòîëáöà, ò.å. åãî èíäåêñà, åñëè èçâåñòåí ñòîëáåö –èùåòñÿ ñòðîêà.
Äàííûå ôóíêöèè âîçâðàùàþò êîîðäèíàòû ñòîëáöà èëè ñòðîêè íàéäåííîé ãðàôîêëåòêè, ëèáî çíà÷åíèå –1, åñëè ãðàôîêëåòêà â äàííîì íàïðàâëåíèè íå íàéäåííà.
Ðàáîòà ìîäóëÿ cikl() çàêëþ÷àåòñÿ â ñëåäóþùåì:
· Ïîèñê íóæíîãî ýëåìåíòà íà÷èíàåòñÿ îòíîñèòåëüíî ãðàôîêëåòêè, ïîìå÷åííîé –1 â ìàòðèöå matr2 (ñ êîîðäèíàòàìè ik è jk ñîãëàñíî âõîäíûì äàííûì) ïî âîçìîæíûì íàïðàâëåíèÿì (ïîî÷åðåäíî);
· Åñëè ïîèñê óñïåøåí, òî ïîëÿ ñòðóêòóðû çàïîëíÿþòñÿ èíôîðìàöèåé, íàéäåííûé ýëåìåíò ñòðóêòóðû âêëþ÷àåòñÿ â ñïèñîê(ðàáîòó ìîäóëÿ ïîääåðæèâàåò ëèíåéíûé ñïèñîê, â êîòîðîì õðàíèòñÿ èíôîðìàöèÿ î õîäå ïîèñêà öåïè), è çà îñíîâó áåðåòñÿ óæå ýòà (òåêóùàÿ) ãðàôîêëåòêà ìàòðèöû matr2(). Äàëåå ïðîöåäóðà ïîèñêà ïîâòîðÿåòñÿ:
· Åñëè ïîèñê íà êàêîì-òî øàãà íå íåóñïåøåí ïî âîçìîæíûì íàïðàâëåíèÿì, òî íàéäåííûé ýëåìåíò èñêëþ÷àåòñÿ èç ñïèñêà è çà îñíîâó áåðåòñÿ ïîñëåäíèé ýëåìåíò ñïèñêà (ïîñëå óäàëåíèÿ).  ðàáî÷åé ìàòðèöå matr2() «îáíóëÿåòñÿ» ýëåìåíò ñ êîîðäèíàòàìè, êîòîðûé õðàíèë èñêëþ÷åííûé ýëåìåíò, ÷òî íåîáõîäèìî äëÿ òîãî, ÷òîáû èñêëþ÷èòü ïîâòîðíîå îáðàùåíèå ê ýëåìåíòó matr2, íå âõîäÿùåììó â öåïü;
· Ïîèñê öèêëà (öåïè) áóäåò çàêîí÷åí, êîãäà ïðè ïðîõîæäåíèè ïî êàêîìó-ëèáî íàïðàâëåíèþ ìû ñíîâà íàòêíåìñÿ íà ýëåìåíò ìàòðèöû matr2 ñî çíà÷åíèåì –1.  êîíöå ìîäóëÿ ýëåìåíòû ñïèñêà, ò.å. åãî ïîëÿ ñ êîîðäèíàòàìè, ïåðåïèñûâàþòñÿ â âåêòîðû zi è zj.
Âíåøíèå ïåðåìåííûå:
Int m, n, *matr2;
Âõîäíûå äàííûå:
Int i1, j1 // êîîðäèíàòû òåêóùåé ãðàôîêëåòêè, îòíîñèòåëüíî êîòîðîé ñòðîèòñÿ öåïü.
Âûõîäíûå äàííûå:
I(j)- êîîðäèíàòû ñòðîêè, ñòîëáöà, åñëè ïåðåìåííàÿ íàéäåíà;
Ôóíêöèÿ pr(), îñóùåñòâëÿåò ïå÷àòü òåêñòîâûõ ñîîáùåíèé î õîäå ïîèñêà â ìàòðèöå; îíà âûçûâàåòñÿ èç ìîäóëÿ cikl().
Ôóíêöèÿ plmi() ïåðåðàñïðåäåëÿåò ïîñòàâêè ïî öåïè, ò.å. óëó÷øàåò ïëàí.
Èñïîëüçóþòñÿ ñëåäóþùèå ïåðåìåííûå:
Int zi,zj;
Int ch,chr; /ïåðåìåííûå ðàçìåðíîñòè ìàññèâîâ zi,zj
Int matr /óêàçàòåëü íà ìàòðèöó áàçèñíûõ ïåðåìåííûõ
Ðàáîòà ñ ìîäóëÿìè âûïîëíÿåòñÿ â íåñêîëüêî ýòàïîâ. Åñëè èìååòñÿ íóëåâîé áàçèñíûé ýëåìåíò (ïîìå÷åííûé êàê –2 â ìàòðèöå matr) è èíäåêñ k íå÷åòåí äëÿ âåêòîðîâ zi,zj, òî ýëåìåíòû matr, ïîìå÷åííûå, êàê –1 è –2(íîâûé ýëåìåíò ïîìå÷åííûé êàê –2 îáíóëÿåì), ìåíÿþòñÿ ìåñòàìè, â ïðîòèâíîì ñëó÷àå(åñëè k ÷åòíî èëè íåò íóëåâûõ áàçèñíûõ ýëåìåíòîâ â matr) îñóùåñòâëÿåòñÿ:
Íàõîæäåíèå ìèíèìàëüíîãî ýëåìåíòà â ìàòðèöå áàçèñíûõ ïåðåìåííûõ: min=matr [i][j], ãäå i=zi[k]; j=zj[k]; k-íå÷åòíîå ÷èñëî;
Ïåðåðàñïðåäåëåíèå ïîñòàâîê:
a) åñëè k ÷åòíîå ÷èñëî, òî matr[i][j] = matr[i][j]+min, ãäå i=zi[k]; j=zj[k];
b)åñëè k íå÷åòíîå ÷èñëî, òî matr[i][j] = matr[i][j]-min, ãäå i=zi[k]; j=zj[k];
Ìîäóëü bas() ïîäñ÷èòûâàåò êîëè÷åñòâî íåíóëåâûõ áàçèñíûõ ïåðåìåííûõ â ìàòðèöå matr.
Ìîäóëü sohran() íàõîäèò íóëåâóþ áàçèñíóþ ïåðåìåííóþ â matr è óñòàíàâëèâàåò å¸ â –2.
Int basper; /êîëè÷åñòâî áàçèñíûõ ïåðåìåííûõ.
Ôóíêöèÿ opplan1() ïîñòðîåíèå ïåðâîíà÷àëüíîãî ïëàíà ìåòîäîì ñåâåðî-âîñòî÷íîãî óãëà, à opplan2()- ìåòîäîì âûáîðà íàèìåíüøåãî ýëåìåíòà â ñòðîêå.
Íèæå ïðèâåäåí òåêñò ïðîãðàììû
#include <stdio.h> //Ïîäêëþ÷åíèå ñòàíäàðòíûõ
#include <alloc.h> // Áèáëèîòåê
#include <conio.h>
#include <process.h>
#include <stdlib.h>
#define MIN -32768
int *po = NULL; //Óêàçàòåëü íà ìàññèâ ïóíêòîâ îòïðàâëåíèÿ
int *pn = NULL; //Óêàçàòåëü íà ìàññèâ ïóíêòîâ íàçíà÷åíèÿ
int *st = NULL; //Óêàçàòåëü íà ìàòðèöó ñòîèìîñòåé
int *matr=NULL; //Óêàçàòåëü íà ìàòðèöó áàçèñíûõ ïåðåìåííûõ
int *matr2 = NULL; //Óêàçàòåëü íà ðàáî÷óþ ìàòðèöó
int n ,m; //Ðàçìåðíîñòü çàäà÷è
int *pu,*pv; //Óêàçàòåëè íà ìàññèâû ïîòåíöèàëîâ
int *zj,*zi; // Óêàçàòåëü íà ìàññèâû èíäåêñîâ
int ch=0,ch2=0; //Ñ÷åò÷èêè
FILE *fpdat; //Óêàçàòåëü íà ââîäíîé ôàéë
int iter=0; //Ñ÷åò÷èê èòåðàöèè
FILE *fil; //Óêàçàòåëü íà âûâîäíîé ôàéë
int zen = -1; //Ïåðåìåííàÿ äëÿ ñîõðàíåíèÿ ñòîèìîñòè ï-íà
int z = 1; //Ôëàã äëÿ âûõîäà ïðè îïòèìàëüíîì ïëàíå
int basper;
// void exit(int status);
void data(void)
{
int i,j,t;
printf("Ââåäèòå êîëè÷åñòâî ñêëàäîâ: ");
scanf("%d",&m);
printf("Kolichestvo skladov-----> %d",m);
printf("\n Ââåäèòå êîëè÷åñòâî ìàãàçèíîâ:\n");
scanf("%d",&n);
printf("\n Kolichestvo magazinov --->%d",n);
//*********** Âûäåëåíèå ïàìÿòè ******************
if((po=(int*)calloc(m,sizeof(int)))==NULL) abort();
if((pn=(int*)calloc(n,sizeof(int)))==NULL) abort();
if((st=(int*)calloc(n*m,sizeof(int)))==NULL) abort();
printf("Ââåäèòå ýëåìåíòû ìàòðèöû ñòîèìîñòåé: \n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("Ââåäèòå [%d][%d]\n ",i,j);
scanf("%d",&t);
*(st+i*n+j)=t;
}
}
printf("\n");
fprintf(fil,"\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",*(st+i*n+j));
fprintf(fil,"%5d",*(st+i*n+j));
}
printf("\n");
fprintf(fil,"\n");
}
printf("Ââåäèòå êîëè÷åñòâî çàïàñîâ íà êàæäîì ñêëàäå:\n");
for(i=0;i<m;i++)
{
printf("\n");
scanf("%d",po+i);
printf("%5d",*(po+i));
}
printf("\n");
printf("Ââåäèòå ïîòðåáíîñòè:\n");
for(j=0;j<n;j++)
{
printf("\n");
scanf("%d",pn+j);
printf("%5d",*(pn+j));
}
return;
}//**** data
//************* SOZDANIE OPORNOGO PLANA ********************
//************* METHOD NORD-WEST YGLA **********************
void opplan(void)
{
int i,j,ch1 = 0;
//*************** ÂÛÄÅËÅÍÈÅ ÏÀÌßÒÈ *************************
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
// ÖÈÊË ÏÐÎÑÒÎÃÎ ÐÀÑÏÐÅÄÅËÅÍÈß ÏÎÒÐÅÁÍÎÑÒÅÉ ïî ÿ÷åéêàì ðàáî÷åé ìàòðèöû
for(i=0;i<m;i++)
{
for(j=ch1;j<n;j++)
{
if(*(po+i)<*(pn+j))
{
*(matr+i*n+j)=*(po+i);
*(pn+j)-=*(po+i);
*(po+i)=0;
break;
}
*(matr+i*n+j)=*(pn+j);
*(po+i) -= *(pn+j);
*(pn+j)=0;
ch1++;
}
}
//********* ÏÐÎÂÅÐÊÀ È ÂÛâîä ïîëó÷èâøåéñÿ ìàòðèöû ***********************
printf("PROVERKA\n");
fprintf(fil,"PROVERKA MATRIX - Ñåâåðî çàïîäíûé ÓÃÎË,\n ïðîñìîòð ïîëó÷èâøåãîñÿ ðàñïðåäåëåíèÿ â ìàòðèöå \n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",*(matr+i*n+j));
fprintf(fil,"%d",*(matr+i*n+j));
}
printf("\n");
fprintf(fil,"\n");
}
fprintf(fil,"********************\n");
return;
} // opplan
void kost(void)
{
int i,j, *matr1,rez=0;
//âûäåëåíèå ïàìÿòè
if((matr1=(int*)calloc(n*m,sizeof(int))) == NULL) abort();
//ïðèñâîåíèå íîâîé ìàòðèöå çíà÷åíèÿ áàçèñíîé(ñòàðîé) ìàòðèöû
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
*(matr1+i*n+j) = *(matr+i*n+j);
}
}
// Ïîäñ÷åò ñòîèìîñòè áàçèñíîé ìàòðèöû (ñîçäàííîãî ìàññèâà)
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr1+i*n+j)>0)
rez += (*(matr1+i*n+j)) *(*(st+i*n+j));
}
}
printf("\n Rezultat : %d",rez);
printf("\n");
fprintf(fil,"%s %5d"," Rezultat : ",rez);
fprintf(fil,"\n");
getch();
free(matr1);
if(zen == rez)
{
z=0;
}
zen = rez;
return;
}
//************* KOST()
//************* PODSCHET POTENCIALOV ********************
void potenzial(void)
{
struct poten
{
int v;
int u;
int zn;
struct poten *next;
int b;
} *topnast = NULL,
*top = NULL,
*top1 = NULL;
int i,j;
int fl;
//********** ÂÛÄÅËÅÍÈÅ ÏÀÌßÒÈ *******************8
if((pu=(int*)calloc(m,sizeof(int)))==NULL) abort();
if((pv=(int*)calloc(n,sizeof(int)))==NULL) abort();
// ÏÐÈÑÂÎÅÍÈÅ ÂÑÅÌ ÏÎÒÅÍÖÈÀËÀÌ ÇÍÀ×ÅÍÈß MIN
for(i=0;i<m;i++)
*(pu+i) = MIN;
for(j=0;j<n;j++)
*(pv+j) = MIN;
// Âûäåëåíèå ïàìÿòè ïîä ñòðóêòóðó è çàïîëíåíèå å¸ çíà÷åíèÿìè
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if((*(matr+i*n+j) > 0) || (*(matr+i*n+j)==-2))
{
if((top=(struct poten*)malloc(sizeof(struct poten)))==NULL)
abort();
fprintf(fil,"top = %d",top);
if(!topnast){
topnast = top;
fprintf(fil,"topnast = top = %d",top);
}
else top1 -> next=top;
top1=top;
top -> next=NULL;
top -> b = *(st+i*n+j); //Ñòîèìîñòè
top -> v = j;
top -> u = i;
top -> zn = -1;
}
}
}
*pu = 0;
i=0; j = -1;
for(top = topnast;top!=NULL;top = top -> next)
{
if((top -> u) == i && (top -> v)!=j)
{
*(pv+(top -> v)) = (top -> b) - *(pu+i);
j = (top->v);
top -> zn = 0;
}
else{
for(top1 = topnast;top1 != NULL;top1 = top1->next)
{
if((top1->v) == j && (top1->u)!=i)
{
*(pu+(top1->u))=(top1->b) - *(pv+j);
i = (top1->u);
top1 ->zn = 0;
break;
}
}
}
}
// ********** Ïðîäîëæåíèå ôóíêöèè ïîäñ÷åòà ïîòåíöèàëîâ *****************
for(;;){
fl = 0;
for(top = topnast;top!=NULL;top =top -> next)
{
if((top -> zn) == -1)
{
if(*(pu+(top ->u)) !=MIN)
{
*(pv+(top->v))=(top->b) - *(pu+(top ->u));
fl = 1;
top -> zn = 0;
}
if(*(pv+(top->v)) !=MIN)
{
*(pu+(top->u))=(top->b) - *(pv+(top->v));
fl=1;
top->zn = 0;
}
}
}
if(!fl) break;
}
printf("\n ÏÎÒÅÍÖÈÀËÛ ÏÎ v:");
fprintf(fil,"\n **** ÏÎÒÅÍÖÈÀËÛ ÏÎ v:");
for(i = 0;i<n;i++)
{
printf("%d",*(pv+i));
fprintf(fil,"%5d",*(pv+i));
}
getch();
printf("\n ÏÎÒÅÍÖÈÀËÛ ÏÎ u: ");
fprintf(fil,"\n **** ÏÎÒÅÍÖÈÀËÛ ÏÎ u: ");
for(i=0;i<m;i++)
{
printf("%d",*(pu+i));
fprintf(fil,"%5d",*(pu+i));
}
fprintf(fil,"\n");
for(top = topnast;top!=NULL;top = top->next)
free(top);
return;
} // potenzial
// ****** PROVERKA PLANA NA OPTIMALNOST' ************************
void abcikl(int ik,int jk);
int cikl(int ik,int jk);
void pr(char pr[],void *st); // Ïðåäâàðèòåëüíî
int prpoisk(int i1,int j1); // Îáúÿâëåíû
int levpoisk(int i1,int j1); //ÝÒÈ
int verpoisk(int i1,int j1); //Ôóíêöèè
int nizpoisk(int i1,int j1);
int optim(void)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
// ÈÙÅÌ ÎÏÒÈÌÀËÜÍÎÅ ÐÅØÅÍÈÅ Â ÍÀØÅÉ ÌÀÒÐÈÖÅ È ÅÑËÈ ÅÃÎ ÍÅ ÍÀÉÄÅÌ
// ÒÎ ÏÎ ÑËÅÄÓÞÙÅÌÓ ÓÑËÎÂÈÞ ÏÐÈÑÂÎÈÌ ÃÐÀÔÎÊËÅÒÊÅ Ñ ÊÎÎÐÄÈÍÀÒÀÌÈ
// ik,jk ÇÍÀ×ÅÍÈÅ -1
if(( *(pu+i)+ *(pv+j))>(*(st+i*n+j))&&((*(matr+i*n+j)) == 0))
{
abcikl(i,j);
fprintf(fil,"optim(): Ïëàí íå îïòèìàëåí, ôóíêöèè main() âîçâðàùàåì -1,\n à abcikl() ïàðàìåòðû i,j ");
return(-1);
}
}
}
fprintf(fil,"Plan optimalen");
return(0);
} // ******* optim() ***************
// ************** UPGRADE PLAN **************************
void abcikl(int ik,int jk)
{
int i,j;
fprintf(fil,"Ìû â abcikl()");
if((matr2=(int*)calloc(n*m,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
*(matr2+i*n+j) = *(matr+i*n+j); // Ñîçäàåì êîïèþ ðàáî÷åé ìàòðèöû
}
}
*(matr2+ik*n+jk) = -1;
// çíà÷åíèþ ìàòðèöû ñ ïàðàìåòðàìè ik,jk ïðèñâàåâàåì -1
printf("\n");
printf("Ïîèñê Öåïè: \n\n");
fprintf(fil,"Ïîèñê Öåïè: \n\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr2+i*n+j));
printf("%5d",*(matr2+i*n+j));
}
fprintf(fil,"\n");
printf("\n");
}
fprintf(fil,"\n\n Ïåðåõîäèì â Ñðàíóþ, Ìàòü å¸, Ôóíêöèþ cikl(ik,jk) \n");
getch();
cikl(ik,jk);
return;
} // abcikl
// ********* FUNKCION POISKA CIKLA **************************
int cikl(int ik,int jk)
{
int nst,nstr,i,j,
perlev = 0,
perpr = 0;
int perver = 0,
perniz = 0,
fl = 0,
fl3 = 1;
int napr;
struct cik { int prnapr;
int ick;
int jck;
struct cik *next;
} *topnast1 = NULL,
*top2 = NULL,
*top3 = NULL;
ch = 0;
if((top2 = (struct cik*)malloc(sizeof(struct cik))) == NULL)
abort();
if(!topnast1)
{
topnast1=top2;
top3=top2;
top3->ick=ik;
top3->jck=jk;
}
else
top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
fprintf(fil,"\n\nÄî Óñëîâèÿ while fl3 =%d \n",fl3);
pr("top2",top2);
fprintf(fil,"Âåñü öèêë ïîèñêà ñåé÷àñ íà÷íåòñÿ, íàäåþñü - \n ÷òî îí áóäåò íå áåñêîíå÷íûé èëè íå áåñïîëåçíûé :( \n");
printf("Âåñü öèêë ïîèñêà ñåé÷àñ íà÷íåòñÿ, íàäåþñü - \n ÷òî îí áóäåò íå áåñêîíå÷íûé èëè íå áåñïîëåçíûé :( \n");
printf("\n \t \t\tpress anykey to contunio\n");
getch();
while(fl3)
{
fl3=0;
fl = 0;
if((nst = prpoisk(ik,jk))>=0)
{
fprintf(fil,"\n\nÂíèìàíèå!!!\n nst = %d \n",nst);
fprintf(fil,"Ùà áóäåò ïîèê èäòè åìó áû...:Point found!\n");
printf("È îí ïîøåë RIGHT:Point found !\n\r");
napr = 2;
jk = nst;
top2->prnapr = 1;
}
else if((nstr = nizpoisk(ik,jk))>=0)
{
fprintf(fil,"DOWN: Point found !\n");
printf("DOWN: Point found !\n\r");
napr = 3;
ik = nstr;
top2->prnapr = 2;
}
else if((nst=levpoisk(ik,jk))>=0)
{
fprintf(fil,"LEFT:Point found !\n");
printf("LEFT:Point found !\n\r");
napr = 4;
jk = nst;
top2->prnapr = 3;
}
// **************** Prodolzhenie 1 poiska ***********************
else if((nstr = verpoisk(ik,jk))>=0)
{
fprintf(fil,"UP:Point found !\n");
printf("UP:Point found !\n\r");
napr = 1;
ik = nstr;
top2->prnapr = 4;
}
else
return(-1);
while(!fl || *(matr2+ik*n+jk)!=-1)
{
fl=1;
switch(napr)
{
case 1:
printf("Search to the right --->");
fprintf(fil,"Search to the right --->");
if((nst = prpoisk(ik,jk))>=0)
{
printf("founded\n\r");
fprintf(fil,"founded\n");
if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)
abort();
if(!topnast1) topnast1=top2;
else top3 -> next=top2;
top3 = top2;
top2 -> next = NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
top2->prnapr = 1;
pr("top2",top2);
napr = 2;
jk = nst;
perpr = perlev = 0;
} // **** IF *******
else
{
fprintf(fil,"Point not found ! Change direction to LEFT\n");
napr = 3;
perpr = 1;
}
break;
//***************** PRODOLZHENIE 2 POISKA ******************************
case 2:
printf("Search to the down --->");
fprintf(fil,"Search to the down --->");
if((nstr=nizpoisk(ik,jk))>=0)
{
if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL)
abort();
printf("founded\n\r"); fprintf(fil,"founded\n");
if(!topnast1) topnast1=top2;
else top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
top2->prnapr = 2;
pr("top2",top2);
napr = 3;
ik = nstr;
perniz=perver=0;
} //**** IF ********
else
{
fprintf(fil,"Point not found ! Change direction to UP\n");
napr = 4;
perniz = 1;
}
break;
case 3:
printf("Search to the left -->");
fprintf(fil,"Search to the left -->");
if((nst=levpoisk(ik,jk))>=0)
{
if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL)
abort();
printf("founded\n\r"); fprintf(fil,"founded\n");
if(!topnast1)
topnast1=top2;
else
top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
//************ PRODOLZHENIE 3 POISKA *************
top2->prnapr = 3;
pr("top2",top2);
napr = 4; jk = nst;
perlev = perpr = 0;
} // ******* IF *****
else{
fprintf(fil,"Point not found ! Change direction to RIGHT\n");
napr = 1;
perlev = 1;
}
break;
case 4:
printf("Search to the up --->");
fprintf(fil,"Search to the up --->");
if((nstr=verpoisk(ik,jk))>=0)
{
if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)
abort();
printf("founded\n\r"); fprintf(fil,"founded\n");
if(!topnast1) topnast1=top2;
else top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick=ik;
top2->jck=jk;
ch++;
top2->prnapr = 4;
pr("top2",top2);
napr = 1;
ik = nstr;
perver = perniz = 0;
} // *****If **************
else
{
fprintf(fil,"Point not found ! Change direction to DOWN\n");
napr = 2;
perver = 1;
}
break;
} // ************ SWITCH ********************
// ************** PRODOLZHENIE 4 POISKA ********************
if(perlev == 1 && perpr == 1)
{
*(matr2+ik*n+jk) = 0;
ik = top3 ->ick;
jk = top3 ->jck;
napr = top3->prnapr;
top3 = topnast1;
printf("Zerro 1\n\r");
for(top2=topnast1;top2->next !=NULL;top2=top2->next)
top3 = top2;
top3 -> next=NULL;
perlev = perpr = 0; // if(ch == 1)
if(top2==top3)
{
fl3=1;
break;
}
else
{
top3->next=NULL;
free(top2);
ch--;
printf("Viynimaem tochky: (%d,%d)=%d\n",ik,jk,*(matr2+ik*n+jk));
fprintf(fil,"Viynimaem tochky: (%d,%d)=%d\n",ik,jk,*(matr2+ik*n+jk));
pr("top2",top2);
}
perpr = 0;
perlev = 0;
} // IF
if(perver == 1 && perniz == 1)
{
*(matr2+ik*n+jk)=0;
printf("Zerro 2\n\r");
ik=top3->ick;
jk = top3->jck;
napr = top3->prnapr;
top3 = topnast1;
for(top2 = topnast1;top2->next !=NULL;top2=top2->next)
top3 = top2; perver = perniz = 0;
if(top2==top3)
{
fl3=1;
break;
}
else
{
top3->next = NULL;
free(top2);
ch--;
// ******* PRODOLZHENIE 5 POISKA *********************
printf("Viynimaem tochky: (%d,%d) = %d\n",ik,jk,*(matr2+ik*n+jk));
fprintf(fil,"Viynimaem tochky: (%d,%d) = %d\n",ik,jk,*(matr2+ik*n+jk));
pr("top2",top2);
}
perver = 0;
perniz = 0;
} // IF
if(ch==0)
{
fl3=1;
break;
}
} //while
} //while
i=0;
if((zi = (int*)calloc(ch,sizeof(int))) == NULL ) abort();
if((zj = (int*)calloc(ch,sizeof(int))) == NULL ) abort();
printf("\n\r");
ch2 = ch;
for(top2 = topnast1;top2 !=NULL;top2 = top2->next)
{
*(zi+i) = top2 ->ick;
*(zj+i) = top2 ->jck;
i++;
}
return(0);
} // *********** cikl ****************************
int prpoisk(int i1, int j1)
{
int j;
for(j=j1+1;j<n;j++)
{
if((*(matr2+i1*n+j))!=0)
return(j);
}
return(-1);
}
int levpoisk(int i1,int j1)
{
int j;
for(j = j1-1;j>=0;j--)
{
if((*(matr2+i1*n+j))!=0)
return(j);
}
return(-1);
}
int verpoisk(int i1,int j1)
{
int i;
for(i=i1-1;i>=0;i--)
{
if((*(matr2+i*n+j1))!=0)
return(i);
}
return(-1);
}
int nizpoisk(int i1, int j1)
{
int i;
for(i = i1+1;i<m;i++)
{
if((*(matr2+i*n+j1))!=0)
return(i);
}
return(-1);
}
// ************* FUNCTION SEARCH ********************
void pr(char pr[],void *st)
{
struct cik { int prnapr;
int ick;
int jck;
struct cik *next;
} *ptr;
int i,j;
ptr = (struct cik *)st;
fprintf(fil,"Koordinatiy ytoplennoy tochki : %d and %d",ptr->ick,ptr->jck);
printf("Koordinatiy ytoplennoy tochki : %d and %d\n\r",ptr->ick,ptr->jck);
fprintf(fil,"and napravlenie");
printf("Napravlenie");
switch(ptr->prnapr)
{
case 1:
fprintf(fil,"Vpravo\n");
printf("Vpravo\n\r");
break;
case 2:
fprintf(fil,"Vniz\n");
printf("Vniz\n\r");
break;
case 3:
fprintf(fil,"Vlevo\n");
printf("Vlevo\n\r");
break;
case 4:
fprintf(fil,"Vverh\n");
printf("Vverh\n\r");
break;
default:
fprintf(fil,"Start\n");
printf("Start\n\r");
break;
}
fprintf(fil,"WORK MATRIX\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr2+i*n+j));
}
fprintf(fil,"\n");
}
fprintf(fil,"************************************\n");
return;
}
// **************** UPGRADE PLAN *********************************//
void plmi(void)
{
int i,j,k,min,i1,j1,flagok;
ch = ch2;
flagok = 0;
i1=*zi;
j1 = *zj;
for(k=1;k<ch;k+=2){
i=*(zi+k);
j = *(zj+k);
if(*(matr+i*n+j) == -2){
*(matr+i1*n+j1) = *(matr+i*n+j);
*(matr+i*n+j) = 0;
flagok = 1;
break;
}
} // for
if(!flagok){
for(k=2;k<ch;k+=2){
i = *(zi+k);
j = *(zj+k);
if(*(matr+i*n+j) == -2)
*(matr+i*n+j) = 0;
} // for
i = *(zi+1);
j = *(zj+1);
min = *(matr+i*n+j);
for(k=3;k<ch;k+=2){
i=*(zi+k);
j=*(zj+k);
if(*(matr+i*n+j)<min)
min = *(matr+i*n+j);
}
if(min == -2) min = 0;
for(k=0;k<ch;k+=2){
i = *(zi+k);
j = *(zj+k);
*(matr+i*n+j) += min;
}
for(k=1;k<ch;k+=2){
i=*(zi+k);
j=*(zj+k);
*(matr+i*n+j)-=min;
}
} //if
// ***************** PROVERKA **************************//
printf("PROVERKA\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
free(matr2);free(zi);free(zj);free(pu);free(pv);
return;
}
void Bas(void)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr+i*n+j)!=0) basper++;
}
}
return;
}
void sohran(void)
{
// Sravnenie
int i,j,k;
for(k=0;k<ch;k++)
{
i=zi[k];
j=zj[k];
if((*(matr+i*n+j) == 0) && (basper < m+n-1))
{
*(matr+i*n+j) = -2;
basper++;
}//if
}
return;
}
// ************ SOZDANIE OPORNOGO PLANA **************************
// ************ METODOM SEVERNO-ZAPADNOGO YGLA *******************
void opplan1(void)
{
int i,j, ch1 = n-1;
//**************** Viydelenie pamyty *************************
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++)
{
for(j=ch1;j>=0;j--)
{
if(*(po+i)<*(pn+j))
{
*(matr+i*n+j)=*(po+i);
*(pn+j)-=*(po+i);
*(po+i)=0;
break;
}
*(matr+i*n+j)=*(pn+j);
*(po+i)-=*(pn+j);
*(pn+j)=0;
ch1--;
}
}
//*************** Proverka *************************
printf("Proverka\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
fprintf(fil,"matrix\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr+i*n+j));
}
fprintf(fil,"\n");
}
fprintf(fil,"*****************\n");
return;
}//******** opplan1
//************** SOZDANIE OPORNOGO PLANA ********************
//*************** METHOD NORD-WEST YGOL *********************
void opplan2(void)
{
int i,j,k_i,k_j=0, min = 32767, *kontr,fl;
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
if((kontr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++){
for(j=0;j<n;j++){
*(kontr+i*n+j) = 0;
}
}
for(i=0;i<m;i++){
fl = 0;
while(!fl){
for(j=0;j<n;j++){
if(*(st+i*n+j)<min){
if(*(kontr+i*n+j) == 0) {
min = *(st+i*n+j);
k_i = i; k_j = j;
}
}
}
*(kontr+k_i*n+k_j) = 1;
if(*(po+k_i)<*(pn+k_j)) {
min = 32767;
*(matr+k_i*n+k_j)=*(po+k_i);
*(pn+k_j)=*(po+k_i);
*(po+k_i)=0;
break;
}
else {
*(matr+k_i*n+k_j)=*(pn+k_j);
*(po+k_i)-=*(pn+k_j);
*(pn+k_j)=0;
min = 32767;
if(*(po+k_i) == 0) fl = 1;
}
}
}
printf("Proverka\n"); // proverka
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
fprintf(fil," matr\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){
fprintf(fil,"%5d",*(matr+i*n+j));
}
fprintf(fil,"\n");
}
fprintf(fil,"*********************************\n");
return;
}// opplan2
void main()
{
int i,j,met;
int flagok;
fil = fopen("otchet.txt","w");
clrscr();
gotoxy(1,3);
printf("WARNING USERS ---->\n\n\n");
printf("Ðåøåíèå çàêðûòîé òðàíñï.çàäà÷è\n\n");
printf("Áàçèñíûå ïåðåìåííûå,ðàâíûå íóëþ, ïîìå÷àþòñÿ -2;\n");
printf("Ãðàôîêëåòêà, îòíîñèòåëüíî êîòîðîé ñòðîèòñÿ öåïü\n");
printf("ïîìå÷àåòñÿ -1\n");
gotoxy(1,22);
printf("press anykey to contunio...\n");
getch();
clrscr();
data();
printf("press anykey to contunio...\n");
getch();
clrscr();
gotoxy(1,3);
printf("\n YOU selest method building first plan:\n");
printf("1-method NORD-WEST ygol\n");
printf("2-method NORD-EST ygol\n");
printf("3-method minimum element to string\n");
scanf("%d",&met);
gotoxy(1,22);
printf("press anykey, to contunie...\n");
getch();
//void opplan(void);
//void opplan1(void);
//void opplan2(void);
clrscr();
switch(met)
{
case 1: opplan();
break;
case 2: opplan1();
break;
case 3: opplan2();
break;
default: printf("íåâåðíî âûáðàí ÌÅÒÎÄ\n"); exit(-1);
}
basper = 0;
Bas();
flagok = 0;
if(basper<m+n-1)
{
//Åñëè â ïåðâîíà÷àëüíîì ïëàíå êîëè÷åñòâî áàçèñíûõ
//ïåðåìåííûõ, îòëè÷íûõ îò íóëÿ, ìåíüøå, ÷åì M+N-1
while(!flagok)
{
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr+i*n+j)==0)
{
*(matr+i*n+j) = -2;
flagok = 1;
basper++;
break;
} //if
}
if(flagok) break;
}
if(basper<m+n-1) flagok = 0;
}//while
}//if
for(;;)
{
fprintf(fil,"*********** Íà÷àëî ÄÎËÁÀÍÓÒÎÉ Èòåðàöèè**********\n");
basper = 0;
Bas();
//void sohran(void);
if(iter>0)
{
//Êîëè÷åñòâî áàçèñíûõ íåíóëåâûõ ïåðåìåííûõ <m+n-1
if(basper <m+n-1) sohran();
}
kost(); //****** Âûâîä îáùåé ñòîèìîñòè******
potenzial(); //*******Ïîäñ÷åò ïîòåíöèàëîâ********
ch2 = 0;
z = optim();
if(!z) break;
plmi();
iter++;
fprintf(fil,"%d ØÀÃ ÄÎÑÒÀÂØÅÉ ÄÎ ÑÚÅÕÀÂØÅÉ ÊÐÛØÈ ÈÒÅÐÀÖÈÈ",iter);
}
//************* ÏÐÎÂÅÐÊÀ************
printf("\n\nOPTIMAL PLAN :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
fprintf(fil,"optimal PLAN :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr+i*n+j));
}
fprintf(fil,"\n");
}
kost(); //************ÂÛÂÎÄ îáùåé ñòîèìîñòè***********
fclose(fil);
clrscr();
printf("Îò÷åò î ïðîäåëàííîé ðàáîòå ÏÐÎÃÐÀÌÌÛ â ôàéëå otchet.txt");
getch();
return;
} // main