旅行商售貨員問題的回溯法設(shè)計與實現(xiàn)

1、旅行商售貨員問題的回溯法的設(shè)計與實現(xiàn)班級學(xué)號姓名成績分一、 設(shè)計目的1） 理解旅行商售貨員問題的問題模型；2） 理解回溯法解決問題的基本思路；3） 掌握旅行商售貨員問題的回溯算法；4） 掌握集合的全排列問題的遞歸算法。二、 設(shè)計內(nèi)容1 任務(wù)描述旅行商售貨員問題描述設(shè)計任務(wù)簡介設(shè)計求解旅行商售貨員問題的回溯法，即設(shè)計和實現(xiàn)旅行商售貨員問題解的表示方案、回溯法的剪枝函數(shù)(約束函數(shù)，限界函數(shù))，設(shè)計對算法或程序的測試方案并完成測試。旅行商售貨員解的表示方案:X 向量（含義），約束函數(shù)：限界函數(shù)：解題思路：2 主要數(shù)據(jù)類型與變量解旅行商售貨員問題的類：Traveling 類主要描述成員及含義（必要時，

2、可對數(shù)據(jù)類型和變量進一步解釋或說明，增加可讀性）3 算法或程序模塊(1) Traveling 實現(xiàn)void Traveling:BackTrack();/實施對排列樹的回溯搜索。獲得具有最小耗費的周游路線。實現(xiàn)方法(p166)：.(2) int TSP(int * a,int v,int n, int NoEdge)/將數(shù)據(jù)初始化入 Traveling 類的一個對象。數(shù)據(jù)預(yù)處理。調(diào)用 BackTrack(2)開始回溯搜索。(3) void Swap(int *a, int *b)/將變量 a 和變量b 的信息交換，用于構(gòu)造排列時。（必要時，可對算法或程序模塊進一步解釋或說明，增加可讀性）(4)

3、 程序的執(zhí)行流程圖（可選）(5) 改進：教材上的限界函數(shù)：cc+axi-1x jbestc即可以進入 x j子樹的限界是進入 x j子樹后的部分路徑的耗費必須小于當(dāng)前最優(yōu)路徑的耗費。改進措施：參考 6.7 分枝限界法中的限界函數(shù)構(gòu)造即可以進入 x j子樹的限界是進入 x j子樹后的耗費的下界必須小于當(dāng)前最優(yōu)路徑的耗費。int tcc = cc+axi-1xj;int trcost = rcost - MinOutxi-1; int b = tcc+trcost;bbestctcc：進入 x j子樹的部分路徑的耗費，為 x1:i-1 與 xi-1至 xj的耗費之和。trcost：初始值為所有頂點

4、的最小出邊和。這是旅行商售貨員問題耗費的下界。即旅行商售貨員問題的最優(yōu)周游路線耗費的下界，假設(shè)從每個頂點到下一個頂點都恰好走它出去的最小耗費的那條邊。當(dāng)已確定了部分路經(jīng)x1:i-1 ，xi-1至 xj后，trcost 為剩余還沒有到達的那些頂點的最小出邊和。三、 測試a) 方案描述測試方案、測試模塊、測試數(shù)據(jù)實例（文字?jǐn)?shù)據(jù)、圖或表等形式）注：給出一個測試用例。畫出其搜索樹，畫出剪枝示意圖，標(biāo)出結(jié)點擴展序號。給出最大效益值及解向量。int n=4;int a5=0,0,0,0,0;int b5=0,0,30,6,4;int c5=0,30,0,5,10;int d5=0,6,5,0,20;int e5=0,4,10,20,0;int *p5 =a,b,c,d,e;b) 結(jié)果結(jié)合測試數(shù)據(jù)實例描述測試過程和測試結(jié)果，最好給出表示測試過程和結(jié)果的抓圖，對測試結(jié)果進行分析并得出結(jié)論。結(jié)果：bestc=25bestx=1，3，2，4四、 總結(jié)與討論可針對本設(shè)計談體會、談改進、談設(shè)想等，展示你的概括、歸納和創(chuàng)新思維能力，看重的不是你的對與錯，而是鼓勵你的創(chuàng)新思維。附：程序模塊的源代碼幾點說明(此行及以下內(nèi)容不在報告中出現(xiàn)，請注意刪除)建議將算法功能模塊與測試模塊分離、存盤，以備今后調(diào)用；除基本版式外，各大項的小項僅供參考，你可根據(jù)設(shè)計的具體內(nèi)容靈活展現(xiàn)你的報告能力；撰寫報告時，注意序