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

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

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

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

5、圖中的每一個節點n，能滿足h(n)=h*(n)、稱h 函數取h* 的下界。這種算法叫A* 算法。對ff里的每一個節點做評估函數F分為兩部分G和H：假設從A城市走到X城市，又走到Y城市，所以G可表示為：G = A到X的距離 + X到Y的距離；未走的的城市數=（總城市數+1）-目前城市的層數。為什得加1，因為最后得走回初始城市，所以總路徑的城市數為總城市數+1。H = 未走的城市數目前的最小距離；F = G + H ;計算ff表里每個節點的F值，F值最小的節點作為活路徑，把它加到bestpath中。3 算法代碼3.1分支界限法#include #include #define NoEdge 100

6、0 struct MinHeapNode int lcost; /子樹費用的下界 int cc; /當前費用 int rcost; /xs:n-1中頂點最小出邊費用和 int s; /根節點到當前節點的路徑為x0:s int *x; /需要進一步搜索的頂點是/xs+1:n-1 struct MinHeapNode *next; ; int n; /圖G的頂點數 int *a; /圖G的鄰接矩陣 /int NoEdge; /圖G的無邊標記 int cc; /當前費用 int bestc; /當前最小費用 MinHeapNode* head = 0; /*堆頭*/ MinHeapNode* lq

7、= 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; int Insert(MinHeapNode* hn) if(head-next = NULL) head-next = hn;

8、 /將元素放入鏈表中 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-next != NULL & tmp-cc hn-cc) hn-next = tmp-next; tmp-next = hn; break; tmp = tmp-next; if(tmp = NULL) lq

9、-next = hn; lq = lq-next; return 0; int BBTSP(int v) /解旅行售貨員問題的優先隊列式分支限界法 /*初始化最優隊列的頭結點*/ head = (MinHeapNode*)malloc(sizeof(MinHeapNode); head-cc = 0; head-x = 0; head-lcost = 0; head-next = NULL; head-rcost = 0; head-s = 0; int *MinOut = new intn + 1; /*定義定點i的最小出邊費用*/ /計算MinOuti=頂點i的最小出邊費用 int Min

10、Sum = 0;/最小出邊費用總合 for(int i = 1; i = n; i+) int Min = NoEdge; /*定義當前最小值*/ for(int j = 1; j = n; j+) if(aij != NoEdge & /*當定點i,j之間存在回路時*/ (aij x = new intn; / E.x=new intn; for(int i = 0; i xi = i + 1; E-s = 0; E-cc = 0; E-rcost = MinSum; E-next = 0; /初始化當前擴展節點 int bestc = NoEdge; /*記錄當前最小值*/ /搜索排列空間

11、樹 while(E-s s = n - 2) /當前擴展結點是葉結點的父結點 /* 首先考慮s=n-2的情形，此時當前擴展結點是排列樹中某個葉結點的父結點。如果該葉結點相應一條可行回路 且費用小于當前最小費用，則將該葉結點插入到優先隊列中，否則舍去該葉結點 */ if(aE-xn - 2E-xn - 1 != NoEdge & /*當前要擴展和葉節點有邊存在*/ aE-xn - 11 != NoEdge & /*當前頁節點有回路*/ (E-cc + aE-xn - 2E-xn - 1 + aE-xn - 11 cc + aE-xn - 2E-xn - 1 + aE-xn - 11; /*更新當

12、前最新費用*/ E-cc = bestc; E-lcost = bestc; E-s+; E-next = NULL; Insert(E); /*將該頁節點插入到優先隊列中*/ else free(E-x);/該頁節點不滿足條件舍棄擴展結點 else /*產生當前擴展結點的兒子結點 當sn-2時，算法依次產生當前擴展結點的所有兒子結點。由于當前擴展結點所相應的路徑是x0:s， 其可行兒子結點是從剩余頂點xs+1:n-1中選取的頂點xi，且(xs，xi)是所給有向圖G中的一條邊。 對于當前擴展結點的每一個可行兒子結點，計算出其前綴(x0:s，xi)的費用cc和相應的下界lcost。 當lcost

13、s + 1; i xE-sE-xi != NoEdge) /*當前擴展節點到其他節點有邊存在*/ /可行兒子結點 int cc = E-cc + aE-xE-sE-xi; /*加上節點i后當前節點路徑*/ int rcost = E-rcost - MinOutE-xE-s; /*剩余節點的和*/ int b = cc + rcost; /下界 if(b x = new intn; for(int j = 0; j xj = E-xj; N-xE-s + 1 = E-xi; N-xi = E-xE-s + 1;/*添加當前路徑*/ N-cc = cc; /*更新當前路徑距離*/ N-s = E

14、-s + 1; /*更新當前節點*/ N-lcost = b; /*更新當前下界*/ N-rcost = rcost; N-next = NULL; Insert(N); /*將這個可行兒子結點插入到活結點優先隊列中*/ free(E-x); /完成結點擴展 DeleteMin(E);/取下一擴展結點 if(E = NULL) break; /堆已空 if(bestc = NoEdge) return NoEdge;/無回路 for(int i = 0; i xi;/將最優解復制到v1:n while(true) /釋放最小堆中所有結點 free(E-x); DeleteMin(E); if(

15、E = NULL) break; return bestc; int main() n = 0; int i = 0; /FILE *in, *out; /in = fopen(input.txt, r); /out = fopen(output.txt, 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*)ma

16、lloc(sizeof(int) * (n + 1); / for(i = 1; i = n; i+) / for(int j = 1; j = n; j+) / /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 = (i

17、nt*)malloc(sizeof(int)*(n+1) ; int*v = (int*)malloc(sizeof(int) * (n + 1);/ MaxLoading(w , c , n) ; for(i = 1; i = n; i+) vi = 0; bestc = BBTSP(v); printf(n); printf(最優路徑為); for(i = 1; i = n; i+) fprintf(stdout, %ct, vi+64); fprintf(stdout, n); fprintf(stdout, 總路程為n, bestc); return 0; 3.2 A*算法#inclu

18、de stdio.hconst int max=9999;const int ax=50;int isbest(int i,int bestpath,int p)/檢測改節點是否已經加入bestpath中 for(int k=1;k=p;k+)if(i=bestpathk)break;if(k!=p+1)/新測試節點在a中 return 1;elsereturn 0;void main() int min=max;int minf=max;int num;/城市數量int mataxax;/城市間距離int bestpathax;/最佳路徑int f=0,g=0,h=0;int ffax;/依

19、次求每個城市的f值int ggax;/城市的g值printf(城市個數為：);scanf(%d,&num);printf(城市間的距離為：n);/輸入各城市間距離的矩陣for(int i=0;inum;i+)for(int j=0;jnum;j+)scanf(%d,&matij); bestpath0=0;/起點為0，即城市Afor(int p=0;pnum-1;p+)/依次求每個最優節點，每次循環得到一個新的最優城市放到bestpath中for(int kk=0;kknum;kk+)ffkk=max;/便于后面求最小值for(i=1;inum;i+)/起點A不算，從非起點開始找尋最優城市if(isbest(i,bestpath,p)/該點已經在bestpath中的話，忽略continue;else/計算該點的