分支限界法求旅行售貨員問題_物聯(lián)1301班_劉悅_201308080112_第1頁
分支限界法求旅行售貨員問題_物聯(lián)1301班_劉悅_201308080112_第2頁
分支限界法求旅行售貨員問題_物聯(lián)1301班_劉悅_201308080112_第3頁
分支限界法求旅行售貨員問題_物聯(lián)1301班_劉悅_201308080112_第4頁
分支限界法求旅行售貨員問題_物聯(lián)1301班_劉悅_201308080112_第5頁
已閱讀5頁,還剩11頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

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

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

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

4、個葉結點的父結點。如果該葉結點相應的一條可行回路且費用小于當前最小費用,則將該葉結點插入到優(yōu)先隊列中,否則去掉該葉結點。 當sn-2時,算法依次產(chǎn)生當前擴展結點的所有兒子結點。關鍵代碼/定義圖的頂點數(shù) const int N = 4; /*=定義Traveling類來存儲的信息。=*/ template class Traveling public: Type BBTSP(int v); int n; /圖G的頂點數(shù) Type *a, /圖G的鄰接矩陣 / NoEdge, /圖G的無邊標識 cc, /當前費用 bestc; /當前最小費用 ; /*= 定義MinHeapNode類來存儲最小堆中

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

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

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

8、兒子結點插入到活結點優(yōu)先隊列中。 算法結束時返回找到的最小費用,相應的最優(yōu)解由數(shù)組v給出。 =*/ template Type Traveling:BBTSP(int v) /定義有1000個結點的最小堆 MinHeapMinHeapNode H(1000); /動態(tài)分配內(nèi)存 Type * MinOut = new Typen+1; /計算MinOuti = 頂點i的最小出邊費用 Type MinSum = 0; /最小出邊費用和 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; /如果某個頂點沒有出邊,則該圖不可能有回路,算法結束 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é)點到當前節(jié)點路徑為x0:s E.cc = 0; /當前費用 E.rcost = MinSum;/最小出邊費用和 Type bestc = NoEdge; /搜索排列空間樹 whi

10、le(E.sn-1)/非葉結點 if(E.s = n-2)/當前擴展節(jié)點是葉節(jié)點的父節(jié)點 /再加2條邊構成回路 /所構成回路是否優(yōu)于當前最優(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) /費用更小的回路/記錄最小費用 bestc = E.cc + aE.xn-2E.xn-1+aE.xn-11; /記錄結點的信息 E.cc = bestc; E.lcost = bestc; E.s+;/將結點放入最小堆中 H.Insert(E); else d

11、elete E.x;/舍棄擴展節(jié)點 else/當前擴展節(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;/保存結點信息 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; /將結點插入最小堆 H.Insert(N); delete E.x;/完成節(jié)點擴展 /最小堆空了就結束 if(H.Size() = 0) break; H.DeleteMin(E);/取下一擴展節(jié)點 /如果最小費用為NoEdge,則圖中無回路 if(bestc = NoEdge) return NoEdge;/無回路 /將最優(yōu)解復制到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. 由上表可以知道最短的為至葉結點Q的路徑1 -3 -2 -4-1,長度為25。這里可能會有疑問,至結點P的距離也為25,為什么不選擇路徑1 -4 -2 -3-1。這是因為只有當求得的路徑比當前最優(yōu)值小的時候才會記錄,這里一樣大,所以不會記錄,也就不會輸出這條路徑。5. 算法輸出結果如下:輸出圖的頂點個數(shù)。輸出最短路徑。輸出最短路徑的長度。輸出時間。6. 可以看到輸出的結果與分析的結果一樣,所以算法實現(xiàn)正確。并且可以看到分支限界法在實現(xiàn)我們給的這個圖的時候,時間性能

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

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

16、求旅行售貨員問題,掌握了分支限界法求解問題的基本步驟,掌握了旅行售貨員問題的問題描述,求解過程。相信在以后的學習工作中可以熟練使用分支限界法求解問題,也可以使用多種方法求解旅行售貨員問題。實驗得分助教簽名附錄:完整代碼#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的無邊標識 cc, /當前費用 bestc; /當前最小費用 ; /*= 定義MinHeapNode類來存儲最小堆中頂點的信息。* lcost表示子樹費用的下界。 cc表示當前費用。 rcost表示xs:n-1中頂點最小出邊費用和。 s表示根節(jié)點到當前節(jié)點的路徑為x0:s。 x表示需要進一步搜索的頂點是xs+1,n-1。 =*/ template class MinHeapNode friend Traveling; public: operator Type() const r

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

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

20、可行兒子結點是從剩余頂點xs+1:n-1中選取的頂點xi,且(xs,xi)是有向圖G的一條邊。對于當前擴展結點的每一個可行兒子結點,計算出其前綴(x0:s,xi)的費用cc和相應的下界lcost。當lcostbestc時,將這個可行兒子結點插入到活結點優(yōu)先隊列中。 算法結束時返回找到的最小費用,相應的最優(yōu)解由數(shù)組v給出。 =*/ template Type Traveling:BBTSP(int v) /定義有1000個結點的最小堆 MinHeapMinHeapNode H(1000); /動態(tài)分配內(nèi)存 Type * MinOut = new Typen+1; /計算MinOuti = 頂點i

21、的最小出邊費用 Type MinSum = 0; /最小出邊費用和 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; /如果某個頂點沒有出邊,則該圖不可能有回路,算法結束 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é)點到當前節(jié)點路徑為x0:s E.cc = 0; /當前費用 E.rcost = MinSum;/最小出邊費用和 Type bestc = NoEdge; /搜索排列空間樹 while(E.sn-1)/非葉結點 if(E.s = n-2)/當前擴展節(jié)點是葉節(jié)點的父節(jié)點 /再加2條邊構成回路 /所構成回路是否優(yōu)于當前最優(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) /費用更小的回路/記錄最小費

23、用 bestc = E.cc + aE.xn-2E.xn-1+aE.xn-11; /記錄結點的信息 E.cc = bestc; E.lcost = bestc; E.s+;/將結點放入最小堆中 H.Insert(E); else delete E.x;/舍棄擴展節(jié)點 else/當前擴展節(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;/保存結點信息 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; /將結點插入最小堆 H.Insert(N); delete E.x;/完成節(jié)點擴展 /最小堆空了就結束 if(H.Size() = 0) break; H.DeleteMin(E)

25、;/取下一擴展節(jié)點 /如果最小費用為NoEdge,則圖中無回路 if(bestc = NoEdge) return NoEdge;/無回路 /將最優(yōu)解復制到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);/取下一擴展節(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); /結束計時 end=clock();/輸出最短回路 cout最短回路為:endl; for(int i=1;i=N;i+) cou

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論