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

1、旅行商售貨員問題的分支限界算法姓名： 學(xué)號(hào)：一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握旅行商售貨員問題的分支限界算法；2、區(qū)分分支限界算法與回溯算法的區(qū)別，加深對(duì)分支限界法的理解。二、實(shí)驗(yàn)題：編程實(shí)現(xiàn)：某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費(fèi))。他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一次，最后回到駐地的路線，使總的路程(或總旅費(fèi))最小。三、實(shí)驗(yàn)提示旅行商問題的解空間是一個(gè)排列樹。有兩種實(shí)現(xiàn)的方法。第一種是只使用一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)元素 中都包含到達(dá)根的路徑。另一種是保留一個(gè)部分解空間樹和一個(gè)優(yōu)先隊(duì)列，優(yōu)先隊(duì)列中 的元素并不包含到達(dá)根的路徑。以下為第一種方法。 由于我們要尋找的是最小耗費(fèi)

2、的旅行路徑，因此可以使用最小耗費(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ù)排列，其中x0 = 1 ），s（一個(gè)整數(shù)，使得從排列樹的根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑定義了旅行路徑的前綴x0:s, 而剩余待訪問的節(jié)點(diǎn)是x s + 1 : n - 1 ），cc（旅行路徑前綴，即解空間樹中從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗費(fèi)），lcost（該節(jié)點(diǎn)子樹中任意葉節(jié)點(diǎn)中的最小耗費(fèi)）， rcost（從頂點(diǎn)xs : n - 1出發(fā)的所有邊的最小耗費(fèi)之和）。當(dāng)類型為MinHeapNode( T )的數(shù)據(jù)被轉(zhuǎn)換成為類型T時(shí)，其結(jié)果即

3、為lcost的值。代碼：#include <stdio.h> #include <istream> using namespace std; /-宏定義- #define MAX_CITY_NUMBER 10 /城市最大數(shù)目 #define MAX_COST 10000000 /兩個(gè)城市之間費(fèi)用的最大值 /-全局變量- int City_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER; /表示城市間邊權(quán)重的數(shù)組 int City_Size; /表示實(shí)際輸入的城市數(shù)目 int Best_Cost; /最小費(fèi)用 int Best_Cost_PathM

4、AX_CITY_NUMBER; /最小費(fèi)用時(shí)的路徑 /-定義結(jié)點(diǎn)- typedef struct Node int lcost; /優(yōu)先級(jí) int cc; /當(dāng)前費(fèi)用 int rcost; /剩余所有結(jié)點(diǎn)的最小出邊費(fèi)用的和 int s; /當(dāng)前結(jié)點(diǎn)的深度，也就是它在解數(shù)組中的索引位置 int xMAX_CITY_NUMBER; /當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的路徑 struct Node* pNext; /指向下一個(gè)結(jié)點(diǎn) Node; /-定義堆和相關(guān)對(duì)操作- typedef struct MiniHeap Node* pHead; /堆的頭 MiniHeap; /初始化 void InitMiniHeap(M

5、iniHeap* pMiniHeap) pMiniHeap->pHead = new Node; pMiniHeap->pHead->pNext = NULL; /入堆 void put(MiniHeap* pMiniHeap,Node node) Node* next; Node* pre; Node* pinnode = new Node; /將傳進(jìn)來的結(jié)點(diǎn)信息copy一份保存 /這樣在函數(shù)外部對(duì)node的修改就不會(huì)影響到堆了 pinnode->cc = node.cc; pinnode->lcost = node.lcost; pinnode->pNe

6、xt = node.pNext; pinnode->rcost = node.rcost; pinnode->s = node.s; pinnode->pNext = NULL; for(int k=0;k<City_Size;k+) pinnode->xk = node.xk; pre = pMiniHeap->pHead; next = pMiniHeap->pHead->pNext; if(next = NULL) pMiniHeap->pHead->pNext = pinnode; else while(next != NUL

7、L) if(next->lcost) > (pinnode->lcost) /發(fā)現(xiàn)一個(gè)優(yōu)先級(jí)大的，則置于其前面 pinnode->pNext = pre->pNext; pre->pNext = pinnode; break; /跳出 pre = next; next = next->pNext; pre->pNext = pinnode; /放在末尾 /出堆 Node* RemoveMiniHeap(MiniHeap* pMiniHeap) Node* pnode = NULL; if(pMiniHeap->pHead->pNext

8、 != NULL) pnode = pMiniHeap->pHead->pNext; pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext; return pnode; /-分支限界法找最優(yōu)解- void Traveler() int i,j; int temp_xMAX_CITY_NUMBER; Node* pNode = NULL; int miniSum; /所有結(jié)點(diǎn)最小出邊的費(fèi)用和 int miniOutMAX_CITY_NUMBER; /保存每個(gè)結(jié)點(diǎn)的最小出邊的索引 MiniHeap

9、* heap = new MiniHeap; /分配堆 InitMiniHeap(heap); /初始化堆 miniSum = 0; for (i=0;i<City_Size;i+) miniOuti = MAX_COST; /初始化時(shí)每一個(gè)結(jié)點(diǎn)都不可達(dá) for(j=0;j<City_Size;j+) if (City_Graphij>0 && City_Graphij<miniOuti) /從i到j(luò)可達(dá)，且更小 miniOuti = City_Graphij; if (miniOuti = MAX_COST)/ i 城市沒有出邊 Best_Cost =

10、 -1; return ; miniSum += miniOuti; for(i=0;i<City_Size;i+) /初始化的最優(yōu)路徑就是把所有結(jié)點(diǎn)依次走一遍 Best_Cost_Pathi = i; Best_Cost = MAX_COST; /初始化的最優(yōu)費(fèi)用是一個(gè)很大的數(shù) pNode = new Node; /初始化第一個(gè)結(jié)點(diǎn)并入堆 pNode->lcost = 0; /當(dāng)前結(jié)點(diǎn)的優(yōu)先權(quán)為0 也就是最優(yōu) pNode->cc = 0; /當(dāng)前費(fèi)用為0（還沒有開始旅行） pNode->rcost = miniSum; /剩余所有結(jié)點(diǎn)的最小出邊費(fèi)用和就是初始化的min

11、iSum pNode->s = 0; /層次為0 pNode->pNext = NULL; for(int k=0;k<City_Size;k+) pNode->xk = Best_Cost_Pathk; /第一個(gè)結(jié)點(diǎn)所保存的路徑也就是初始化的路徑 put(heap,*pNode); /入堆 while(pNode != NULL && (pNode->s) < City_Size-1) /堆不空 不是葉子 for(int k=0;k<City_Size;k+) Best_Cost_Pathk = pNode->xk ; /將最優(yōu)

12、路徑置換為當(dāng)前結(jié)點(diǎn)本身所保存的 /* * * pNode 結(jié)點(diǎn)保存的路徑中的含有這條路徑上所有結(jié)點(diǎn)的索引 * * x路徑中保存的這一層結(jié)點(diǎn)的編號(hào)就是xCity_Size-2 * * 下一層結(jié)點(diǎn)的編號(hào)就是xCity_Size-1 */ if (pNode->s) = City_Size-2) /是葉子的父親 int edge1 = City_Graph(pNode->x)City_Size-2(pNode->x)City_Size-1; int edge2 = City_Graph(pNode->x)City_Size-1(pNode->x)0; if(edge1

13、>= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) < Best_Cost) /edge1 -1 表示不可達(dá) /葉子可達(dá)起點(diǎn)費(fèi)用更低 Best_Cost = pNode->cc + edge1+edge2; pNode->cc = Best_Cost; pNode->lcost = Best_Cost; /優(yōu)先權(quán)為 Best_Cost pNode->s+; /到達(dá)葉子層 else /內(nèi)部結(jié)點(diǎn) for (i=pNode->s;i<City_Size;i+) /從當(dāng)前

14、層到葉子層 if(City_GraphpNode->xpNode->spNode->xi >= 0) /可達(dá) /pNode的層數(shù)就是它在最優(yōu)路徑中的位置 int temp_cc = pNode->cc+City_GraphpNode->xpNode->spNode->xi; int temp_rcost = pNode->rcost-miniOutpNode->xpNode->s; /下一個(gè)結(jié)點(diǎn)的剩余最小出邊費(fèi)用和 /等于當(dāng)前結(jié)點(diǎn)的rcost減去當(dāng)前這個(gè)結(jié)點(diǎn)的最小出邊費(fèi)用 if (temp_cc+temp_rcost<Be

15、st_Cost) /下一個(gè)結(jié)點(diǎn)的最小出邊費(fèi)用和小于當(dāng)前的最優(yōu)解，說明可能存在更優(yōu)解 for (j=0;j<City_Size;j+) /完全copy路徑，以便下面修改 temp_xj=Best_Cost_Pathj; temp_xpNode->xpNode->s+1 = Best_Cost_Pathi; /將當(dāng)前結(jié)點(diǎn)的編號(hào)放入路徑的深度為s+1的地方 temp_xi = Best_Cost_PathpNode->s+1; /? /將原路/徑中的深度為s+1的結(jié)點(diǎn)編號(hào)放入當(dāng)前路徑的 /相當(dāng)于將原路徑中的的深度為i的結(jié)點(diǎn)與深度W為s+1的結(jié)點(diǎn)交換 Node* pNextNo

16、de = new Node; pNextNode->cc = temp_cc; pNextNode->lcost = temp_cc+temp_rcost; pNextNode->rcost = temp_rcost; pNextNode->s = pNode->s+1; pNextNode->pNext = NULL; for(int k=0;k<City_Size;k+) pNextNode->xk = temp_xk; put(heap,*pNextNode); delete pNextNode; pNode = RemoveMiniHea

17、p(heap); int main() int i,j;printf("請(qǐng)輸入旅行的節(jié)點(diǎn)數(shù)"); scanf("%d",&City_Size); for(i=0;i<City_Size;i+) printf("請(qǐng)分別輸入每個(gè)節(jié)點(diǎn)與其它節(jié)點(diǎn)的路程花費(fèi)"); for(j=0;j<City_Size;j+) scanf("%d",&City_Graphij); Traveler(); printf("最小花費(fèi)""%dn",Best_Cost); retu

18、rn 1; 運(yùn)行結(jié)果：分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出T中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。 由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法在解空間樹T上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹T。分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹