TSP問題算法分析

1、TSP問題算法分析集團(tuán)企業(yè)公司編碼：LL3698? KKI1265TI2483 ? LUI12689? ITT289-算法第二次大作業(yè)TSP 問題算法分析021251班 王昱(02125029) 一 . 問題描述“ TSP問題常被稱為“旅行商問題，是指一名推銷員要拜訪多個地點 時，如何找到在拜訪每個地點一次后再回到起點的最短路徑。TSP問題在本實驗中的具體化：從 A城市出發(fā)，到達(dá)每個城市并且一個城 市 只允許訪問一次，最后又回到原來的城市，尋找一條最短距離的路 徑。 二 . 算法描述2.1 分支界限法2.1.1 算法思想分支限界法常以廣度優(yōu)先或以最小消耗 (最大效益 )優(yōu)先的方式搜 索問 題的

2、解空間樹。 在分支限界法中，每一個活結(jié)點只有一次時機(jī)成為擴(kuò)展結(jié)點?；罱Y(jié)點一 旦 成為擴(kuò)展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被參加 活結(jié)點 表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，并重復(fù)上述結(jié) 點 擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。2.1.2 算法設(shè)計說明設(shè)求解最大化問題，解向量為X二(xl,xn), xi的取值范圍為Si,|Si|=rio 在使用分支限界搜索問題的解空間樹時，先根據(jù)限界函數(shù)估算 目標(biāo) 函數(shù)的界 down, up, 然后從根結(jié)點出發(fā)，擴(kuò)展根結(jié)點的辺個孩子 結(jié)點，從 而

3、構(gòu)成分量門的 rl 種可能的取值方式。 對這門個孩子結(jié)點分別估算可能的目標(biāo)函數(shù) bound(xl), 其含義：以該 結(jié)點為根的子樹所有可能的取值不大于 bound(xl), 即：bound(xl) Abound(xl, x2) 2Abound(xl,，xn)假設(shè)某孩子結(jié)點的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的下界，那么將該孩子結(jié)點丟棄；否那么，將該孩子結(jié)點保存在待處理結(jié)點表PT中。再取PT表中目標(biāo)函數(shù)極大值結(jié)點作為擴(kuò)展的根結(jié)點，重復(fù)上述。直到一個葉子結(jié)點時的可行解X= (xl,，xn),及目標(biāo)函數(shù)值bound (xl, ， xn) 。2. 2A* 算法 算法思想對于某一已到達(dá)的現(xiàn)行狀態(tài)，如己到達(dá)圖中的 n

4、 節(jié)點 , 它是否可能成 為最正確路徑上的一點的估價，應(yīng)由估價函數(shù) f(n) 值來決定。假設(shè) g*(n) 函 數(shù) 值表示從起始節(jié)點 s 到任意一個節(jié)點 n 的一條最正確路徑上的實際耗散 值。 h*(n) 函數(shù)值表示從任意節(jié)點 n 到目標(biāo)節(jié)點 ti 的最正確路徑的實際耗 散值。其 中 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ù) 是對辭的估計， h 函數(shù)是對 h* 的

5、一種估計。 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算法的根底上，進(jìn)一步限制h(n)函數(shù)，使得搜索圖中的每一個節(jié)點n,能滿足h(n)<=h*(n)>稱h函數(shù)取h*的下界。這種 算法叫A算法。對ff里的每一個節(jié)點做評估函數(shù)F分為兩局部G和H:假設(shè)從A城市走到X城市，又走到Y(jié)城市，所以G可表示為：G=A到X的距離+X到丫的距離；未走的的城市數(shù)二 ( 總城市數(shù) +1) -

6、目前城市的層數(shù)。為什得加 1, 因為最 后得走回初始城市，所以總路徑的城市數(shù)為總城市數(shù) +1。H 二未走的城市數(shù) X 目前的最小距離；F 二 G+H;計算ff表里每個節(jié)點的F值，F(xiàn)值最小的節(jié)點作為活路徑，把它加到bestpath 中。三 . 算法代碼3.1 分支界限法tiinclude<stdio. h>#include<malloc ? h> ftdefineNoEdgelOOOstructMinHeapNode intlcost;/ 子樹費用的下界intcc;/ 當(dāng)前費用intrcost ;/xs: nlJ 中頂點最小出邊費用和 ints;/ 根節(jié)點到當(dāng)前節(jié)點的路徑

7、為 x0:s int*x;/ 需要進(jìn)一步搜索的頂點是 / xs+l:n-llstructMinHeapNode*next;；intn;/圖G的頂點數(shù)/圖G的鄰接矩陣/intNoEdge;/圖G的無邊標(biāo)記intcc;/ 當(dāng)前費用intbestc; / 當(dāng)前最小費用MinHeapNode*head=0; /* 堆頭 */ MinHeapNode*lq=0; /* 堆第一個元素 */ MinHeapNode*fq 二 0;/* 堆最后一個元素 */ intDeleteMin(MinHeapNode*&E) MinHeapNode*tmp=NULL;tmp=fq;/w=fq->weigh

8、t;E 二 fq ； if(E 二二 NULL) returnO; head->next 二 fq->next ;/* 一定不能丟 了鏈表頭 *， fq=fq->next; /free(tmp);next 二二 NULL) head - >next 二 hn;/returnO;intlnsert (MinHeapNode*hn) if(head-將元素放入鏈表中fq 二 lq 二 head- next; /定要使元素放到鏈中 elseMinHeapNode*tmp二 NULL;tmp=fq;if(tmp - cc>hn->cc) hn -next 二 tmp

9、;head- next 二 hn;fq=head->next;/* 鏈表只有一個元素的情況 */ elsefor(:tmp!=NULL;)if(tmp - next! 二 N U L L&&tm-p cc>hn->cc)二 hn;hn- next 二 tmp- next; tmp->next break;tmp 二 tmp->next;辻(tmp 二二 NULL)lq->next=hn;lq 二 lq->next;returnO;intBBTSP(intv)/ 解旅行售貨員問題的優(yōu)先隊列式分支限界法/* 初始化最優(yōu)隊列的頭結(jié)點 */he

10、ad 二 (MinHeapNode*)malloc(sizeof(MinHeapNode);head- cc=0;head->x=0;head->lcost 二 0;head->next 二 NULL;head- rcost 二 0;head- s 二 0;int*MinOut=newint n+1 ;/*定義定點 i 的最小出邊費用 */計算 MinOuti= 頂點 i 的最小出邊費用intMinSum 二 0;/ 最小出邊費用總合for(inti=l;i<=n;i+)intMin 二 NoEdge; /* 定義當(dāng)前最小值 */for(intj=l;j<=n;j

11、+)if(aij! =NoEdge&&/* 當(dāng)定點 i, j 之間存在回路時 */Min*/(aij<Min Min=NoEdge)/* 當(dāng)頂點 i, j 之間的距離小于； /* 更新當(dāng)前最小值 */辻 (Min 二二 NoEdge)returnNoEdge; / 無 |H! 路MinOuti 二 Min;/printf (，/ %dn， / , MinOut i) ;/*頂點 i 的最小出邊費用 */MinSum+=Min;/printf (， %dn， ? MinSum) ;/* 最小出邊費用的總和 */MinHeapNode*E=0;E=(MinHeapNode*)

12、malloc(sizeof(MinHeapNode);E>x=newintn ；/E. x=newintn;for(inti=0;i<n;i+)E->xi=i+l;E->s=0;E->cc=0;E>rcost=MinSum;E->next=0; / 初始化當(dāng)前擴(kuò)展節(jié)點intbestc=NoEdge; /* 記錄當(dāng)前最小值 */ 搜索排列空間樹while(E>s<nl)/ 非葉結(jié)點if(E->s=n-2)/ 當(dāng)前擴(kuò)展結(jié)點是葉結(jié)點的父結(jié)點 /* 首先考慮 s=n-2 的情形，此時當(dāng)前擴(kuò) 展結(jié)點是排列樹中某個葉結(jié)點的父結(jié)點。如果該葉結(jié)點相應(yīng)

13、一條可行回路 且費用小于當(dāng)前最小費用，那么將該葉結(jié)點插入到優(yōu)先隊列中，否那么舍去 該 葉結(jié)點*/if (aE->xn-2E->xn-l !=NoEdge&&/* 當(dāng)前要擴(kuò)展和葉節(jié)點有邊存 在*/ aE->xn-lll !=NoEdge&&/* 當(dāng)前頁節(jié)點有回路 */ (E->cc+aE->xn-2E->xn-l+aE->xnT_l bestc/* 該節(jié)點相 應(yīng)費用小于最小費用 */bestc 二二 NoEdge)bestc 二 E->cc+aE->xn-2 E->xn-l +aE->xnT 1 ;

14、/*更新當(dāng)前最新費用 */E->cc=bestc:E->lcost=bestc:E- s+;E->next=NULL;Insert (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)的路徑是 xO:s, 其可行兒子結(jié)點是從剩余頂點 xs+l:n-l 中選取的頂點 xi, 且(Xs, xi)是所給有向圖G中的一條邊。對于當(dāng)前擴(kuò)展結(jié)點的每一個可行兒子結(jié)點，計算出其前綴 (xO:sl

15、, xil) 的 費用CC和相應(yīng)的下界Icosto當(dāng) lcost<bestc 時，將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。 */ for (inti 二 E->s+I;i<n;i+)if(aE->xE->sE->xi!二 NoEdge)/* 當(dāng)前擴(kuò)展節(jié)點到其他節(jié)點有邊存在 */ 可行兒子結(jié)點intcc=E->cc+aE->xE->s E->xi ;/*加上節(jié)點 i 后當(dāng)前節(jié)點路徑 */intrcost=E->rcost-MinOut E - xE->s ;/* 剩余節(jié)點的和 */ intb=cc+rcost;/ 下界if

16、 (b<bestc bestc 二二 NoEdge)/ 子樹可能含最優(yōu)解，結(jié)點插入最小堆MinHeapNode*N;N=(MinHeapNode*)maIIoc(sizeof(MinHeapNode);N- x 二 newintn ； for(intj=0;j<n;j+)N->xj=E->xj;N->xE->s+I=E->xi;N->xi=E->xE->s+I;/* 添加當(dāng)前路徑 */N->cc=cc;/* 更新當(dāng)前路徑距離 */N->s=E->s+l;/* 更新當(dāng)前節(jié)點 */N->lcost=b;/* 更新當(dāng)

17、前下界 */N->rcost 二 rcost;N->next 二 NULL;Insert (N);/* 將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中 */free (E>x);/ 完成結(jié)點擴(kuò)展DeleteMin(E) ;/ 取下一擴(kuò)展結(jié)點辻 (E 二二 NULL)break;/ 堆已空if(bestc 二二 NoEdge)returnNoEdge; / 無 |H! 路for(inti=0;i<n;i+)vi+l=E->xi ;/ 將最優(yōu)解復(fù)制到 vl:n while(true)/ 釋放最小堆中所有結(jié)點free(E->x);DeleteMin(E);辻(E=NUL

18、L)break;returnbestc;intm ain ()n=0;inti 二 0;/FILE*in, *out;/in=fopen (z，input, txt", "r");,7out 二 fopen("output. txt", "w");/if(in 二二 NULL out=NULL)/printfC沒有輸入輸出文件n");/returnl;/fscanf (in, &n);n=5;a=(int*)malloc(sizeof(int*)*(n+1);for (i=l:i<=n;i+)ai=(

19、int*)malloc(sizeof(int)*(n+1);/for(i=l;i<=n;i+)/for(intj=l;j<=n;j+)/fscanf(in, "%d", &aiEj);/ai j=l;all二 0;al2二 6;al 二 1;al 4 二 5;al 二 7;a1二 6;a2 21=0;a 2 3二 6;a 2 4二 4;a2 51=3;a3l=l;a 3 2 二 6;3 3=0;a 3 41=8;a35=2;a41=5;a二4;a 4 31=8;a441=0;a45=5;a5 二 7;a 5 2 =3;a5 31=2;a54=5;a5 5

20、1=0;/prev=(int*)malloc(sizeof(int)* (n+1);int*v=(int*)malloc(sizeof(int)*(n+1):/MaxLoading(w, c, n);for(i=l;i<=n;i+)vi=0;bestc=BBTSP (v);printf ( n) ；printfC 最優(yōu)路徑為 ) ；for(i=l;i<=n;i+) fprintf(stdout, "n");fprintf (stdout, 總路程為 n , bestc);returnO;3. 2A* 算法#include"stdio. h"c

21、onst intmax=9999;constintax 二 50;intisbest (inti, intbestpath, intp)/ 檢測改節(jié)點是否已經(jīng)參加 bestpath 中for (intk=l;k<=p;k+)if(i 二二 bestpathlk)break;辻 (k!=p+l)/ 新測試節(jié)點在 a 中returnl;elsereturnO; voidmain() intmin=max;intminf=max;i nt num; / 城市數(shù)量intmat axj ax ;/城市間距離intbestpath ax ;/最正確路徑intf 二 0, g=0, h=0;intff

22、 ax ;/ 依次求每個城市的 f 值intggEax :/ 城市的 g 值printfC 城市個數(shù)為 : 9;scanf&num);printfC 城市間的距離為： n ) ；/ 輸入各城市間距離的矩陣 for (inti 二 0; i num; i+)for(intj=0;j<num;j+)scanf ， &matijj);bestpath01=0;/ 起點為 0, 即城市 Afor (intp 二 0; p<num-l; p+) / 依次求每個最優(yōu)節(jié)點，每次循環(huán)得到 一個新的最優(yōu)城市放到 bestpath 中for (intkk=0;kk<num;kk+)ff kkj=max;/ 便于后面求最小值for (i=l; i<num; i+)/起點 A 不算，從非起點開始找尋最優(yōu)城市中的話，忽略continue;else/ 計算該點的 &值ggi=g+mat b