《TSP问题算法分析报告.doc》由会员分享，可在线阅读，更多相关《TSP问题算法分析报告.doc（16页珍藏版）》请在三一文库上搜索。
1、算法第二次大作业TSP问题算法分析021251班王昱（02125029）一. 问题描述“TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如 何找到在拜访每个地点一次后再回到起点的最短路径。TSP问题在本实验中的具体化：从 A城市出发，到达每个城市并且一个城市只允 许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。二. 算法描述2.1分支界限法算法思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点 一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点 中，导致不可行解或导
2、致非最优解的儿子结点被舍弃，其余儿子结点 被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述 结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时 为止。算法设计说明设求解最大化问题，解向量为 X=(x1,xn)，xi的取值范围为Si，|Si|=ri 。在使用分支限界搜索问题的解空间树时，先根据限界 函数估算目标函数的界down, up，然后从根结点出发，扩展根结点 的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即：bound
3、(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的
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城市，又走到丫城市，所以G可表示为：G = A到X的距离+ X到丫的距离；未走的的城市数=(总城市数+1)-目前城市的层数。为什得加1，因为最后得走回初始城市，所以总路径的城市数为总城市数 +1。H =未走的城市数X目前的最小距离；F = G + H ;计算ff表里每个节点的F值，F值最小的节点作为活路径，把它加到 bestpath 中。3.1分支界限法#in elude <stdio.h>#i nclude &l
6、t;malloc.h>#defi ne NoEdge 1000struct MinH eapNodeint Icost; /子树费用的下界in t cc; /当前费用in t rcost; /xs:n-1中顶点最小出边费用和int s; /根节点到当前节点的路径为 x0:sint *x; /需要进一步搜索的顶点是 xs+1: n-1struct MinH eapNode *n ext;；int n; / 图G的顶点数int *a; / 图G的邻接矩阵/int NoEdge; / 图G的无边标记in t cc; /当前费用int bestc; /当前最小费用MinHeapNode* hea
7、d = 0; /* 堆头 */MinHeapNode* Iq = 0; /*堆第一个元素 */MinHeapNode* fq = 0; /*堆最后一个元素 */ int DeleteMi n(Mi nH eapNode*&E) Mi nH eapNode* tmp = NULL; tmp = fq;/ w = fq->weight ;E = fq;if(E = NULL)，定不能丢了链表头*/return 0;head->n ext = fq->n ext; /*fq = fq->n ext;/ free(tmp);return 0; int In sert(M
8、i nH eapNode* hn)if(head-> next = NULL)head-> next = hn; /将元素放入链表中fq = lq = head-> next; /定要使元素放到链中elseMi nH eapNode *tmp = NULL;tmp = fq;if(tmp->cc > hn->cc)hn->n ext = tmp;head->n ext = hn;fq = head-> next; /*链表只有一个元素的情况 */elsefor(; tmp != NULL;)if(tmp-> next != NULL
9、&& tmp->cc > hn->cc)hn->n ext = tmp->n ext;tmp->n ext = hn;break;tmp = tmp->n ext;if(tmp = NULL)lq->n ext = hn;Iq = lq->n ext;return 0; int BBTSP(i nt v)解旅行售货员问题的优先队列式分支限界法/*初始化最优队列的头结点*/head = (Mi nH eapNode*)malloc(sizeof(Mi nH eapNode); head->cc = 0;head->
10、x = 0;head->lcost = 0;head-> next = NULL;head->rcost = 0;head->s = 0;int *MinOut = new intn + 1; /*定义定点i的最小出边费用*/ 计算MinOuti=顶点i的最小出边费用int Mi nSum = 0;/最小出边费用总合for(i nt i = 1; i <= n; i+)int Min = NoEdge; /*定义当前最小值*/for(i nt j = 1; j <= n; j+)if(aij != NoEdge && /*当定点i,j之间存在
11、回路时*/(aij < Min | Min = NoEdge) /*当顶点 i,j 之间的距离小于Mi n*/Min = aij; /*if(Min = NoEdge) return NoEdge;/Mi nOuti = Mi n;/pri ntf("%dn",Mi nOuti);/* Min Sum += Min;/ prin tf("%dn",Mi nSum); /* 更新当前最小值*/无回路顶点i的最小出边费用*/最小出边费用的总和*/MinH eapNode *E = 0;E = (Mi nH eapNode*)malloc(sizeof(
12、Mi nH eapNode); E->x = new intn;/ E.x=new intn;for(i nt i = 0; i < n; i+)E->xi = i + 1;E->s = 0;E->cc = 0;E->rcost = Min Sum;E-> next = 0; /初始化当前扩展节点int bestc = NoEdge; /*记录当前最小值*/搜索排列空间树while(E->s < n - 1)/ 非叶结点if(E->s = n - 2)/当前扩展结点是叶结点的父结点/*首先考虑s=n-2的情形，此时当前扩展结点是排列树
13、中某个叶结点的父结 点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点*/if(aE->xn - 2E->x n - 1 != NoEdge && /*当前要扩展和叶节点有边存在*/aE->xn - 11 != NoEdge && /*当前页节点有回路 */(E->cc+ aE->x n - 2E->x n-1 + aE->x n - 11< bestc/*该节点相应费用小于最小费用*/| bestc = NoEdge)bestc= E->cc + aE-&
14、gt;xn - 2E->xn - 1 + aE->xn - 11;/*更新当前最新费用*/E->cc = bestc;E->lcost = bestc;E->s+;E-> next = NULL;In sert(E); /*将该页节点插入到优先队列中*/elsefree(E->x);/该页节点不满足条件舍弃扩展结点else/*产生当前扩展结点的儿子结点当s<n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结 点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1: n-1中选取的顶点xi，且(xs ,xi)是所给有向图G中的一
15、条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀（xO：s, xi）的费用cc和相应的下界Icost。当Icostvbestc 时，将这个可行儿子结点插入到活结点优先队列中。*/for(i nt i = E->s + 1; i v n; i+)if(aE->xE->sE->xi != NoEdge) /*当前扩展节点到其他节点有边存在*/可行儿子结点int cc = E->cc + aE->xE->sE->xi; /*当前节点路径*/加上节点i后in t rcost = E->rcost - Mi nOutE->xE->
16、s; /*剩余节点的和*/int b = cc + rcost; /下界if(b < bestc | bestc = NoEdge)/子树可能含最优解，结点插入最小堆MinH eapNode * N;N = (Mi nH eapNode*)malloc(sizeof(Mi nH eapNode);N->x = new intn; for(i nt j = 0; j < n; j+)N->xj = E->xj; N->xE->s + 1 = E->xi; N->xi = E->xE->s + 1;/* N->cc = cc;
17、 /*N->s = E->s + 1; /* N->Icost = b; /*N->rcost = rcost;N-> next = NULL;In sert(N); /*中*/free(E->x);/完成结点扩展添加当前路径*/更新当前路径距离*/更新当前节点*/更新当前下界*/将这个可行儿子结点插入到活结点优先队列DeleteMi n( E);/ if(E = NULL) break; /取下一扩展结点堆已空if(bestc = NoEdge)return NoEdge;/无回路for(i nt i = 0; i v n; i+)vi + 1 = E-&
18、gt;xi;/将最优解复制到 v1:nwhile(true)/释放最小堆中所有结点free(E->x);DeleteMi n(E); if(E = NULL) break; return bestc;int mai n()n = 0;int i = 0;/FILE *in, *out;/in = fope n("i nput.txt", "r");/out = fope n("output.txt", "w");if(in = NULL | out = NULL)/ printf("没有输入输出文件
19、n");/ return 1;/fsca nf(i n, "%d", &n);n=5;a = (in t*)malloc(sizeof(i nt*) * (n + 1);for(i = 1; i <= n; i+)ai = (in t*)malloc(sizeof(i nt) * (n + 1);/ for(i = 1; i <= n; i+)/for(i nt j = 1; j <= n; j+)/fsca nf(i n, "%d", & aij);/aij=1;a11=0;a12=6;a13=1;a14=5
20、;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;a5 4=5;a55=0;/ prev = (in t*)malloc(sizeof(i nt)* (n+1);int*v = (in t*)malloc(sizeof(i nt) * (n + 1);/ MaxLoadi ng(w , c , n); for(i = 1; i <= n; i+)vi = 0;bestc = BBTSP(v);prin tf(&
21、quot;n");printf("最优路径为");for(i = 1; i <= n; i+)fprin tf(stdout, "%ct", vi+64);fprin tf(stdout, "n");fprintf(stdout,"总路程为 n", bestc);return 0;3.2 A*算法#i nclude "stdio.h"const int max=9999;检测改节点是否已经加入bestpath中const int ax=50;int isbest(i nt i,i
22、 nt bestpath,i nt p)/ for(i nt k=1;k<=p;k+)if(i=bestpathk)break;if(k!=p+1)新测试节点在a中return 1;elsereturn 0;void mai n()int mi n=ma x;int min f=max;int num;/ 城市数量int mataxax;城市间距离int bestpathax; 最佳路径int f=O,g=O,h=O;int ffax;/依次求每个城市的f值int ggax;/城市的 g 值printf("城市个数为：");scan f("%d",
23、&n um);printf(”城市间的距离为：n ”);/输入各城市间距离的矩阵for(i nt i=0;i <nu m;i+)for(i nt j=O;j< nu m;j+)scan f("%d",&matij);bestpathO=O;起点为0，即城市Afor(i ntp=0;p< num-1;p+)依次求每个最优节点，每次循环得到一个新的最优城市放到 bestpath中for(i nt kk=0;kk< nu m;kk+) ffkk=ma x;/ for(i=1;i <nu m;i+) if(isbest(i,bestpa
24、th,p)/ con ti nue;else/计算该点的g值 ggi=g+matbestpathpi;/i便于后面求最小值起点A不算，从非起点开始找寻最优城市该点已经在bestpath中的话，忽略点的g值for(i nt m=0;m<num ;m+)开始计算h值if(isbest(m,bestpath,p)/该点已经在bestpath中的话，忽略con ti nue;for(i nt t=m+1;t <nu m;t+)if(isbest(t,bestpath,p)con ti nue;if(m!=O|t!=i|p=num-2)不是最后一个点的话，不算A点到这个点长度if(matmt
25、<mi n)mi n=matmt;h=min*(nu m-p-1);/h值ffi=ggi+h；第i个节点的f值min=max;/重新赋值最大，以便下次循环for(i=0;i<num;i+)找寻最优点，即 f值最小者if(ffi<mi nf)mi nf=ffi;bestpathp+1=i;minf=max;/重新赋值最大，以便下次循环g=g+matbestpathpbestpathp+1;更新 g 值printf("最优路径为:");for(i=0;i< nu m;i+)prin tf("%c ”,bestpathi+65);prin tf(
26、"An");printf("总路程为:");int sum=0;for(i=0;i< nu m-1;i+)sum=sum+matbestpathibestpathi+1;sum=sum+matbestpath nu m-10;总路程最后一个城市要回到A,所以加上其距离prin tf("%dn",sum);四.结果截图4.1分支界限法4.2 A*算法城市个数为5- 城帀间审距离为：Q 6 1 5 76 0 6 4 316 0 8 25 4 S 0 57 3 2 S 0最优路径为"C E B B fi 莒路程为江5Press an9 Jey to continiw