貪婪法解貨郎擔(dān)問題

《貪婪法解貨郎擔(dān)問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、/*按以下貪婪法求解貨郎擔(dān)問題。貨郎擔(dān)問題是指給定一個(gè)無向圖，已知各頂點(diǎn)的坐標(biāo),能求出各頂點(diǎn)之間邊的權(quán)。要在在這個(gè)圖中找一個(gè)閉合回路，使回路經(jīng)過圖中的每一個(gè)點(diǎn),而回路各邊的權(quán)之和為最小。求解貨郎擔(dān)問題的貪婪算法如下：{1、輸入無向圖的頂點(diǎn)數(shù)n(設(shè)各點(diǎn)依次自0開始順序連續(xù)編號(hào))；2、順序輸入各頂點(diǎn)的坐標(biāo)；3、計(jì)算邊的權(quán),及累計(jì)邊數(shù)(n*(n-l)/2)；4、建立按邊的權(quán)自小到大排序的邊權(quán)順序表；5、用貪婪算法，選擇邊。入選的邊必須符合以下兩個(gè)條件：5.1不會(huì)使該邊的每個(gè)頂點(diǎn)與兩條以上已入選邊相聯(lián)系

2、。5.2不會(huì)因入選的邊形成回路，除非該邊入選后，正好邊數(shù)等于頂點(diǎn)數(shù)。}為存儲(chǔ)入選邊的信息，可用頂點(diǎn)聯(lián)系表，該表的表元有三個(gè)成分：與該頂點(diǎn)相連的已入選的邊數(shù)，與該頂點(diǎn)相連的頂點(diǎn)1,與該點(diǎn)相連的頂點(diǎn)2。與每個(gè)頂點(diǎn)相連的邊只能有兩條入選，故最多只有兩個(gè)別的頂點(diǎn)與它相連。如果由(5)找不到解，可適當(dāng)調(diào)整邊權(quán)順序表，改變相同邊權(quán)的次序。重新執(zhí)行(5)o如果找到解，就能從端點(diǎn)聯(lián)系表求出回路的軌跡。選擇邊(i,j)合理，首先是這條邊的加入，使這兩個(gè)頂點(diǎn)只與一個(gè)頂點(diǎn)相連；該邊加入會(huì)使其中一個(gè)頂點(diǎn)與3個(gè)頂點(diǎn)相連，

3、則這條邊的加入是不合理的。另外，這條邊的加入,使與早先加入的邊構(gòu)成回路，則是不合理的；否則，是合理的。為了能判定邊(i,j)的入選是否會(huì)構(gòu)成回路，有兩種辦法：1)臨時(shí)復(fù)制出一個(gè)頂點(diǎn)聯(lián)系表，并將邊(i,j)入選，然后反復(fù)去掉其中已只與一個(gè)頂點(diǎn)相連的頂點(diǎn)，最后若還有與兩個(gè)頂點(diǎn)相連的頂點(diǎn)，并且這樣的頂點(diǎn)數(shù)大于等于3個(gè)，則說明邊(i,j)的入選將會(huì)構(gòu)成回路。2)由于路線中一個(gè)頂點(diǎn)最多只能與兩個(gè)頂點(diǎn)相連，可從i頂點(diǎn)出發(fā)，沿著選中的連，往前走，如能走到j(luò)頂點(diǎn)，貝0加入邊(i,j)將構(gòu)成回路；如在走的過程中到

4、了還只有與一個(gè)頂點(diǎn)相連的頂點(diǎn)，則不會(huì)構(gòu)成回路?！境绦颉?/^includettincludettdefineMAXN300^definePN30^defineSQR2(x,y)(x)*(x)+(y)*(y)typedefstruct{intp⑵;doubled;}TDR;/*兩頂點(diǎn)及之間的距離*/typedefstruct{intn;intp[2];}TR;//相聯(lián)頂點(diǎn)數(shù)，相聯(lián)的頂點(diǎn)typedefstruct{doublex,y;}POINT;/*點(diǎn)的類型，X坐

5、標(biāo)、Y坐標(biāo)*/TDRdr[MAXN];/*邊長表*/TRr[PN];/*頂點(diǎn)聯(lián)系表*/POINTp[PN];intpn;intdistance(POINT*pp,intn,TDR*t)//求所有頂點(diǎn)對之間的矩離{intk,i,j;for(k=i=0;i

6、d(TDR*t,intn)//排序{TDRtemp;intk,m,j;m=n-1;while(m>0){for(k=j=0;jt[j+l].d){temp=t[j];t[j]=t[j+l];t[j+l]=temp;k=j;}m=k;}}voidselect(TR*r,inti,intj){r[i]?p[r[i]?n++]=j;//i接上j,i的度增1,頂點(diǎn)j成為i的聯(lián)系頂點(diǎn)r[j].p[r[j].n++]=i;//j接上i,j的度增1,頂點(diǎn)i成為j的聯(lián)系頂點(diǎn)}intiscirc

7、uit(TR*r,intn,inti,intj){intk,u;TRtr[PN]:if(r[i].n==2

8、

9、r[j].n==2)return1;if(r[i]?n二二0

10、

11、r[j]?n==0)return0;/*自i頂點(diǎn)岀發(fā)，順著已選中的邊能走到j(luò),則表示加入邊(i,j)將產(chǎn)生回路intk0=i,kl=r[i].p[0];intloop=0;while(kl!=j){kt=kO;kO=kl;if(r[kl].n==1)return0;kl=r[kl].p[0]=kt?r[kl].p[l]:r[

12、kl].p[0];}return1;*/for(u=0;u