TSP問題算法分析報告

1、算法第二次大作業(yè)TSP問題算法分析021251班王昱（02125029）一. 問題描述“TSP問題”常被稱為“旅行商問題”，是指一名推銷員要拜訪多個地點時，如 何找到在拜訪每個地點一次后再回到起點的最短路徑。TSP問題在本實驗中的具體化：從 A城市出發(fā)，到達(dá)每個城市并且一個城市只允 許訪問一次，最后又回到原來的城市，尋找一條最短距離的路徑。二. 算法描述2.1分支界限法算法思想分支限界法常以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點?；罱Y(jié)點 一旦成為擴(kuò)展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點 中，導(dǎo)致不可行解或?qū)?/p>

2、致非最優(yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點 被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述 結(jié)點擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時 為止。算法設(shè)計說明設(shè)求解最大化問題，解向量為 X=(x1,xn)，xi的取值范圍為Si，|Si|=ri 。在使用分支限界搜索問題的解空間樹時，先根據(jù)限界 函數(shù)估算目標(biāo)函數(shù)的界down, up，然后從根結(jié)點出發(fā)，擴(kuò)展根結(jié)點 的r1個孩子結(jié)點，從而構(gòu)成分量x1的r1種可能的取值方式。對這r1個孩子結(jié)點分別估算可能的目標(biāo)函數(shù)bound(x1)，其含義：以該結(jié)點為根的子樹所有可能的取值不大于bound(x1)，即：bound

3、(x1) >bound(x1,x2)bound(x1，,xn)若某孩子結(jié)點的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的下界，則將該孩子結(jié)點丟棄；否則，將該孩子結(jié)點保存在待處理結(jié)點表PT中。再取PT表中目標(biāo)函數(shù)極大值結(jié)點作為擴(kuò)展的根結(jié)點， 重復(fù)上述。 直到一個葉子結(jié)點時的可行解X=(x1,xn),及目標(biāo)函數(shù)值 bound(x1,xn)。2.2 A*算法算法思想對于某一已到達(dá)的現(xiàn)行狀態(tài)，如已到達(dá)圖中的n節(jié)點，它是否可能成為最 佳路徑上的一點的估價,應(yīng)由估價函數(shù)f(n)值來決定。假設(shè)g*(n)函數(shù)值表示從 起始節(jié)點s到任意一個節(jié)點n的一條最佳路徑上的實際耗散值。h*(n)函數(shù)值表 示從任意節(jié)點n到目標(biāo)節(jié)點ti的

4、最佳路徑的實際耗散值。其中ti是一個可能 的目標(biāo)節(jié)點。f*(n)函數(shù)值表示從起始s,通過某一指定的n到達(dá)目標(biāo)節(jié)點ti 的一條最佳路徑的實際耗散值，并有 f*( n)=g*( n)+h*( n)。假設(shè)f函數(shù)是對f*函數(shù)的一種估計，并有f(n)=g(n)+h(n)，其中g(shù)函數(shù) 是對g*的估計，h函數(shù)是對h*的一種估計。f( n)包括兩個部分，其中g(shù)(n) 表示到達(dá)n節(jié)點時，已付出代價的估計；而h(n)表示從n節(jié)點到達(dá)目標(biāo)節(jié)點ti 將要付出代價的估計。按f(n)=g*(n)+h*(n) 的值來排序ff表的節(jié)點，f值小者優(yōu)先。通常稱這種算法 為A算法。在A算法的基礎(chǔ)上，進(jìn)一步限制h(n)函數(shù)，使得搜索

5、圖中的每一個 節(jié)點n,能滿足h(n)<=h*(n)、稱h函數(shù)取h*的下界。這種算法叫A*算法。 對ff里的每一個節(jié)點做評估函數(shù)F分為兩部分G和H：假設(shè)從A城市走到X城市，又走到丫城市，所以G可表示為：G = A到X的距離+ X到丫的距離；未走的的城市數(shù)=(總城市數(shù)+1)-目前城市的層數(shù)。為什得加1，因為最后得走回初始城市，所以總路徑的城市數(shù)為總城市數(shù) +1。H =未走的城市數(shù)X目前的最小距離；F = G + H ;計算ff表里每個節(jié)點的F值，F(xiàn)值最小的節(jié)點作為活路徑，把它加到 bestpath 中。3.1分支界限法#in elude <stdio.h>#i nclude &l

6、t;malloc.h>#defi ne NoEdge 1000struct MinH eapNodeint Icost; /子樹費用的下界in t cc; /當(dāng)前費用in t rcost; /xs:n-1中頂點最小出邊費用和int s; /根節(jié)點到當(dāng)前節(jié)點的路徑為 x0:sint *x; /需要進(jìn)一步搜索的頂點是 xs+1: n-1struct MinH eapNode *n ext;；int n; / 圖G的頂點數(shù)int *a; / 圖G的鄰接矩陣/int NoEdge; / 圖G的無邊標(biāo)記in t cc; /當(dāng)前費用int bestc; /當(dāng)前最小費用MinHeapNode* hea

7、d = 0; /* 堆頭 */MinHeapNode* Iq = 0; /*堆第一個元素 */MinHeapNode* fq = 0; /*堆最后一個元素 */ int DeleteMi n(Mi nH eapNode*&E) Mi nH eapNode* tmp = NULL; tmp = fq;/ w = fq->weight ;E = fq;if(E = NULL)，定不能丟了鏈表頭*/return 0;head->n ext = fq->n ext; /*fq = fq->n ext;/ free(tmp);return 0; int In sert(M

8、i nH eapNode* hn)if(head-> next = NULL)head-> next = hn; /將元素放入鏈表中fq = lq = head-> next; /定要使元素放到鏈中elseMi nH eapNode *tmp = NULL;tmp = fq;if(tmp->cc > hn->cc)hn->n ext = tmp;head->n ext = hn;fq = head-> next; /*鏈表只有一個元素的情況 */elsefor(; tmp != NULL;)if(tmp-> next != NULL

9、&& tmp->cc > hn->cc)hn->n ext = tmp->n ext;tmp->n ext = hn;break;tmp = tmp->n ext;if(tmp = NULL)lq->n ext = hn;Iq = lq->n ext;return 0; int BBTSP(i nt v)解旅行售貨員問題的優(yōu)先隊列式分支限界法/*初始化最優(yōu)隊列的頭結(jié)點*/head = (Mi nH eapNode*)malloc(sizeof(Mi nH eapNode); head->cc = 0;head->

10、x = 0;head->lcost = 0;head-> next = NULL;head->rcost = 0;head->s = 0;int *MinOut = new intn + 1; /*定義定點i的最小出邊費用*/ 計算MinOuti=頂點i的最小出邊費用int Mi nSum = 0;/最小出邊費用總合for(i nt i = 1; i <= n; i+)int Min = NoEdge; /*定義當(dāng)前最小值*/for(i nt j = 1; j <= n; j+)if(aij != NoEdge && /*當(dāng)定點i,j之間存在

11、回路時*/(aij < Min | Min = NoEdge) /*當(dāng)頂點 i,j 之間的距離小于Mi n*/Min = aij; /*if(Min = NoEdge) return NoEdge;/Mi nOuti = Mi n;/pri ntf("%dn",Mi nOuti);/* Min Sum += Min;/ prin tf("%dn",Mi nSum); /* 更新當(dāng)前最小值*/無回路頂點i的最小出邊費用*/最小出邊費用的總和*/MinH eapNode *E = 0;E = (Mi nH eapNode*)malloc(sizeof(

12、Mi nH eapNode); E->x = new intn;/ E.x=new intn;for(i nt i = 0; i < n; i+)E->xi = i + 1;E->s = 0;E->cc = 0;E->rcost = Min Sum;E-> next = 0; /初始化當(dāng)前擴(kuò)展節(jié)點int bestc = NoEdge; /*記錄當(dāng)前最小值*/搜索排列空間樹while(E->s < n - 1)/ 非葉結(jié)點if(E->s = n - 2)/當(dāng)前擴(kuò)展結(jié)點是葉結(jié)點的父結(jié)點/*首先考慮s=n-2的情形，此時當(dāng)前擴(kuò)展結(jié)點是排列樹

13、中某個葉結(jié)點的父結(jié) 點。如果該葉結(jié)點相應(yīng)一條可行回路且費用小于當(dāng)前最小費用，則將該葉結(jié)點插入到優(yōu)先隊列中，否則舍去該葉結(jié)點*/if(aE->xn - 2E->x n - 1 != NoEdge && /*當(dāng)前要擴(kuò)展和葉節(jié)點有邊存在*/aE->xn - 11 != NoEdge && /*當(dāng)前頁節(jié)點有回路 */(E->cc+ aE->x n - 2E->x n-1 + aE->x n - 11< bestc/*該節(jié)點相應(yīng)費用小于最小費用*/| bestc = NoEdge)bestc= E->cc + aE-&

14、gt;xn - 2E->xn - 1 + aE->xn - 11;/*更新當(dāng)前最新費用*/E->cc = bestc;E->lcost = bestc;E->s+;E-> next = NULL;In sert(E); /*將該頁節(jié)點插入到優(yōu)先隊列中*/elsefree(E->x);/該頁節(jié)點不滿足條件舍棄擴(kuò)展結(jié)點else/*產(chǎn)生當(dāng)前擴(kuò)展結(jié)點的兒子結(jié)點當(dāng)s<n-2時，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點的所有兒子結(jié)點。由于當(dāng)前擴(kuò)展結(jié) 點所相應(yīng)的路徑是x0:s，其可行兒子結(jié)點是從剩余頂點xs+1: n-1中選取的頂點xi，且(xs ,xi)是所給有向圖G中的一

15、條邊。對于當(dāng)前擴(kuò)展結(jié)點的每一個可行兒子結(jié)點，計算出其前綴（xO：s, xi）的費用cc和相應(yīng)的下界Icost。當(dāng)Icostvbestc 時，將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。*/for(i nt i = E->s + 1; i v n; i+)if(aE->xE->sE->xi != NoEdge) /*當(dāng)前擴(kuò)展節(jié)點到其他節(jié)點有邊存在*/可行兒子結(jié)點int cc = E->cc + aE->xE->sE->xi; /*當(dāng)前節(jié)點路徑*/加上節(jié)點i后in t rcost = E->rcost - Mi nOutE->xE->

16、s; /*剩余節(jié)點的和*/int b = cc + rcost; /下界if(b < bestc | bestc = NoEdge)/子樹可能含最優(yōu)解，結(jié)點插入最小堆MinH eapNode * N;N = (Mi nH eapNode*)malloc(sizeof(Mi nH eapNode);N->x = new intn; for(i nt j = 0; j < n; j+)N->xj = E->xj; N->xE->s + 1 = E->xi; N->xi = E->xE->s + 1;/* N->cc = cc;

17、 /*N->s = E->s + 1; /* N->Icost = b; /*N->rcost = rcost;N-> next = NULL;In sert(N); /*中*/free(E->x);/完成結(jié)點擴(kuò)展添加當(dāng)前路徑*/更新當(dāng)前路徑距離*/更新當(dāng)前節(jié)點*/更新當(dāng)前下界*/將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列DeleteMi n( E);/ if(E = NULL) break; /取下一擴(kuò)展結(jié)點堆已空if(bestc = NoEdge)return NoEdge;/無回路for(i nt i = 0; i v n; i+)vi + 1 = E-&

18、gt;xi;/將最優(yōu)解復(fù)制到 v1:nwhile(true)/釋放最小堆中所有結(jié)點free(E->x);DeleteMi n(E); if(E = NULL) break; return bestc;int mai n()n = 0;int i = 0;/FILE *in, *out;/in = fope n("i nput.txt", "r");/out = fope n("output.txt", "w");if(in = NULL | out = NULL)/ printf("沒有輸入輸出文件

19、n");/ return 1;/fsca nf(i n, "%d", &n);n=5;a = (in t*)malloc(sizeof(i nt*) * (n + 1);for(i = 1; i <= n; i+)ai = (in t*)malloc(sizeof(i nt) * (n + 1);/ for(i = 1; i <= n; i+)/for(i nt j = 1; j <= n; j+)/fsca nf(i n, "%d", & aij);/aij=1;a11=0;a12=6;a13=1;a14=5

20、;a15=7;a21=6;a22=0;a23=6;a24=4;a25=3;a31=1;a32=6;a33=0;a34=8;a35=2;a41=5;a42=4;a43=8;a44=0;a45=5;a51=7;a52=3;a53=2;a5 4=5;a55=0;/ prev = (in t*)malloc(sizeof(i nt)* (n+1);int*v = (in t*)malloc(sizeof(i nt) * (n + 1);/ MaxLoadi ng(w , c , n); for(i = 1; i <= n; i+)vi = 0;bestc = BBTSP(v);prin tf(&

21、quot;n");printf("最優(yōu)路徑為");for(i = 1; i <= n; i+)fprin tf(stdout, "%ct", vi+64);fprin tf(stdout, "n");fprintf(stdout,"總路程為 n", bestc);return 0;3.2 A*算法#i nclude "stdio.h"const int max=9999;檢測改節(jié)點是否已經(jīng)加入bestpath中const int ax=50;int isbest(i nt i,i

22、 nt bestpath,i nt p)/ for(i nt k=1;k<=p;k+)if(i=bestpathk)break;if(k!=p+1)新測試節(jié)點在a中return 1;elsereturn 0;void mai n()int mi n=ma x;int min f=max;int num;/ 城市數(shù)量int mataxax;城市間距離int bestpathax; 最佳路徑int f=O,g=O,h=O;int ffax;/依次求每個城市的f值int ggax;/城市的 g 值printf("城市個數(shù)為：");scan f("%d",

23、&n um);printf(”城市間的距離為：n ”);/輸入各城市間距離的矩陣for(i nt i=0;i <nu m;i+)for(i nt j=O;j< nu m;j+)scan f("%d",&matij);bestpathO=O;起點為0，即城市Afor(i ntp=0;p< num-1;p+)依次求每個最優(yōu)節(jié)點，每次循環(huán)得到一個新的最優(yōu)城市放到 bestpath中for(i nt kk=0;kk< nu m;kk+) ffkk=ma x;/ for(i=1;i <nu m;i+) if(isbest(i,bestpath,p)/ con ti nue;else/計算該點的g值 ggi=g+matbestpathpi;/i便于后面求最小值起點A不算，從非起點開始找尋最優(yōu)城市該點已經(jīng)在bestpath中的話，忽略點的g值for(i nt m=0;m<num ;m+)開始計算h值if(is