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

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

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

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

4、個葉結(jié)點的父結(jié)點。如果該葉結(jié)點相應(yīng)的一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用,則將該葉結(jié)點插入到優(yōu)先隊列中,否則去掉該葉結(jié)點。 當(dāng)sn-2時,算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點的所有兒子結(jié)點。關(guān)鍵代碼/定義圖的頂點數(shù) const int n = 4; /*=定義traveling類來存儲的信息。=*/ template class traveling public: type bbtsp(int v); int n; /圖g的頂點數(shù) type *a, /圖g的鄰接矩陣 / noedge, /圖g的無邊標(biāo)識 cc, /當(dāng)前費(fèi)用 bestc; /當(dāng)前最小費(fèi)用 ; /*= 定義minheapnode類來存儲最小堆中

5、頂點的信息。* lcost表示子樹費(fèi)用的下界。 cc表示當(dāng)前費(fèi)用。 rcost表示xs:n-1中頂點最小出邊費(fèi)用和。 s表示根節(jié)點到當(dāng)前節(jié)點的路徑為x0:s。 x表示需要進(jìn)一步搜索的頂點是xs+1,n-1。 =*/ template class minheapnode friend traveling; public: operator type() const return lcost; private: type lcost, /子樹費(fèi)用的下界 cc, /當(dāng)前費(fèi)用 rcost; /xs:n-1中頂點最小出邊費(fèi)用和 int s, /根節(jié)點到當(dāng)前節(jié)點的路徑為x0:s *x; /需要進(jìn)一步搜索的

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

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

8、兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。 算法結(jié)束時返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v給出。 =*/ template type traveling:bbtsp(int v) /定義有1000個結(jié)點的最小堆 minheapminheapnode h(1000); /動態(tài)分配內(nèi)存 type * minout = new typen+1; /計算minouti = 頂點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 & (a

9、ijmin|min=noedge) min = aij; /如果某個頂點沒有出邊,則該圖不可能有回路,算法結(jié)束 if(min = noedge) return noedge; minouti = min; minsum += min; /初始化 minheapnode e;/動態(tài)內(nèi)存分配 e.x = new intn; /初始化 for(int i=0; in; i+) e.xi = i+1; e.s = 0; /根節(jié)點到當(dāng)前節(jié)點路徑為x0:s e.cc = 0; /當(dāng)前費(fèi)用 e.rcost = minsum;/最小出邊費(fèi)用和 type bestc = noedge; /搜索排列空間樹 whi

10、le(e.sn-1)/非葉結(jié)點 if(e.s = n-2)/當(dāng)前擴(kuò)展節(jié)點是葉節(jié)點的父節(jié)點 /再加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-11bestc | bestc = noedge) /費(fèi)用更小的回路/記錄最小費(fèi)用 bestc = e.cc + ae.xn-2e.xn-1+ae.xn-11; /記錄結(jié)點的信息 e.cc = bestc; e.lcost = bestc; e.s+;/將結(jié)點放入最小堆中 h.insert(e); else d

11、elete e.x;/舍棄擴(kuò)展節(jié)點 else/當(dāng)前擴(kuò)展節(jié)點是葉節(jié)點的父節(jié)點 for(int i=e.s+1;in;i+) if(ae.xe.se.xi!=noedge) /可行兒子節(jié)點 type cc = e.cc + ae.xe.se.xi; type rcost = e.rcost - minoute.xe.s; type b = cc + rcost;/下界 if(bbestc | bestc = noedge) /子樹可能含有最優(yōu)解 /節(jié)點插入最小堆 minheapnode n; n.x = new intn;/保存結(jié)點信息 for(int j=0; jn; j+) n.xj = e.

12、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é)點插入最小堆 h.insert(n); delete e.x;/完成節(jié)點擴(kuò)展 /最小堆空了就結(jié)束 if(h.size() = 0) break; h.deletemin(e);/取下一擴(kuò)展節(jié)點 /如果最小費(fèi)用為noedge,則圖中無回路 if(bestc = noedge) return noedge;/無回路 /將最優(yōu)解復(fù)制到v1:n for(int i=0; i2 -3 -4-1m661 -2 -4

13、 -3-1n251 -3 -2 -4-1o661 -3 -4-2-1p251 -4 -2 -3-1q591 -4 -3 -2-14. 由上表可以知道最短的為至葉結(jié)點q的路徑1 -3 -2 -4-1，長度為25。這里可能會有疑問，至結(jié)點p的距離也為25，為什么不選擇路徑1 -4 -2 -3-1。這是因為只有當(dāng)求得的路徑比當(dāng)前最優(yōu)值小的時候才會記錄，這里一樣大，所以不會記錄，也就不會輸出這條路徑。5. 算法輸出結(jié)果如下：輸出圖的頂點個數(shù)。輸出最短路徑。輸出最短路徑的長度。輸出時間。6. 可以看到輸出的結(jié)果與分析的結(jié)果一樣，所以算法實現(xiàn)正確。并且可以看到分支限界法在實現(xiàn)我們給的這個圖的時候，時間性能

14、很好。實驗心得說實話，個人覺得旅行售貨員問題的實現(xiàn)算法不好寫，因為旅行售貨員問題的解空間是一棵排列樹，個人覺得排列樹較子集樹來說，更加難以理解。這個算法的實現(xiàn)中，有一個地方卡了很久，雖然可以通過嘗試數(shù)值的方法來確定到底是哪個，但是還是覺得自己理解了比較好，畢竟不是什么東西都可以挨個值試出來的，如果有一個問題有很多可能的數(shù)值如果要試的話會很費(fèi)時間?？撕芫玫牡胤骄褪钱?dāng)前擴(kuò)展結(jié)點是葉結(jié)點的父結(jié)點的時候s（層數(shù)）的數(shù)值是什么。這個算法中是子集樹的第二層的時候s為0。拿我們給的這個圖的例子來說，就是b那一層s=0。所以當(dāng)前擴(kuò)展結(jié)點是葉結(jié)點的父結(jié)點的時候s應(yīng)該等于n-2，而不是n-1。這里是因為算法的第

15、1個擴(kuò)展結(jié)點是排列樹中唯一兒子結(jié)點。在該結(jié)點處，已經(jīng)確定的回路中唯一頂點為頂點1。像我剛剛說的，如果不知道到底是哪個值的話，可以依次嘗試一下n、n-1和n-2這三個值，看為哪個值的時候輸出正確的最短路徑。這里的這個代碼的編寫主要是用來與前面的回溯法進(jìn)行比較?；厮莘ㄖ饕鞘褂玫纳疃葍?yōu)先的探索，就是從一個子結(jié)點向下擴(kuò)展，一直擴(kuò)展到葉子結(jié)點或者不能繼續(xù)向下擴(kuò)展。而這里的分支限界法是寬度優(yōu)先的擴(kuò)展策略，這里使用的是優(yōu)先隊列來實現(xiàn)的話，就是每次擴(kuò)展優(yōu)先級最小的結(jié)點。因為給定的這個圖的結(jié)點比較少，所以兩個算法輸出的時間都為0，無法通過這一組測試數(shù)據(jù)給出兩種算法的時間比較分析。通過這次實驗，編寫了分支限界法

16、求旅行售貨員問題，掌握了分支限界法求解問題的基本步驟，掌握了旅行售貨員問題的問題描述，求解過程。相信在以后的學(xué)習(xí)工作中可以熟練使用分支限界法求解問題，也可以使用多種方法求解旅行售貨員問題。實驗得分助教簽名附錄：完整代碼#include minheap.h #include #include#include#include#include#define noedge -1 using namespace std; /定義圖的頂點數(shù) const int n = 4; /*=定義traveling類來存儲的信息。=*/ template class traveling public: type bb

17、tsp(int v); int n; /圖g的頂點數(shù) type *a, /圖g的鄰接矩陣 / noedge, /圖g的無邊標(biāo)識 cc, /當(dāng)前費(fèi)用 bestc; /當(dāng)前最小費(fèi)用 ; /*= 定義minheapnode類來存儲最小堆中頂點的信息。* lcost表示子樹費(fèi)用的下界。 cc表示當(dāng)前費(fèi)用。 rcost表示xs:n-1中頂點最小出邊費(fèi)用和。 s表示根節(jié)點到當(dāng)前節(jié)點的路徑為x0:s。 x表示需要進(jìn)一步搜索的頂點是xs+1,n-1。 =*/ template class minheapnode friend traveling; public: operator type() const r

18、eturn lcost; private: type lcost, /子樹費(fèi)用的下界 cc, /當(dāng)前費(fèi)用 rcost; /xs:n-1中頂點最小出邊費(fèi)用和 int s, /根節(jié)點到當(dāng)前節(jié)點的路徑為x0:s *x; /需要進(jìn)一步搜索的頂點是xs+1,n-1; /*=bbtsp函數(shù)為使用優(yōu)先隊列求最小費(fèi)用。 這里是使用一個優(yōu)先隊列來存儲活結(jié)點。優(yōu)先隊列中的每個活結(jié)點都存儲從根到該活結(jié)點的相應(yīng)路徑。算法開始創(chuàng)建一個最小堆，表示活結(jié)點優(yōu)先隊列。堆中每個結(jié)點的lcost值是優(yōu)先隊列的優(yōu)先級。接著計算出圖中每個頂點的最小費(fèi)用出邊并用minout記錄。如果所給的有向圖中某個頂點沒有出邊，則該圖不可能有回路,

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

20、可行兒子結(jié)點是從剩余頂點xs+1:n-1中選取的頂點xi,且(xs,xi)是有向圖g的一條邊。對于當(dāng)前擴(kuò)展結(jié)點的每一個可行兒子結(jié)點,計算出其前綴(x0:s,xi)的費(fèi)用cc和相應(yīng)的下界lcost。當(dāng)lcostbestc時,將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。 算法結(jié)束時返回找到的最小費(fèi)用，相應(yīng)的最優(yōu)解由數(shù)組v給出。 =*/ template type traveling:bbtsp(int v) /定義有1000個結(jié)點的最小堆 minheapminheapnode h(1000); /動態(tài)分配內(nèi)存 type * minout = new typen+1; /計算minouti = 頂點i

21、的最小出邊費(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 & (aijmin|min=noedge) min = aij; /如果某個頂點沒有出邊,則該圖不可能有回路,算法結(jié)束 if(min = noedge) return noedge; minouti = min; minsum += min; /初始化 minheapnode e;/動態(tài)內(nèi)存分配 e.x = new intn; /初始化 for(int i=0; in; i

22、+) e.xi = i+1; e.s = 0; /根節(jié)點到當(dāng)前節(jié)點路徑為x0:s e.cc = 0; /當(dāng)前費(fèi)用 e.rcost = minsum;/最小出邊費(fèi)用和 type bestc = noedge; /搜索排列空間樹 while(e.sn-1)/非葉結(jié)點 if(e.s = n-2)/當(dāng)前擴(kuò)展節(jié)點是葉節(jié)點的父節(jié)點 /再加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-11bestc | bestc = noedge) /費(fèi)用更小的回路/記錄最小費(fèi)

23、用 bestc = e.cc + ae.xn-2e.xn-1+ae.xn-11; /記錄結(jié)點的信息 e.cc = bestc; e.lcost = bestc; e.s+;/將結(jié)點放入最小堆中 h.insert(e); else delete e.x;/舍棄擴(kuò)展節(jié)點 else/當(dāng)前擴(kuò)展節(jié)點是葉節(jié)點的父節(jié)點 for(int i=e.s+1;in;i+) if(ae.xe.se.xi!=noedge) /可行兒子節(jié)點 type cc = e.cc + ae.xe.se.xi; type rcost = e.rcost - minoute.xe.s; type b = cc + rcost;/下界

24、if(bbestc | bestc = noedge) /子樹可能含有最優(yōu)解 /節(jié)點插入最小堆 minheapnode n; n.x = new intn;/保存結(jié)點信息 for(int j=0; jn; 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; /將結(jié)點插入最小堆 h.insert(n); delete e.x;/完成節(jié)點擴(kuò)展 /最小堆空了就結(jié)束 if(h.size() = 0) break; h.deletemin(e)

25、;/取下一擴(kuò)展節(jié)點 /如果最小費(fèi)用為noedge,則圖中無回路 if(bestc = noedge) return noedge;/無回路 /將最優(yōu)解復(fù)制到v1:n for(int i=0; in; i+) vi+1 = e.xi; while(true)/釋放最小堆中所有節(jié)點 delete e.x; if(h.size() = 0) break; h.deletemin(e);/取下一擴(kuò)展節(jié)點 return bestc; /*=main函數(shù)是主函數(shù)。實現(xiàn)輸入輸出，調(diào)用之前的分支限界法函數(shù)bbtsp求得最優(yōu)值,并且通過數(shù)組v得到最優(yōu)解。輸出最短路徑和最短路徑的長度。 =*/ int main(

26、) cout=endl;cout=分支限界法求tsp問題=endl;cout=endl; int bestxn+1;int bestlength; /輸出圖的頂點個數(shù) cout圖的頂點個數(shù)為：nendl; /動態(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;jn;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; /定義traveling類型的變量t traveling t; /給變量t賦初值 t.a = a; t.n = n; /開始計時 clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/調(diào)用函數(shù) bestlength=t.bbtsp(bestx); /結(jié)束計時 end=clock();/輸出最短回路 cout最短回路為：endl; for(int i=1;i=n;i+) cou