TSP問題算法分析報告

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

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

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

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

5、中的每一個節(jié)點(diǎn)n，能滿足h(n)<=h*(n)、稱h 函數(shù)取h* 的下界。這種算法叫A* 算法。對ff里的每一個節(jié)點(diǎn)做評估函數(shù)F分為兩部分G和H：假設(shè)從A城市走到X城市，又走到Y(jié)城市，所以G可表示為：G = A到X的距離 + X到Y(jié)的距離；未走的的城市數(shù)=（總城市數(shù)+1）-目前城市的層數(shù)。為什得加1，因?yàn)樽詈蟮米呋爻跏汲鞘?，所以總路徑的城市?shù)為總城市數(shù)+1。H = 未走的城市數(shù)×目前的最小距離；F = G + H ;計算ff表里每個節(jié)點(diǎn)的F值，F(xiàn)值最小的節(jié)點(diǎn)作為活路徑，把它加到bestpath中。3 算法代碼3.1分支界限法#include <stdio.h> #i

6、nclude <malloc.h> #define NoEdge 1000 struct MinHeapNode int lcost; /子樹費(fèi)用的下界 int cc; /當(dāng)前費(fèi)用 int rcost; /xs:n-1中頂點(diǎn)最小出邊費(fèi)用和 int s; /根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑為x0:s int *x; /需要進(jìn)一步搜索的頂點(diǎn)是/xs+1:n-1 struct MinHeapNode *next; ; int n; /圖G的頂點(diǎn)數(shù) int *a; /圖G的鄰接矩陣 /int NoEdge; /圖G的無邊標(biāo)記 int cc; /當(dāng)前費(fèi)用 int bestc; /當(dāng)前最小費(fèi)用 MinH

7、eapNode* head = 0; /*堆頭*/ MinHeapNode* lq = 0; /*堆第一個元素*/ MinHeapNode* fq = 0; /*堆最后一個元素*/ int DeleteMin(MinHeapNode*&E) MinHeapNode* tmp = NULL; tmp = fq; / w = fq->weight ; E = fq; if(E = NULL) return 0; head->next = fq->next; /*一定不能丟了鏈表頭*/ fq = fq->next; / free(tmp) ; return 0; in

8、t Insert(MinHeapNode* hn) if(head->next = NULL) head->next = hn; /將元素放入鏈表中 fq = lq = head->next; /一定要使元素放到鏈中 else MinHeapNode *tmp = NULL; tmp = fq; if(tmp->cc > hn->cc) hn->next = tmp; head->next = hn; fq = head->next; /*鏈表只有一個元素的情況*/ else for(; tmp != NULL;) if(tmp->n

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

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

11、mp;& /*當(dāng)定點(diǎn)i,j之間存在回路時*/ (aij < Min | Min = NoEdge) /*當(dāng)頂點(diǎn)i,j之間的距離小于Min*/ Min = aij; /*更新當(dāng)前最小值*/ if(Min = NoEdge) return NoEdge;/無回路 MinOuti = Min; /printf("%dn",MinOuti);/*頂點(diǎn)i的最小出邊費(fèi)用*/ MinSum += Min; / printf("%dn",MinSum); /*最小出邊費(fèi)用的總和*/ MinHeapNode *E = 0; E = (MinHeapNode*

12、)malloc(sizeof(MinHeapNode); E->x = new intn; / E.x=new intn; for(int i = 0; i < n; i+) E->xi = i + 1; E->s = 0; E->cc = 0; E->rcost = MinSum; E->next = 0; /初始化當(dāng)前擴(kuò)展節(jié)點(diǎn) int bestc = NoEdge; /*記錄當(dāng)前最小值*/ /搜索排列空間樹 while(E->s < n - 1) /非葉結(jié)點(diǎn) if(E->s = n - 2) /當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn) /*

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

14、 NoEdge) bestc = E->cc + aE->xn - 2E->xn - 1 + aE->xn - 11; /*更新當(dāng)前最新費(fèi)用*/ E->cc = bestc; E->lcost = bestc; E->s+; E->next = NULL; Insert(E); /*將該頁節(jié)點(diǎn)插入到優(yōu)先隊(duì)列中*/ else free(E->x);/該頁節(jié)點(diǎn)不滿足條件舍棄擴(kuò)展結(jié)點(diǎn) else /*產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的兒子結(jié)點(diǎn) 當(dāng)s<n-2時，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)。由于當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的路徑是x0:s， 其可行兒子結(jié)點(diǎn)是從

15、剩余頂點(diǎn)xs+1:n-1中選取的頂點(diǎn)xi，且(xs，xi)是所給有向圖G中的一條邊。 對于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個可行兒子結(jié)點(diǎn)，計算出其前綴(x0:s，xi)的費(fèi)用cc和相應(yīng)的下界lcost。 當(dāng)lcost<bestc時，將這個可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。*/ for(int i = E->s + 1; i < n; i+) if(aE->xE->sE->xi != NoEdge) /*當(dāng)前擴(kuò)展節(jié)點(diǎn)到其他節(jié)點(diǎn)有邊存在*/ /可行兒子結(jié)點(diǎn) int cc = E->cc + aE->xE->sE->xi; /*加上節(jié)點(diǎn)i后當(dāng)前節(jié)點(diǎn)路徑

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

17、; N->xi = E->xE->s + 1;/*添加當(dāng)前路徑*/ N->cc = cc; /*更新當(dāng)前路徑距離*/ N->s = E->s + 1; /*更新當(dāng)前節(jié)點(diǎn)*/ N->lcost = b; /*更新當(dāng)前下界*/ N->rcost = rcost; N->next = NULL; Insert(N); /*將這個可行兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中*/ free(E->x); /完成結(jié)點(diǎn)擴(kuò)展 DeleteMin(E);/取下一擴(kuò)展結(jié)點(diǎn) if(E = NULL) break; /堆已空 if(bestc = NoEdge) re

18、turn NoEdge;/無回路 for(int i = 0; i < n; i+) vi + 1 = E->xi;/將最優(yōu)解復(fù)制到v1:n while(true) /釋放最小堆中所有結(jié)點(diǎn) free(E->x); DeleteMin(E); if(E = NULL) break; return bestc; int main() n = 0; int i = 0; /FILE *in, *out; /in = fopen("input.txt", "r"); /out = fopen("output.txt", &q

19、uot;w"); /if(in = NULL | out = NULL) / / printf("沒有輸入輸出文件n"); / return 1; / /fscanf(in, "%d", &n); n=5; a = (int*)malloc(sizeof(int*) * (n + 1); for(i = 1; i <= n; i+) ai = (int*)malloc(sizeof(int) * (n + 1); / for(i = 1; i <= n; i+) / for(int j = 1; j <= n; j+)

20、 / /fscanf(in, "%d", &aij); / aij=1; a11=0; a12=6; a13=1; a14=5; 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; a54=5; a55=0; / prev = (int*)malloc(sizeof(int)*(n+1) ; int*v = (int*)malloc(sizeof(int)

21、 * (n + 1);/ MaxLoading(w , c , n) ; for(i = 1; i <= n; i+) vi = 0; bestc = BBTSP(v); printf("n"); printf("最優(yōu)路徑為"); for(i = 1; i <= n; i+) fprintf(stdout, "%ct", vi+64); fprintf(stdout, "n"); fprintf(stdout, "總路程為n", bestc); return 0; 3.2 A*算法#

22、include "stdio.h"const int max=9999;const int ax=50;int isbest(int i,int bestpath,int p)/檢測改節(jié)點(diǎn)是否已經(jīng)加入bestpath中 for(int k=1;k<=p;k+)if(i=bestpathk)break;if(k!=p+1)/新測試節(jié)點(diǎn)在a中 return 1;elsereturn 0;void main() int min=max;int minf=max;int num;/城市數(shù)量int mataxax;/城市間距離int bestpathax;/最佳路徑int f=

23、0,g=0,h=0;int ffax;/依次求每個城市的f值int ggax;/城市的g值printf("城市個數(shù)為：");scanf("%d",&num);printf("城市間的距離為：n");/輸入各城市間距離的矩陣for(int i=0;i<num;i+)for(int j=0;j<num;j+)scanf("%d",&matij); bestpath0=0;/起點(diǎn)為0，即城市Afor(int p=0;p<num-1;p+)/依次求每個最優(yōu)節(jié)點(diǎn)，每次循環(huán)得到一個新的最優(yōu)城市

24、放到bestpath中for(int kk=0;kk<num;kk+)ffkk=max;/便于后面求最小值for(i=1;i<num;i+)/起點(diǎn)A不算，從非起點(diǎn)開始找尋最優(yōu)城市if(isbest(i,bestpath,p)/該點(diǎn)已經(jīng)在bestpath中的話，忽略continue;else/計算該點(diǎn)的g值ggi=g+matbestpathpi;/i點(diǎn)的g值 for(int m=0;m<num;m+)/開始計算h值 if(isbest(m,bestpath,p)/該點(diǎn)已經(jīng)在bestpath中的話，忽略 continue;for(int t=m+1;t<num;t+)if(isbest(t,bestpath,p)continue;if(m!=0|t!=i|p=num-2)/不是最