TSP问题算法分析

1、TSP问题算法分析集团企业公司编码：LL3698? KKI1265TI2483 ? LUI12689? ITT289-算法第二次大作业TSP 问题算法分析021251班 王昱(02125029) 一 . 问题描述“ TSP问题常被称为“旅行商问题，是指一名推销员要拜访多个地点 时，如何找到在拜访每个地点一次后再回到起点的最短路径。TSP问题在本实验中的具体化：从 A城市出发，到达每个城市并且一个城 市 只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路 径。 二 . 算法描述2.1 分支界限法2.1.1 算法思想分支限界法常以广度优先或以最小消耗 (最大效益 )优先的方式搜 索问 题的

2、解空间树。 在分支限界法中，每一个活结点只有一次时机成为扩展结点。活结点一 旦 成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被参加 活结点 表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结 点 扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.1.2 算法设计说明设求解最大化问题，解向量为X二(xl,xn), xi的取值范围为Si,|Si|=rio 在使用分支限界搜索问题的解空间树时，先根据限界函数估算 目标 函数的界 down, up, 然后从根结点出发，扩展根结点的辺个孩子 结点，从 而

3、构成分量门的 rl 种可能的取值方式。 对这门个孩子结点分别估算可能的目标函数 bound(xl), 其含义：以该 结点为根的子树所有可能的取值不大于 bound(xl), 即：bound(xl) Abound(xl, x2) 2Abound(xl,，xn)假设某孩子结点的目标函数值超出目标函数的下界，那么将该孩子结点丢弃；否那么，将该孩子结点保存在待处理结点表PT中。再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解X= (xl,，xn),及目标函数值bound (xl, ， xn) 。2. 2A* 算法 算法思想对于某一已到达的现行状态，如己到达图中的 n

4、 节点 , 它是否可能成 为最正确路径上的一点的估价，应由估价函数 f(n) 值来决定。假设 g*(n) 函 数 值表示从起始节点 s 到任意一个节点 n 的一条最正确路径上的实际耗散 值。 h*(n) 函数值表示从任意节点 n 到目标节点 ti 的最正确路径的实际耗 散值。其 中 ti 是一个可能的目标节点。 f*(n) 函数值表示从起始 s, 通过 某一指定的 n 到达目标节点 ti 的一条最正确路径的实际耗散值，并有f* (n)=g* (n) +h* (n)假设 f 函数是对 f* 函数的一种估计，并有f(n)=g(n)+h(n), 其中 g 函数 是对辭的估计， h 函数是对 h* 的

5、一种估计。 f(n) 包括两个局部，其中g(n)表示到达n节点时，已付出代价的估计；而 h(n)表 示从 n 节点到达 目标节点 ti 将要付出代价的估计。按 f(n)=g*(n)+h*(n) 的值来排序 ff 表的节点 , f 值小者优先。通常称这 种算法为A算法。在A算法的根底上，进一步限制h(n)函数，使得搜索图中的每一个节点n,能满足h(n)<=h*(n)>称h函数取h*的下界。这种 算法叫A算法。对ff里的每一个节点做评估函数F分为两局部G和H:假设从A城市走到X城市，又走到Y城市，所以G可表示为：G=A到X的距离+X到丫的距离；未走的的城市数二 ( 总城市数 +1) -

6、目前城市的层数。为什得加 1, 因为最 后得走回初始城市，所以总路径的城市数为总城市数 +1。H 二未走的城市数 X 目前的最小距离；F 二 G+H;计算ff表里每个节点的F值，F值最小的节点作为活路径，把它加到bestpath 中。三 . 算法代码3.1 分支界限法tiinclude<stdio. h>#include<malloc ? h> ftdefineNoEdgelOOOstructMinHeapNode intlcost;/ 子树费用的下界intcc;/ 当前费用intrcost ;/xs: nlJ 中顶点最小出边费用和 ints;/ 根节点到当前节点的路径

7、为 x0:s int*x;/ 需要进一步搜索的顶点是 / xs+l:n-llstructMinHeapNode*next;；intn;/图G的顶点数/图G的邻接矩阵/intNoEdge;/图G的无边标记intcc;/ 当前费用intbestc; / 当前最小费用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)/ 解旅行售货员问题的优先队列式分支限界法/* 初始化最优队列的头结点 */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; /* 定义当前最小值 */for(intj=l;j<=n;j

11、+)if(aij! =NoEdge&&/* 当定点 i, j 之间存在回路时 */Min*/(aij<Min Min=NoEdge)/* 当顶点 i, j 之间的距离小于； /* 更新当前最小值 */辻 (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; / 初始化当前扩展节点intbestc=NoEdge; /* 记录当前最小值 */ 搜索排列空间树while(E>s<nl)/ 非叶结点if(E->s=n-2)/ 当前扩展结点是叶结点的父结点 /* 首先考虑 s=n-2 的情形，此时当前扩 展结点是排列树中某个叶结点的父结点。如果该叶结点相应

13、一条可行回路 且费用小于当前最小费用，那么将该叶结点插入到优先队列中，否那么舍去 该 叶结点*/if (aE->xn-2E->xn-l !=NoEdge&&/* 当前要扩展和叶节点有边存 在*/ aE->xn-lll !=NoEdge&&/* 当前页节点有回路 */ (E->cc+aE->xn-2E->xn-l+aE->xnT_l bestc/* 该节点相 应费用小于最小费用 */bestc 二二 NoEdge)bestc 二 E->cc+aE->xn-2 E->xn-l +aE->xnT 1 ;

14、/*更新当前最新费用 */E->cc=bestc:E->lcost=bestc:E- s+;E->next=NULL;Insert (E) ; /*将该页节点插入到优先队列中 */ elsefree (E->x) ;/ 该页节点不满足条件舍弃扩展结点 else/* 产生当前扩展结点的儿子结点 当 s n-2 时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩 展结点所相应的路径是 xO:s, 其可行儿子结点是从剩余顶点 xs+l:n-l 中选取的顶点 xi, 且(Xs, xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀 (xO:sl

15、, xil) 的 费用CC和相应的下界Icosto当 lcost<bestc 时，将这个可行儿子结点插入到活结点优先队列中。 */ for (inti 二 E->s+I;i<n;i+)if(aE->xE->sE->xi!二 NoEdge)/* 当前扩展节点到其他节点有边存在 */ 可行儿子结点intcc=E->cc+aE->xE->s E->xi ;/*加上节点 i 后当前节点路径 */intrcost=E->rcost-MinOut E - xE->s ;/* 剩余节点的和 */ intb=cc+rcost;/ 下界if

16、 (b<bestc bestc 二二 NoEdge)/ 子树可能含最优解，结点插入最小堆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;/* 添加当前路径 */N->cc=cc;/* 更新当前路径距离 */N->s=E->s+l;/* 更新当前节点 */N->lcost=b;/* 更新当

17、前下界 */N->rcost 二 rcost;N->next 二 NULL;Insert (N);/* 将这个可行儿子结点插入到活结点优先队列中 */free (E>x);/ 完成结点扩展DeleteMin(E) ;/ 取下一扩展结点辻 (E 二二 NULL)break;/ 堆已空if(bestc 二二 NoEdge)returnNoEdge; / 无 |H! 路for(inti=0;i<n;i+)vi+l=E->xi ;/ 将最优解复制到 vl:n while(true)/ 释放最小堆中所有结点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 最优路径为 ) ；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)/ 检测改节点是否已经参加 bestpath 中for (intk=l;k<=p;k+)if(i 二二 bestpathlk)break;辻 (k!=p+l)/ 新测试节点在 a 中returnl;elsereturnO; voidmain() intmin=max;intminf=max;i nt num; / 城市数量intmat axj ax ;/城市间距离intbestpath ax ;/最正确路径intf 二 0, g=0, h=0;intff

22、 ax ;/ 依次求每个城市的 f 值intggEax :/ 城市的 g 值printfC 城市个数为 : 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+) / 依次求每个最优节点，每次循环得到 一个新的最优城市放到 bestpath 中for (intkk=0;kk<num;kk+)ff kkj=max;/ 便于后面求最小值for (i=l; i<num; i+)/起点 A 不算，从非起点开始找寻最优城市中的话，忽略continue;else/ 计算该点的 &值ggi=g+mat b