旅行商售貨員問(wèn)題的分支限界算法

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

2、問(wèn)題的解空間是一個(gè)排列樹(shù)。有兩種實(shí)現(xiàn)的方法。第一種是只使用一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)元素中都包含到達(dá)根的路徑。另一種是保留一個(gè)部分解空間樹(shù)和一個(gè)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列中的元素并不包含到達(dá)根的路徑。以下為第一種方法。由于我們要尋找的是最小耗費(fèi)的旅行路徑，因此可以使用最小耗費(fèi)分枝定界法。在實(shí)現(xiàn)過(guò)程中，使用一個(gè)最小優(yōu)先隊(duì)列來(lái)記錄活節(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ù)，使得從排列樹(shù)的根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑定義了旅行路徑的前綴x[0:s]而剩余待訪問(wèn)的節(jié)點(diǎn)是x[s1:n1]），cc（旅行路徑前綴，即解空間樹(shù)中從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗費(fèi)），lcost（該節(jié)點(diǎn)子樹(shù)中任意葉節(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)先級(jí)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=