貪婪法解貨郎擔問題

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

2、會使該邊的每個頂點與兩條以上已入選邊相聯(lián)系。5.2不會因入選的邊形成回路，除非該邊入選后，正好邊數(shù)等于頂點數(shù)。為存儲入選邊的信息，可用頂點聯(lián)系表，該表的表元有三個成分：與該頂點相連的已入選的邊數(shù)，與該頂點相連的頂點1與該點相連的頂點2。與每個頂點相連的邊只能有兩條入選，故最多只有兩個別的頂點與它相連。如果由(5)找不到解，可適當調(diào)整邊權(quán)順序表，改變相同邊權(quán)的次序。重新執(zhí)行(5)o如果找到解，就能從端點聯(lián)系表求出回路的軌跡。選擇邊(ij)

3、合理，首先是這條邊的加入，使這兩個頂點只與一個頂點相連；該邊加入會使其中一個頂點與3個頂點相連，則這條邊的加入是不合理的。另外，這條邊的加入使與早先加入的邊構(gòu)成回路，則是不合理的；否則，是合理的。為了能判定邊(ij)的入選是否會構(gòu)成回路，有兩種辦法：1)臨時復(fù)制出一個頂點聯(lián)系表，并將邊(ij)入選，然后反復(fù)去掉其中已只與一個頂點相連的頂點，最后若還有與兩個頂點相連的頂點，并且這樣的頂點數(shù)大于等于3個，則說明邊(ij)的入選將會構(gòu)成回路。

4、2)由于路線中一個頂點最多只能與兩個頂點相連，可從i頂點出發(fā)，沿著選中的連，往前走，如能走到j(luò)頂點，貝0加入邊(ij)將構(gòu)成回路；如在走的過程中到了還只有與一個頂點相連的頂點，則不會構(gòu)成回路?！境绦颉縙includettincludettdefineMAXN300^definePN30^defineSQR2(xy)(x)(x)(y)(y)typedefstructintp⑵doubledTDR兩頂點及之間的距離typedefstruct

5、intnintp[2]TR相聯(lián)頂點數(shù)，相聯(lián)的頂點typedefstructdoublexyPOINT點的類型，X坐標、Y坐標TDRdr[MAXN]邊長表TRr[PN]頂點聯(lián)系表POINTp[PN]intpnintdistance(POINTppintnTDRt)求所有頂點對之間的矩離intkijf(k=i=0i=3voidmain()intindoublexyprintfC輸入點數(shù)n(n30)n)scanf(“%d“printf(“輸入

6、%(1個點的坐標n“n)f(i=0ini)scanf(“%lf%lf“p[i].x=xp[i].y=yTDRdr[MAXN]ttTRr[PN]intjkhmkkiiintcourse[PN]doubledistf(i=0ini)r[i].n=0所有的頂點都不在被選中的邊上m=distance(pndr)std(drm)ii=0kk=1dodist=0k=h=0doi=dr[k].p[0]j=dr[k].p[l]if(r[ij.n=1當前