分支限界法求旅行售貨員問(wèn)題_物聯(lián)1301班_劉悅_201308080112

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第 X 次實(shí)驗(yàn)姓名劉悅學(xué)號(hào)201308080112班級(jí)物聯(lián)1301班時(shí)間12.26上午地點(diǎn)工訓(xùn)樓C棟309 實(shí)驗(yàn)名稱分支限界法求旅行售貨員問(wèn)題實(shí)驗(yàn)?zāi)康?通過(guò)上機(jī)實(shí)驗(yàn)，掌握分支限界算法的思想，利用Dijkstra 算法求解最短路徑并實(shí)現(xiàn)。實(shí)驗(yà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)的lcost值是優(yōu)先隊(duì)列的優(yōu)先級(jí)。接著計(jì)算出圖中每個(gè)頂點(diǎn)的最小費(fèi)用出邊并用Minout記錄。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路,算法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的

2、Minout作算法初始化。算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒子結(jié)點(diǎn)。在該結(jié)點(diǎn)處，已確定的回路中的唯一頂點(diǎn)為頂點(diǎn)1.初始時(shí)有s=0,x0=1,x1:n-1=(2,3,n),cc=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-

3、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)的下界lcost。當(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給出。實(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ì)算出的Minout作算法初始化。 算法第一個(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ò)展

4、結(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)。關(guān)鍵代碼/定義圖的頂點(diǎn)數(shù) const int N = 4; /*=定義Traveling類來(lái)存儲(chǔ)的信息。=*/ template<class Type> class Traveling public: Type BBTSP(int v); int n; /圖G的頂點(diǎn)數(shù) Type *a, /圖G的鄰接矩陣 / NoEdge, /圖G的無(wú)邊標(biāo)識(shí) cc, /當(dāng)前費(fèi)用 bestc; /當(dāng)前最小

5、費(fèi)用 ; /*= 定義MinHeapNode類來(lái)存儲(chǔ)最小堆中頂點(diǎn)的信息。* lcost表示子樹(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。 =*/ template<class Type> class MinHeapNode friend Traveling<Type> public: operator Type() const return lcost; private: Type lcost, /子樹(shù)費(fèi)用的下界 cc, /當(dāng)前費(fèi)用 rcos

6、t; /xs:n-1中頂點(diǎn)最小出邊費(fèi)用和 int s, /根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:s *x; /需要進(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)用出邊并用Minout記錄。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路,算法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的Minout作算法初始化。算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒

7、子結(jié)點(diǎn)。在該結(jié)點(diǎn)處，已確定的回路中的唯一頂點(diǎn)為頂點(diǎn)1.初始時(shí)有s=0,x0=1,x1:n-1=(2,3,n),cc=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ò)展

8、結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn),計(jì)算出其前綴(x0:s,xi)的費(fèi)用cc和相應(yīng)的下界lcost。當(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給出。 =*/ template<class Type> Type Traveling<Type>:BBTSP(int v) /定義有1000個(gè)結(jié)點(diǎn)的最小堆 MinHeap<MinHeapNode<Type> > H(1000); /動(dòng)態(tài)分配內(nèi)存 Type * MinOut = new Typen+1; /計(jì)算MinOuti = 頂

9、點(diǎn)i的最小出邊費(fèi)用 Type MinSum = 0; /最小出邊費(fèi)用和 for(int i=1; i<=n; i+) Type Min = NoEdge; for(int j=1; j<=n; j+) if(aij!=NoEdge && (aij<Min|Min=NoEdge) Min = aij; /如果某個(gè)頂點(diǎn)沒(méi)有出邊,則該圖不可能有回路,算法結(jié)束 if(Min = NoEdge) return NoEdge; MinOuti = Min; MinSum += Min; /初始化 MinHeapNode<Type> E;/動(dòng)態(tài)內(nèi)存分配 E.x

10、= new intn; /初始化 for(int i=0; i<n; i+) E.xi = i+1; E.s = 0; /根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑為x0:s E.cc = 0; /當(dāng)前費(fèi)用 E.rcost = MinSum;/最小出邊費(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.xn-2E.xn-1!=NoEdge && aE.xn-11!=NoEdge && (E.cc

11、+aE.xn-2E.xn-1+aE.xn-11<bestc | bestc = NoEdge) /費(fèi)用更小的回路/記錄最小費(fèi)用 bestc = E.cc + aE.xn-2E.xn-1+aE.xn-11; /記錄結(jié)點(diǎn)的信息 E.cc = bestc; E.lcost = bestc; E.s+;/將結(jié)點(diǎn)放入最小堆中 H.Insert(E); else delete E.x;/舍棄擴(kuò)展節(jié)點(diǎn) else/當(dāng)前擴(kuò)展節(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn) for(int i=E.s+1;i<n;i+) if(aE.xE.sE.xi!=NoEdge) /可行兒子節(jié)點(diǎn) Type cc = E.cc + aE.xE

12、.sE.xi; Type rcost = E.rcost - MinOutE.xE.s; Type b = cc + rcost;/下界 if(b<bestc | bestc = NoEdge) /子樹(shù)可能含有最優(yōu)解 /節(jié)點(diǎn)插入最小堆 MinHeapNode<Type> N; N.x = new intn;/保存結(jié)點(diǎn)信息 for(int j=0; j<n; j+) N.xj = E.xj; 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; /

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

14、bestc; 測(cè)試結(jié)果1. 使用的圖如下所示：2. 相應(yīng)的排列樹(shù)如下所示：3. 至個(gè)葉結(jié)點(diǎn)的路徑葉結(jié)點(diǎn)路徑長(zhǎng)度路徑順序L591 ->2 ->3 ->4->1M661 ->2 ->4 ->3->1N251 ->3 ->2 ->4->1O661 ->3 ->4->2->1P251 ->4 ->2 ->3->1Q591 ->4 ->3 ->2->14. 由上表可以知道最短的為至葉結(jié)點(diǎn)Q的路徑1 ->3 ->2 ->4->1，長(zhǎng)度為25

15、。這里可能會(huì)有疑問(wèn)，至結(jié)點(diǎn)P的距離也為25，為什么不選擇路徑1 ->4 ->2 ->3->1。這是因?yàn)橹挥挟?dāng)求得的路徑比當(dāng)前最優(yōu)值小的時(shí)候才會(huì)記錄，這里一樣大，所以不會(huì)記錄，也就不會(huì)輸出這條路徑。5. 算法輸出結(jié)果如下：輸出圖的頂點(diǎn)個(gè)數(shù)。輸出最短路徑。輸出最短路徑的長(zhǎng)度。輸出時(shí)間。6. 可以看到輸出的結(jié)果與分析的結(jié)果一樣，所以算法實(shí)現(xiàn)正確。并且可以看到分支限界法在實(shí)現(xiàn)我們給的這個(gè)圖的時(shí)候，時(shí)間性能很好。實(shí)驗(yàn)心得說(shuō)實(shí)話，個(gè)人覺(jué)得旅行售貨員問(wèn)題的實(shí)現(xiàn)算法不好寫，因?yàn)槁眯惺圬泦T問(wèn)題的解空間是一棵排列樹(shù)，個(gè)人覺(jué)得排列樹(shù)較子集樹(shù)來(lái)說(shuō)，更加難以理解。這個(gè)算法的實(shí)現(xiàn)中，有一個(gè)地方卡了

16、很久，雖然可以通過(guò)嘗試數(shù)值的方法來(lái)確定到底是哪個(gè)，但是還是覺(jué)得自己理解了比較好，畢竟不是什么東西都可以挨個(gè)值試出來(lái)的，如果有一個(gè)問(wèn)題有很多可能的數(shù)值如果要試的話會(huì)很費(fèi)時(shí)間?？撕芫玫牡胤骄褪钱?dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn)的時(shí)候s（層數(shù)）的數(shù)值是什么。這個(gè)算法中是子集樹(shù)的第二層的時(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)1。像我剛剛說(shuō)的，如果不知道到底是哪個(gè)值的話，可以依次嘗試一下n、n-1和n-2這三個(gè)值，看為哪個(gè)

17、值的時(shí)候輸出正確的最短路徑。這里的這個(gè)代碼的編寫主要是用來(lái)與前面的回溯法進(jìn)行比較。回溯法主要是使用的深度優(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)比較少，所以兩個(gè)算法輸出的時(shí)間都為0，無(wú)法通過(guò)這一組測(cè)試數(shù)據(jù)給出兩種算法的時(shí)間比較分析。通過(guò)這次實(shí)驗(yàn)，編寫了分支限界法求旅行售貨員問(wèn)題，掌握了分支限界法求解問(wèn)題的基本步驟，掌握了旅行售貨員問(wèn)題的問(wèn)題描述，求解過(guò)程。相信在以后的學(xué)習(xí)工作中可以熟練使用分支限界法求解問(wèn)題，也可以使用多種方法求解旅行

18、售貨員問(wèn)題。實(shí)驗(yàn)得分助教簽名附錄：完整代碼#include "MinHeap.h" #include <iostream> #include<cstdlib>#include<time.h>#include<iomanip>#include<stdlib.h>#define NoEdge -1 using namespace std; /定義圖的頂點(diǎn)數(shù) const int N = 4; /*=定義Traveling類來(lái)存儲(chǔ)的信息。=*/ template<class Type> class Travel

19、ing public: Type BBTSP(int v); int n; /圖G的頂點(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)存儲(chǔ)最小堆中頂點(diǎn)的信息。* lcost表示子樹(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。 =*/ template<class Type> class MinHeapNode friend Trave

20、ling<Type> public: operator Type() const return lcost; private: Type lcost, /子樹(shù)費(fèi)用的下界 cc, /當(dāng)前費(fèi)用 rcost; /xs:n-1中頂點(diǎn)最小出邊費(fèi)用和 int s, /根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:s *x; /需要進(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è)

21、頂點(diǎn)的最小費(fèi)用出邊并用Minout記錄。如果所給的有向圖中某個(gè)頂點(diǎn)沒(méi)有出邊，則該圖不可能有回路,算法結(jié)束。如果每個(gè)頂點(diǎn)都有出邊，則根據(jù)計(jì)算出的Minout作算法初始化。算法第一個(gè)擴(kuò)展結(jié)點(diǎn)是排列樹(shù)中根結(jié)點(diǎn)唯一的兒子結(jié)點(diǎn)。在該結(jié)點(diǎn)處，已確定的回路中的唯一頂點(diǎn)為頂點(diǎn)1.初始時(shí)有s=0,x0=1,x1:n-1=(2,3,n),cc=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)

22、。 當(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)的下界lcost。當(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給出。 =*/ template<class Type> Type Traveling<Type>:BBTSP(int v) /定義有1000個(gè)結(jié)點(diǎn)

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

24、if(Min = NoEdge) return NoEdge; MinOuti = Min; MinSum += Min; /初始化 MinHeapNode<Type> E;/動(dòng)態(tài)內(nèi)存分配 E.x = new intn; /初始化 for(int i=0; i<n; i+) E.xi = i+1; E.s = 0; /根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑為x0:s E.cc = 0; /當(dāng)前費(fèi)用 E.rcost = MinSum;/最小出邊費(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)

25、是葉節(jié)點(diǎn)的父節(jié)點(diǎn) /再加2條邊構(gòu)成回路 /所構(gòu)成回路是否優(yōu)于當(dāng)前最優(yōu)解 if(aE.xn-2E.xn-1!=NoEdge && aE.xn-11!=NoEdge && (E.cc+aE.xn-2E.xn-1+aE.xn-11<bestc | bestc = NoEdge) /費(fèi)用更小的回路/記錄最小費(fèi)用 bestc = E.cc + aE.xn-2E.xn-1+aE.xn-11; /記錄結(jié)點(diǎn)的信息 E.cc = bestc; E.lcost = bestc; E.s+;/將結(jié)點(diǎn)放入最小堆中 H.Insert(E); else delete E.x;/舍棄擴(kuò)

26、展節(jié)點(diǎn) else/當(dāng)前擴(kuò)展節(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn) for(int 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 - MinOutE.xE.s; Type b = cc + rcost;/下界 if(b<bestc | bestc = NoEdge) /子樹(shù)可能含有最優(yōu)解 /節(jié)點(diǎn)插入最小堆 MinHeapNode<Type> N; N.x = new intn;/保存結(jié)點(diǎn)信息 for(int j=0; j<n; j+)

27、 N.xj = E.xj; 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.Insert(N); delete E.x;/完成節(jié)點(diǎn)擴(kuò)展 /最小堆空了就結(jié)束 if(H.Size() = 0) break; H.DeleteMin(E);/取下一擴(kuò)展節(jié)點(diǎn) /如果最小費(fèi)用為NoEdge,則圖中無(wú)回路 if(bestc = NoEdge) return NoEdge;/無(wú)回路 /將最優(yōu)解復(fù)制到v1:n for(int i=0; i<n; i+

28、) vi+1 = E.xi; while(true)/釋放最小堆中所有節(jié)點(diǎn) delete E.x; if(H.Size() = 0) break; H.DeleteMin(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 main() cout<<"="<<endl;cout<<"=分支限界法求TSP問(wèn)題="<<endl;cout<<

29、"="<<endl; int bestxN+1;int bestlength; /輸出圖的頂點(diǎn)個(gè)數(shù) cout<<"圖的頂點(diǎn)個(gè)數(shù)為："<<N<<endl; /動(dòng)態(tài)內(nèi)存分配 int *a=new int*N+1; for(int i=0;i<=N;i+) ai=new intN+1;/初始化 for(int i=0;i<=N;i+)for(int j=0;j<N;j+) aij=NoEdge; a12=30;a13=6;a14=4; a21=30;a23=5;a24=10; a31=6;a32

30、=5;a34=20; a41=4;a42=10;a43=20; /定義Traveling類型的變量t Traveling<int> t; /給變量t賦初值 t.a = a; t.n = N; /開(kāi)始計(jì)時(shí) clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/調(diào)用函數(shù) bestlength=t.BBTSP(bestx); /結(jié)束計(jì)時(shí) end=clock();/輸出最短回路 cout<<"最短回路為："<<endl; for(int i=1

31、;i<=N;i+) cout<<bestxi<<"->" cout<<bestx1<<endl; /輸出最短回路長(zhǎng)度 cout<<"最短回路的長(zhǎng)為："<<bestlength<<endl;/輸出時(shí)間 printf("The time is %6.3fn",(double)(end-start-over)/CLK_TCK); /釋放動(dòng)態(tài)分配的內(nèi)存 for(int i=0;i<=N;i+) delete ai; delete a; a=0; return 0; 最小堆得實(shí)現(xiàn)：#include <iostream> using namespace std; template<class Type> class Graph; /*= 定義MinHeap類來(lái)表示最小堆的信息。=*/ template<class T> class MinHeapprivat