TSP问题算法分析.doc

算法第二次大作业TSP问题算法分析021251班王昱（02125029）1 问题描述“TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。2 算法描述2.1分支界限法2.1.1 算法思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.1.2 算法设计说明设求解最大化问题，解向量为X=(x1,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界down, up，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即：bound(x1)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 的最佳路径的实际耗散值。其中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)函数，使得搜索图中的每一个节点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 1000 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 = 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; /将元素放入链表中 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-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 MinSum = 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; /*记录当前最小值*/ /搜索排列空间树 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; /*更新当前最新费用*/ 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。 当lcosts + 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-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(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*)malloc(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 = (int*)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*算法#include 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;/依次求每个城市的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/计算该点的g值ggi=g+matbestpathpi;/i点的g值 for(int m=0;mnum;m+)/开始计算h值 if(isbest(m,bestpath,p)/该点已经在bestpath中的话，忽略 continue;for(int t=m+1;tnum;t+)if(isbest(t,bestpath,p)continue;if(m!=0|t!=i|p=num-2)/不是最后一个点的话，不算A点到这个点长度if(matmtmin)min=matmt; h=min*(num-p-1);/h值ffi=ggi+h;/第i个节点的f值min=max;/重新赋值最大，以便下次循环for(i=0;inum;i+)/找寻最优点，即f值最小者if(ffiminf)minf=ffi;bestpathp+1=i;minf=max;/重新赋值最大，以便下次循环g=g+matbestpathpbestpathp+1;/更新g值printf(最优路径为:); for(i=0;inum;i+) printf(%c ,bestpathi+65);printf(An);printf(总路程为:); int sum=0;for(i=0;inum-1;i+) sum=sum+matbestpathibestpathi+1;sum=sum+matbestpathnum-10;/总路程最后一个城市要回到A，所以加上其距离printf(%dn,sum);4 结果截图4.1分支界限法4.2 A*算法