《问题算法分析》由会员分享，可在线阅读，更多相关《问题算法分析（24页珍藏版）》请在金锄头文库上搜索。
1、问题算法分析算法第二次大作业TSP问题算法分析021251班王昱（02125029）一问题描述“TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。二算法描述2.1 分支界限法2.1.1算法思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行
2、解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。问题算法分析此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.1.2算法设计说明设求解最大化问题，解向量为X=(x1, ,xn) ， xi 的取值范围为 Si ，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界down,up ，然后从根结点出发，扩展根结点的r1 个孩子结点，从而构成分量x1 的r1 种可能的取值方式。对这 r1 个孩子结点分别估算可能的目标函数bound(x1) ，其含义：以该结点为根的子树所有可能的取值
3、不大于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 的一条最
4、佳路径上的实际耗散值。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)的值来排序
5、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值最小的节点作为活路径，把它加
6、到bestpath 中。问题算法分析三算法代码3.1 分支界限法#include#include#defineNoEdge1000structMinHeapNodeintlcost;/子树费用的下界intcc;/当前费用intrcost;/xs:n-1中顶点最小出边费用和ints;/根节点到当前节点的路径为x0:sint*x;/需要进一步搜索的顶点是/xs+1:n-1structMinHeapNode*next;intn;/图 G的顶点数int*a;/图 G的邻接矩阵问题算法分析/intNoEdge;/图 G的无边标记intcc;/当前费用intbestc;/当前最小费用MinHeapNode
7、*head=0;/* 堆头 */MinHeapNode*lq=0;/*堆第一个元素 */MinHeapNode*fq=0;/* 堆最后一个元素 */intDeleteMin(MinHeapNode*&E)MinHeapNode*tmp=NULL;tmp=fq;/w=fq-weight;E=fq;if(E=NULL)return0;head-next=fq-next;/*一定不能丢了链表头*/fq=fq-next;问题算法分析/free(tmp);return0;intInsert(MinHeapNode*hn)if(head-next=NULL) head-next=hn;/将元素放入链表中f
8、q=lq=head-next;/一定要使元素放到链中elseMinHeapNode*tmp=NULL;tmp=fq;if(tmp-cchn-cc)hn-next=tmp;问题算法分析head-next=hn;fq=head-next;/*链表只有一个元素的情况*/elsefor(;tmp!=NULL;)if(tmp-next!=NULL&tmp-cchn-cc)hn-next=tmp-next;tmp-next=hn;break;tmp=tmp-next;if(tmp=NULL)问题算法分析lq-next=hn;lq=lq-next;return0;intBBTSP(intv)/ 解旅行售货员
9、问题的优先队列式分支限界法/* 初始化最优队列的头结点*/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=newintn+1;/*定义定点 i 的最小出边费用 */ 计算 MinOuti=顶点 i 的最小出边费用intMinSum=0;/最小出边费用总合for(inti=1;i=n;i+)intMin=NoEdge;/*定义当前最小值 */for(intj=1;j=n;j+)if(
10、aij!=NoEdge&/*当定点 i,j之间存在回路时 */(aijx=newintn;/E.x=newintn;for(inti=0;ixi=i+1;E-s=0;E-cc=0;E-rcost=MinSum;E-next=0;/初始化当前扩展节点intbestc=NoEdge;/*记录当前最小值 */ 搜索排列空间树while(E-ss=n-2)/ 当前扩展结点是叶结点的父结点/*首先考虑 s=n-2 的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点*/if(aE-xn-2E-xn-1!=
11、NoEdge&/*当前要扩展和叶节点有边存在*/aE-xn-11!=NoEdge&/*当前页节点有回路*/(E-cc+aE-xn-2E-xn-1+aE-xn-11cc+aE-xn-2E-xn-1+aE-xn-11;/*更新当前最新费用 */E-cc=bestc;E-lcost=bestc;问题算法分析E-s+;E-next=NULL;Insert(E);/*将该页节点插入到优先队列中*/elsefree(E-x);/该页节点不满足条件舍弃扩展结点else/* 产生当前扩展结点的儿子结点当 sn-2 时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是 x0:s，其可行儿子
12、结点是从剩余顶点xs+1:n-1中选取的顶点xi，且 (xs，xi)是所给有向图 G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用 cc和相应的下界lcost 。当 lcosts+1;ixE-sE-xi!=NoEdge)/* 当前扩展节点到其他节点有边存在*/问题算法分析/ 可行儿子结点intcc=E-cc+aE-xE-sE-xi;/*加上节点 i 后当前节点路径 */intrcost=E-rcost-MinOutE-xE-s;/*剩余节点的和 */intb=cc+rcost;/下界if(bx=newintn;for(intj=0;jxj=E-xj;N-
13、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)returnNoEdge;/无回路for(inti=0;ixi;/将最优解复制到v1:nwhile(true)问题算法
14、分析/ 释放最小堆中所有结点free(E-x);DeleteMin(E);if(E=NULL)break;returnbestc;intmain()n=0;inti=0;/FILE*in,*out;/in=fopen(input.txt,r);/out=fopen(output.txt,w);/if(in=NULL|out=NULL)问题算法分析/printf(没有输入输出文件n);/return1;/fscanf(in,%d,&n);n=5;a=(int*)malloc(sizeof(int*)*(n+1);for(i=1;i=n;i+)ai=(int*)malloc(sizeof(int)
15、*(n+1);/for(i=1;i=n;i+)/for(intj=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)*(
16、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);return0;3.2A* 算法#includestdio.hconstintmax=9999;constintax=50;intisbest(inti,intbestpath,intp)/检测改节点是否已经加入bestpath中for(intk=1;k=p;k+)if(i=bestpathk)break;问题算法分析if(k!=p+1)/新测试节点在a 中return1;elsereturn0;voidmain()intmin=max;intminf=max;intnum;/城市数量intmataxax;/城市间距离intbestpathax;/最佳路径intf=0,g=0,h=0;intffax;/依次求每个城市的f 值intgga
