旅行商售貨員問題的分支限界算法

1、旅行商售貨員問題的分支限界算法旅行商售貨員問題的分支限界算法姓名：姓名：學號：學號：一、實驗?zāi)康呐c要求一、實驗?zāi)康呐c要求1、掌握旅行商售貨員問題的分支限界算法；2、區(qū)分分支限界算法與回溯算法的區(qū)別，加深對分支限界法的理解。二、實驗題：二、實驗題：編程實現(xiàn)：某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費)最小。三、實驗提示三、實驗提示旅行商

2、問題的解空間是一個排列樹。有兩種實現(xiàn)的方法。第一種是只使用一個優(yōu)先隊列，隊列中的每個元素中都包含到達根的路徑。另一種是保留一個部分解空間樹和一個優(yōu)先隊列，優(yōu)先隊列中的元素并不包含到達根的路徑。以下為第一種方法。由于我們要尋找的是最小耗費的旅行路徑，因此可以使用最小耗費分枝定界法。在實現(xiàn)過程中，使用一個最小優(yōu)先隊列來記錄活節(jié)點，隊列中每個節(jié)點的類型為MinHeapNode。每個節(jié)點包括如下區(qū)域：x（從1到n的整數(shù)排列，其中x[0]=1），

3、s（一個整數(shù)，使得從排列樹的根節(jié)點到當前節(jié)點的路徑定義了旅行路徑的前綴x[0:s]而剩余待訪問的節(jié)點是x[s1:n1]），cc（旅行路徑前綴，即解空間樹中從根節(jié)點到當前節(jié)點的耗費），lcost（該節(jié)點子樹中任意葉節(jié)點中的最小耗費），rcost（從頂點x[s:n1]出發(fā)的所有邊的最小耗費之和）。當類型為MinHeapNode(T)的數(shù)據(jù)被轉(zhuǎn)換成為類型T時，其結(jié)果即為lcost的值。代碼：代碼：#include#includeusingna

4、mespacestd宏定義#defineMAX_CITY_NUMBER10城市最大數(shù)目#defineMAX_COST10000000兩個城市之間費用的最大值全局變量intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]表示城市間邊權(quán)重的數(shù)組intCity_Size表示實際輸入的城市數(shù)目intBest_Cost最小費用intBest_Cost_Path[MAX_CITY_NUMBER]最小費用時的路

5、徑定義結(jié)點typedefstructNodeintlcost優(yōu)先級intcc當前費用intrcost剩余所有結(jié)點的最小出邊費用的和prepNext=pinnode放在末尾出堆NodeRemoveMiniHeap(MiniHeappMiniHeap)Nodepnode=NULLif(pMiniHeappHeadpNext!=NULL)pnode=pMiniHeappHeadpNextpMiniHeappHeadpNext=pMiniHea

6、ppHeadpNextpNextreturnpnode分支限界法找最優(yōu)解voidTraveler()intijinttemp_x[MAX_CITY_NUMBER]NodepNode=NULLintminiSum所有結(jié)點最小出邊的費用和intminiOut[MAX_CITY_NUMBER]保存每個結(jié)點的最小出邊的索引MiniHeapheap=newMiniHeap分配堆InitMiniHeap(heap)初始化堆miniSum=0f(i=