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

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

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

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

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

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