分支限界法求旅行售貨員問(wèn)答物聯(lián)

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第X次實(shí)驗(yàn)姓名劉悅學(xué)號(hào)20130808011班級(jí)物聯(lián)1301班時(shí)間12.26上午地點(diǎn)工訓(xùn)樓C棟309實(shí)驗(yàn)名稱(chēng)分支限界法求旅行售貨員問(wèn)題通過(guò)上機(jī)實(shí)驗(yàn)，掌握分支限界算法的思想，利用Dijkstra 算法求解最短路實(shí)驗(yàn)?zāi)康膹讲?shí)現(xiàn)。使用一個(gè)優(yōu)先隊(duì)列來(lái)存儲(chǔ)活結(jié)點(diǎn)。 優(yōu)先隊(duì)列中的每個(gè)活結(jié)點(diǎn)都存儲(chǔ)從根到該活結(jié)點(diǎn)的相應(yīng)路徑。 算法開(kāi)始創(chuàng)建一個(gè)最小堆， 表示活結(jié)點(diǎn)優(yōu)先隊(duì)列。 堆中每個(gè)結(jié)點(diǎn)的Icost值是優(yōu)先隊(duì)列的優(yōu)先級(jí)。接著計(jì)算出圖中每個(gè)頂點(diǎn)的最小費(fèi)用出邊并用Min out記錄。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊,則該圖不實(shí)驗(yàn)原理可能有回路，算法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的

2、算法初始化。算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒子結(jié)點(diǎn)。點(diǎn)處，已確定的回路中的唯一頂點(diǎn)為頂點(diǎn)s=0,x0=1,x1:n-1=(2,3,n),cc=0，且 rcost 為 MinoutiMin out 作在該結(jié)1.初始時(shí)有的和，算法bestc記錄當(dāng)前最優(yōu)值。算法的終止條件是排列樹(shù)的葉結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)當(dāng)s=n-2時(shí),當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。相應(yīng)的一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中,否則去掉該葉結(jié)點(diǎn)。當(dāng)s<n-2時(shí),算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)。當(dāng)前擴(kuò)展結(jié)點(diǎn)所對(duì)應(yīng)的路徑是x0:s，其可行兒子結(jié)點(diǎn)是從剩余頂點(diǎn)xs+1:

3、n-1中選取的頂點(diǎn)xi,且(xs,xi)是有向圖G的一條邊。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn),計(jì)算出其前綴(xO:s,xi)的費(fèi)用CC和相應(yīng)的下界 Icost。當(dāng)Icostvbestc時(shí),將這個(gè)可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。算法結(jié)束時(shí)返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v給出。實(shí)驗(yàn)步驟算法開(kāi)始創(chuàng)建一個(gè)最小堆，表示活結(jié)點(diǎn)優(yōu)先隊(duì)列。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路，算法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的Min out作算法初始化。算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒子結(jié)點(diǎn)。算法的終止條件是排列樹(shù)的葉結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)。當(dāng)s=n-2時(shí),當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列

4、樹(shù)中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)相應(yīng)的一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中，否則去掉該葉結(jié)點(diǎn)。當(dāng)s<n-2時(shí)，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)。/定義圖的頂點(diǎn)數(shù) const int N = 4;關(guān)鍵代碼/*定義Traveling類(lèi)來(lái)存儲(chǔ)的信息。*/temp latevciass Typeclass Traveli ng；I*public:Type BBTS P(i nt v);int n;Type *a,/ NoEdge,cc,bestc;/圖G的頂點(diǎn)數(shù)/圖G的鄰接矩陣II圖G的無(wú)邊標(biāo)識(shí)II當(dāng)前費(fèi)用II當(dāng)前最小費(fèi)用定義MinHeapNode類(lèi)來(lái)存儲(chǔ)最

5、小堆中頂點(diǎn)的信息。icost表示子樹(shù)費(fèi)用的下界。cc表示當(dāng)前費(fèi)用。rcost表示xs:n-1中頂點(diǎn)最小出邊費(fèi)用和。s表示根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:s。;/*x表示需要進(jìn)一步搜索的頂點(diǎn)是xs+1,n-1。temp latevciass Typeclass MinHeapN ode*/friend Traveli ng<T ype>public:op erator Typ e() constprivate:retur n Icost;Type lcost,int s,x;cc,rcost;/子樹(shù)費(fèi)用的下界/當(dāng)前費(fèi)用/xs: n-1中頂點(diǎn)最小出邊費(fèi)用和/根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:

6、s/需要進(jìn)一步搜索的頂點(diǎn)是xs+1,n-1BBTSP函數(shù)為使用優(yōu)先隊(duì)列求最小費(fèi)用。這里是使用一個(gè)優(yōu)先隊(duì)列來(lái)存儲(chǔ)活結(jié)點(diǎn)。優(yōu)先隊(duì)列中的每個(gè)活結(jié)點(diǎn)都存儲(chǔ)從根到該活結(jié)點(diǎn)的相應(yīng)路徑。算法開(kāi)始創(chuàng)建一個(gè)最小堆，表示活結(jié)點(diǎn)優(yōu)先隊(duì)列。堆中每個(gè)結(jié)點(diǎn)的小費(fèi)用出邊并用圖不可能有回路作算法初始化。Icost值是優(yōu)先隊(duì)列的優(yōu)先級(jí)。 接著計(jì)算出圖中每個(gè)頂點(diǎn)的最Minout記錄。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊,，算法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒子結(jié)點(diǎn)。結(jié)點(diǎn)處，已確定的回路中的唯一頂點(diǎn)為頂點(diǎn)1.初則該Minout在該s=0,x0=1,x1:n-1=(2,3,n),cc

7、=0，且 rcost 為 Minouti的和，算法 bestc記錄當(dāng)前最優(yōu)值。算法的終止條件是排列樹(shù)的葉結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)。當(dāng)s=n-2時(shí),當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)相應(yīng)的一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中,否則去掉該葉結(jié)點(diǎn)。當(dāng)s<n-2時(shí),算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)。當(dāng)前擴(kuò)展結(jié)點(diǎn)所對(duì)應(yīng)的路徑是x0:s，其可行兒子結(jié)點(diǎn)是從剩余頂點(diǎn)xs+1:n-1中選取的頂點(diǎn)xi,且(xs,xi)是有向圖G的一條邊。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn),計(jì)算出其前綴(x0:s,xi)的費(fèi)用CC和相應(yīng)的下界 Icost。當(dāng)Icostvbes

8、tc時(shí),將這個(gè)可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。算法結(jié)束時(shí)返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v給出。temp latevciass Type*/Type Traveli ng<Ty pe>:BBTS P(in t v)/定義有1000個(gè)結(jié)點(diǎn)的最小堆MinHeap <Mi nH ea pN ode<T ype> > H(1000);/動(dòng)態(tài)分配內(nèi)存Type * MinOut = new Typ e n+1;/計(jì)算MinOuti= 頂點(diǎn)i的最小出邊費(fèi)用Type Mi nSum = 0; /最小出邊費(fèi)用和for(i nt i=1; i<=n; i+)Ty

9、pe Min = NoEdge;for(i nt j=1; j<=n; j+)if(aij!=NoEdge && (aij<Mi n|Mi n=NoEdge)Min = aij;/如果某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路，算法結(jié)束if(Min = NoEdge)retur n NoEdge;Min Outi = Min;Mi nSum += Min;/初始化MinHeapN ode<Ty pe> E;/動(dòng)態(tài)內(nèi)存分配E.x = new in t n;/初始化for(i nt i=0; i<n; i+)E.xi = i+1;E.s = 0;E.cc =

10、 0;/根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑為 x0:s/當(dāng)前費(fèi)用E.rcost = Mi nSum;/最小出邊費(fèi)用和Type bestc = NoEdge;/搜索排列空間樹(shù)while(E.s< n-1)/ 非葉結(jié)點(diǎn)if(E.s = n-2)/當(dāng)前擴(kuò)展節(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn)/再加2條邊構(gòu)成回路/所構(gòu)成回路是否優(yōu)于當(dāng)前最優(yōu)解if(aE.x n-2E.x n-1!=NoEdgeaE.x n-11!=NoEdgeelse&&&& (E.cc+aE.x n-2E.x n-1+aE.x n-11<bestcII bestc = NoEdge)/費(fèi)用更小的回路/記錄最小費(fèi)用bes

11、tc = E.cc + aE.x n-2E.x n-1+aE.x n-11;/記錄結(jié)點(diǎn)的信息E.cc = bestc;E.l cost = bestc;E.s+;/將結(jié)點(diǎn)放入最小堆中H.I nsert(E);delete E.x;/ 舍棄擴(kuò)展節(jié)點(diǎn)else/當(dāng)前擴(kuò)展節(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn)for(i nt i=E.s+1;i< n;i+)if(aE.xE.sE.xi!=NoEdge)/可行兒子節(jié)點(diǎn)Type cc = E.cc + aE.xE.sE.xi;Type rcost = E.rcost - Mi nOutE.xE.s;Type b = cc + rcost;/ 下界if(b<be

12、stc | bestc = NoEdge)/子樹(shù)可能含有最優(yōu)解/節(jié)點(diǎn)插入最小堆MinHeapN ode<Ty pe> N;N.x = new in t n;/保存結(jié)點(diǎn)信息for(i nt j=0; j< n; j+)N.x j = E.x j;N.xE.s+1 = E.xi;N.xi = E.xE.s+1;N.cc = cc;N.s = E.s + 1;N.lcost = b;N.rcost = rcost;/將結(jié)點(diǎn)插入最小堆H.I nsert(N);delete E.x;/完成節(jié)點(diǎn)擴(kuò)展/最小堆空了就結(jié)束if(H.Size() = 0)break;H.DeleteMi n(E

13、);/取下一擴(kuò)展節(jié)點(diǎn)II如果最小費(fèi)用為 NoEdge,則圖中無(wú)回路if(bestc = NoEdge)return NoEdge;/ 無(wú)回路/將最優(yōu)解復(fù)制到v1:nfor(i nt i=0; i<n; i+)vi+1 = E.xi;while(true)/釋放最小堆中所有節(jié)點(diǎn)delete E.x;if(H.Size() = 0)break;H.DeleteMi n(E);/取下一擴(kuò)展節(jié)點(diǎn)retur n bestc;葉結(jié)點(diǎn)路徑長(zhǎng)度路徑順序L591 ->2->3_>4->1M661 ->2->4_>3->lN251->3->2_&g

14、t;4_>1O661->3->4->2->1P251->4->2->3->1Q591->4->3->2->14.由上表可以知道最短的為至葉結(jié)點(diǎn)Q的路徑1 ->3 ->2 ->4->1度為25 。實(shí)驗(yàn)心得，長(zhǎng)這里可能會(huì)有疑問(wèn)，至結(jié)點(diǎn)P的距離也為25，為什么不選擇路徑 1。這是因?yàn)橹挥挟?dāng)求得的路徑比當(dāng)前最優(yōu)值小的時(shí)候才會(huì)記錄，這里一樣大，所以不會(huì)記錄，也就不會(huì)輸出這條路徑。5.算法輸出結(jié)果如下:刁 EVC+-hXDev-CppVCon solePa user 啟陽(yáng)分支限界法求TEF間迦團(tuán)的頂占個(gè)為

15、：_4t>3 >Z>4>1最短回路前超b 25The time IsProcess exited witb retut*n value 6 Ppess an# k&y to continue _ _ _6.可以看到輸出的結(jié)果與分析的結(jié)果一樣，所以算法實(shí)現(xiàn)正確。并且可以看到分支限界法在實(shí)現(xiàn)我們給的這個(gè)圖的時(shí)候，時(shí)間性能很好。說(shuō)實(shí)話，個(gè)人覺(jué)得旅行售貨員問(wèn)題的實(shí)現(xiàn)算法不好寫(xiě),因?yàn)槁眯惺圬泦T問(wèn)題的解空間是一棵排列樹(shù)，個(gè)人覺(jué)得排列樹(shù)較子集樹(shù)來(lái)說(shuō)，更加難以理解。這個(gè)算法的實(shí)現(xiàn)中，有一個(gè)地方卡了很久， 雖然可以通過(guò)嘗試數(shù)值的方法來(lái)確定到底是哪個(gè)， 但是還是覺(jué)得自己理解了比較好

16、，畢竟不是什么東西都可以挨個(gè)值試出來(lái)的，如果有一個(gè)問(wèn)題有很多可能的數(shù)值如果要試的話會(huì)很費(fèi)時(shí)間?？撕芫玫牡胤骄褪钱?dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn)的時(shí)候數(shù)值是什么。這個(gè)算法中是子集樹(shù)的第二層的時(shí)候s （層數(shù)）的s為0。拿我們給的這個(gè)圖的例子來(lái)說(shuō)，就是B那一層s=0。所以當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn)的時(shí)候s應(yīng)該等于n-2，而不是n-1。這里是因?yàn)樗惴ǖ牡?個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中唯一兒子結(jié)點(diǎn)。在該結(jié)點(diǎn)處，已經(jīng)確定的回路中唯一頂點(diǎn)為頂點(diǎn)剛說(shuō)的，如果不知道到底是哪個(gè)值的話，可以依次嘗試一下三個(gè)值，看為哪個(gè)值的時(shí)候輸出正確的最短路徑。這里的這個(gè)代碼的編寫(xiě)主要是用來(lái)與前面的回溯法進(jìn)行比較。1。像我剛n-1和n-2

17、這回溯法主要是使用的深度優(yōu)先的探索， 就是從一個(gè)子結(jié)點(diǎn)向下擴(kuò)展，一直擴(kuò)展到葉子結(jié)點(diǎn)或者不能繼續(xù)向下擴(kuò)展。而這里的分支限界法是寬度優(yōu)先的擴(kuò)展策略,用的是優(yōu)先隊(duì)列來(lái)實(shí)現(xiàn)的話，就是每次擴(kuò)展優(yōu)先級(jí)最小的結(jié)點(diǎn)。因?yàn)榻o定的這個(gè)圖的結(jié)點(diǎn)比較少，所以?xún)蓚€(gè)算法輸出的時(shí)間都為通過(guò)這一組測(cè)試數(shù)據(jù)給出兩種算法的時(shí)間比較分析。這里使0，無(wú)法通過(guò)這次實(shí)驗(yàn)，編寫(xiě)了分支限界法求旅行售貨員問(wèn)題，掌握了分支限界法求解問(wèn)題的基本步驟， 掌握了旅行售貨員問(wèn)題的問(wèn)題描述，求解過(guò)程。相信在以后的學(xué)習(xí)工作中可以熟練使用分支限界法求解問(wèn)題,也可以使用多種方法求實(shí)驗(yàn)得分解旅行售貨員問(wèn)題。助教簽名附錄：完整代碼#in elude "M

18、i nH ea p.h"#in elude <iostream>#in elude<estdlib>#in elude<time.h>#in elude<ioma nip>#in elude<stdlib.h>#defi ne NoEdge -1using n ames pace std;/定義圖的頂點(diǎn)數(shù)const int N = 4;/*定義Traveling 類(lèi)來(lái)存儲(chǔ)的信息。*/temp latevciass Typeclass Traveli ngpublic:Type BBTS P(i nt v);int n;/圖G

19、的頂點(diǎn)數(shù)Type *a./圖G的鄰接矩陣/ NoEdge,/圖G的無(wú)邊標(biāo)識(shí)cc,/當(dāng)前費(fèi)用bestc;/當(dāng)前最小費(fèi)用;/*定義MinHeapNode類(lèi)來(lái)存儲(chǔ)最小堆中頂點(diǎn)的信息。幵*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*Icost表示子樹(shù)費(fèi)用的下界。cc表示當(dāng)前費(fèi)用。rcost表示xs:n-1中頂點(diǎn)最小出邊費(fèi)用和。s表示根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:s。x表示需要進(jìn)一步搜索的頂點(diǎn)是xs+1,n-1。*/temp latevciass Type class MinHeapN odefriend Traveli ng<T ype>pu

20、blic:op erator Typ e() constretur n Icost;private:Type lcost,/子樹(shù)費(fèi)用的下界cc,/當(dāng)前費(fèi)用int s,*x;rcost;/xs: n-1中頂點(diǎn)最小出邊費(fèi)用和II根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:s需要進(jìn)一步搜索的頂點(diǎn)是xs+1,n-1;/*BBTSP函數(shù)為使用優(yōu)先隊(duì)列求最小費(fèi)用。這里是使用一個(gè)優(yōu)先隊(duì)列來(lái)存儲(chǔ)活結(jié)點(diǎn)。優(yōu)先隊(duì)列中的每個(gè)活結(jié)點(diǎn)都存儲(chǔ)從根到 該活結(jié)點(diǎn)的相應(yīng)路徑。算法開(kāi)始創(chuàng)建一個(gè)最小堆，表示活結(jié)點(diǎn)優(yōu)先隊(duì)列。堆中每個(gè) 結(jié)點(diǎn)的lcost值是優(yōu)先隊(duì)列的優(yōu)先級(jí)。接著計(jì)算出圖中每個(gè)頂點(diǎn)的最小費(fèi)用出邊并 用Min out記錄。如果所給的有向

21、圖中某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的Min out作算法初始化。算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒子結(jié)點(diǎn)。在該結(jié)點(diǎn)處，已確定的回路中n),cc=O ，且 rcost的唯一頂點(diǎn)為頂點(diǎn)1.初始時(shí)有s=0,x0=1,x1:n-1=(2,3.為Min OU圳的和，算法bestc記錄當(dāng)前最優(yōu)值。算法的終止條件是排列樹(shù)的葉結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)。當(dāng)s=n-2時(shí),當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。如果該葉結(jié)點(diǎn)相應(yīng)的一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中，否則去掉該葉結(jié)點(diǎn)。當(dāng)s<n-2時(shí),算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒

22、子結(jié)點(diǎn)。當(dāng)前擴(kuò)展結(jié)點(diǎn)所對(duì)應(yīng)的路徑是x0:s，其可行兒子結(jié)點(diǎn)是從剩余頂點(diǎn)xs+1:n-1中選取的頂點(diǎn)xi,且(xs,xi),計(jì)算出其前綴是有向圖G的一條邊。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn)(x0:s,xi) 的費(fèi)用cc和相應(yīng)的下界Icost。當(dāng)lcost<bestc 時(shí)，將這個(gè)可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。算法結(jié)束時(shí)返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v給出。*/temp late<class TypeType Traveli ng<Ty pe>:BBTS P(in t v)/定義有1000個(gè)結(jié)點(diǎn)的最小堆MinHeapvMinH ea pNode<Ty

23、pe> > H(1000);/動(dòng)態(tài)分配內(nèi)存Type * Mi nOut = new Typ e n+1;/計(jì)算MinOuti= 頂點(diǎn)i的最小出邊費(fèi)用Type Mi nSum = 0; II最小出邊費(fèi)用和for(i nt i=1; i<=n; i+)Type Min = NoEdge;for(i nt j=1; j<=n; j+)if(aij!=NoEdge && ij<Mi n| |Mi n=NoEdge)Min = aij;/如果某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路，算法結(jié)束 if(Min = NoEdge)retur n NoEdge;Mi n

24、Outi = Mi n;Mi nSum += Min;/初始化MinHeapN ode<Ty pe> E;/動(dòng)態(tài)內(nèi)存分配E.x = new in t n;/初始化 for(i nt i=0; i<n; i+)E.xi = i+1;E.s = 0;/根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑為xO:sE.cc = 0;/當(dāng)前費(fèi)用E.rcost = Mi nSum;/最小出邊費(fèi)用和Type bestc = NoEdge;/搜索排列空間樹(shù)while(E.s <n-1)/非葉結(jié)點(diǎn)if(E.s = n-2)/當(dāng)前擴(kuò)展節(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn)/再加2條邊構(gòu)成回路/所構(gòu)成回路是否優(yōu)于當(dāng)前最優(yōu)解 if(aE.x

25、 n-2E.x n-1!=NoEdge && aE.x n-11!=NoEdge&& (E.cc+aE.x n-2E.x n-1+aE.x n-11<bestcII bestc = NoEdge)/費(fèi)用更小的回路/記錄最小費(fèi)用 bestc = E.CC + aE.x n-2E.x n-1+aE.x n-11;/記錄結(jié)點(diǎn)的信息E.CC = bestc;E.lcost = bestc;E.S+;/將結(jié)點(diǎn)放入最小堆中H.I nsert(E);elsedelete E.x;/舍棄擴(kuò)展節(jié)點(diǎn)else/當(dāng)前擴(kuò)展節(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn)for(i nt i=E.s+1;i &

26、lt;n ;i+)if(aE.xE.sE.xi!=NoEdge)/可行兒子節(jié)點(diǎn)Type cc = E.cc + aE.xE.sE.xi;Type rcost = E.rcost - Mi nOutE.xE.s;Type b = cc + rcost;/下界if(b<bestc | bestc = NoEdge)/子樹(shù)可能含有最優(yōu)解/節(jié)點(diǎn)插入最小堆MinHeapN ode<Ty pe> N;N.x = new intn;/保存結(jié)點(diǎn)信息 for(i nt j=0; j< n; j+)N.xj = E.xj;N.xE.s+1 = E.xi;N.xi = E.xE.s+1;N.

27、cc = cc;N.s = E.s + 1;N.lcost = b;N.rcost = rcost;/將結(jié)點(diǎn)插入最小堆H.I nsert(N);delete E.x;/ 完成節(jié)點(diǎn)擴(kuò)展/最小堆空了就結(jié)束if(H.Size() = 0)break;H.DeleteMi n( E);/取下一擴(kuò)展節(jié)點(diǎn)/如果最小費(fèi)用為NoEdge,則圖中無(wú)回路 if(bestc = NoEdge)return NoEdge;/ 無(wú)回路/將最優(yōu)解復(fù)制到v1:n for(i nt i=0; i<n; i+)vi+1 = E.xi;while(true)/釋放最小堆中所有節(jié)點(diǎn)delete E.x;if(H.Size()

28、 = 0)break;H.DeleteMi n( E);/取下一擴(kuò)展節(jié)點(diǎn)return bestc;/*main函數(shù)是主函數(shù)。實(shí)現(xiàn)輸入輸出，調(diào)用之前的分支限界法函數(shù)BBTSP求得最優(yōu)值,并且通過(guò)數(shù)組v得到最優(yōu)解。輸出最短路徑和最短路徑的長(zhǎng)度。*/int mai n()cout<<"<<e ndl;cout<<"分支限界法求TSP問(wèn)題"<<e ndl;cout<<"<<e ndl;int bestxN+1;int bestle ngth;/輸出圖的頂點(diǎn)個(gè)數(shù)cout<<&quo

29、t;圖的頂點(diǎn)個(gè)數(shù)為："<<N<<e ndl;/動(dòng)態(tài)內(nèi)存分配int *a=new in t*N+1;for(i nt i=O;i<=N;i+)ai=new in tN+1;/初始化for(i nt i=0;i<=N;i+)for(i nt j=0;j<N;j+)aij=NoEdge;a12=30;a13=6;a14=4;a21=30;a23=5;a24=10;a31=6;a32=5;a34=20;a41=4;a42=10;a43=20;II定義Traveling 類(lèi)型的變量tTraveli ng<int> t;/給變量t賦初值t.a

30、 = a;t.n = N;/開(kāi)始計(jì)時(shí)clock_t start,e nd,over;start=clock();en d=clock();over=e nd-start;start=clock();/調(diào)用函數(shù)bestle ngth=t.BBTS P(bestx);/結(jié)束計(jì)時(shí)en d=clock();/輸出最短回路cout<<"最短回路為："<<e ndl;for(i nt i=1;i<=N;i+)cout<<bestxi<<"->"cout<<bestx1<<e ndl;

31、/輸出最短回路長(zhǎng)度cout<<"最短回路的長(zhǎng)為："<<bestle ngth<<e ndl;/輸出時(shí)間prin tf("The time is %6.3fn",(double)(e nd-start-over)/CLK_TCK);/釋放動(dòng)態(tài)分配的內(nèi)存for(i nt i=O;i<=N;i+)delete ai;delete a;a=0;return 0;最小堆得實(shí)現(xiàn):#in clude <iostream> using n ames pace std;temp late<class Type class Graph;/*定義MinHeap 類(lèi)來(lái)表示最小堆的信息。*/temp latevciass T> class MinHeapp rivate:T* Hea p;/堆數(shù)組的指針int maxsize;/堆最多的結(jié)點(diǎn)數(shù)目int n;/當(dāng)前堆中的結(jié)點(diǎn)數(shù)目/交換函數(shù) void sw ap(T &am