回溯法求旅行售货员问题_物联1301班_刘悦_201308080112

算法分析与设计实验报告第X次实验姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309实验名称回溯法求旅行售货员问题实验目的通过上机实验，掌握回溯算法的思想，利用回溯法求旅行售货员问题并实现。实验原理旅行售货员问题的解空间树是一棵排列树。当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。当in时，当前扩展结点位于排列树的第i-1层。图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时算法进入排列树的第i层，否则将减去相应的子树。算法中用变量cc记录当前路径x[1:i]的费用。实验步骤①从起点开始，找其子结点，即存在一条边相连。②如果费用小于当前最优值则以此结点继续向下探索，否则就剪去相应的子树。③当扩展到叶结点的父结点时，检测此结点与叶结点，叶结点与起点是否有边相连。④若均有边相连，则检测此回路的费用是否小于最优费用。⑤若小于最优费用，则更新最优费用，同时记录最优解。关键代码//定义图的顶点数constintN=4;/*=================================================================定义Traveling类来存储的信息。=================================================================*/templateclassTypeclassTraveling{templateclassTfriendTTSP(T**a,intn);private:voidBacktrack(inti);intn,//图G的顶点数*x,//当前解*bestx;//当前最优解Type**a,//图G的领接矩阵cc,//当前费用bestc;//当前最优值intNoEdge;//无边标记};/*=================================================================Backtrack函数为递归算法。当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。当in时，当前扩展结点位于排列树的第i-1层。图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时算法进入排列树的第i层，否则将减去相应的子树。算法中用变量cc记录当前路径x[1:i]的费用。=================================================================*/templateclassTypevoidTravelingType::Backtrack(inti){//前扩展结点是排列树的叶结点的父结点if(i==n){//检测是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边//存在且这条回路的费用小于已找到的最优费用if(a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]bestc||bestc==0)){//记录最优解for(intj=1;j=n;j++)bestx[j]=x[j];//更新最优费用bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}//前扩展结点位于排列树的第i-1层else{for(intj=i;j=n;j++){//判断是否可进入x[j]子树if(a[x[i-1]][x[j]]!=0&&(cc+a[x[i-1]][x[i]]bestc||bestc==0)){//搜索子树//交换inttemp=x[i];x[i]=x[j];x[j]=temp;//当前费用累加cc+=a[x[i-1]][x[i]];//排列向右扩展,排列树向下一层扩展Backtrack(i+1);//当前费用减少cc-=a[x[i-1]][x[i]];//交换temp=x[i];x[i]=x[j];x[j]=temp;}}}}/*=================================================================TSP函数进行初始化，并返回最短路径的长度。主要为使用Backtrack函数进行搜索。=================================================================*/templateclassTypeTypeTSP(Type**a,intn){//定义traveling类型的变量YTravelingTypeY;//初始化YY.n=n;Y.x=newint[n+1];Y.bestx=newint[n+1];//置x为单位排列for(inti=1;i=n;i++){Y.x[i]=i;}Y.a=a;Y.cc=0;Y.bestc=0;Y.NoEdge=0;//搜索x[2:n]的全排列Y.Backtrack(2);//输出最短回路cout最短回路为：endl;for(inti=1;i=n;i++){coutY.bestx[i]--;}coutY.bestx[1]endl;//删除动态内存分配delete[]Y.x;Y.x=0;delete[]Y.bestx;Y.bestx=0;returnY.bestc;}/*=================================================================Swap函数实现两个数值交换。需要注意的是形参那里一定要使用&符号，不然的话修改之后的结果不会在其他函数中看到。=================================================================*/templateclassTypeinlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}测试结果1.使用的图如下所示：2.相应的排列树如下所示：3.至个叶结点的路径叶结点路径长度路径顺序L591--2--3--4--1M661--2--4--3--1N251--3--2--4--1O661--3--4--2--1P251--4--2--3--1Q591--4--3--2--14.由上表可以知道最短的为至叶结点Q的路径1--3--2--4--1，长度为25。这里可能会有疑问，至结点P的距离也为25，为什么不选择路径1--4--2--3--1。这是因为只有当求得的路径比当前最优值小的时候才会记录，这里一样大，所以不会记录，也就不会输出这条路径。5.算法输出结果如下：6.可以看到输出的结果与分析的结果一样，所以算法实现正确。并且可以看到分支限界法在实现我们给的这个图的时候，时间性能很好。实验心得因为我自己觉得解空间为排列树的问题的算法不是很好理解，所以就多编写了旅行售货员问题的代码，这里使用的是回溯法实现。就整体上来说，我认为回溯法的思想还是很好理解的，就是扩展一个结点的子结点，继续扩展子结点的子结点，当不能扩展的时候，就返回到上一个扩展结点，找其他的子结点进行扩展，当往回找到根结点，根结点没有子结点继续扩展的时候，就结束算法。但是这里是排列树的回溯法，就难理解一点。主要是使用了交换。voidbacktrack(intt){if(tn)output(x);elsefor(inti=t;i=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}排列树的实现的伪代码如上所示。主要存在两个交换。第一个交换是保存x[t]当前的状态，而后面一个交换则是回到x[t]刚才的状态。理解了这一点之后，回溯法求解旅行售货员问题的代码其实也就不难理解了。输入起点与终点，即源结点与目的结点。输出源结点到目的结点的最短路径。输出源结点到目的结点的最短路径的长度。输出时间。附录：完整代码#includeiostream#includecstdlib#includetime.h#includeiomanip#includestdlib.husingnamespacestd;//定义图的顶点数constintN=4;/*============================================================================定义Traveling类来存储的信息。============================================================================*/templateclassTypeclassTraveling{templateclassTfriendTTSP(T**a,intn);private:voidBacktrack(inti);intn,//图G的顶点数*x,//当前解*bestx;//当前最优解Type**a,//图G的领接矩阵cc,//当前费用bestc;//当前最优值intNoEdge;//无边标记};/*============================================================================Backtrack函数为递归算法。因为这里给的图的顶点比较少，无法直观的看出算法的时间性能。就回溯法求解旅行售货员问题，如果不考虑更新bestx所需的计算时间，则Backtrack需要O((n-1)!)计算时间。由于算法Backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需要O(n)计算时间，所以整个算法的计算时间复杂性为O(n!)。通过这次实验，编写了回溯法求解旅行售货员问题的代码，熟悉了回溯法求解问题的步骤，熟练掌握了回溯法，理解了排列树的问题，进一步熟悉了旅行售货员问题的问题描述与解题思路。相信在以后的学习工作中，一定可以熟练使用回溯法求解问题，当然肯定可以使用回溯法求解旅行售货员问题。实验得分助教签名当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。当in时，当前扩展结点位于排列树的第i-1层。图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时算法进入排列树的第i层，否则将减去相应的子树。算法中用变量cc记录当前路径x[1:i]的费用。============================================================================*/tem