算法报告-旅行商问题模板讲解

《算法设计与课程设计》题目：TSP问题多种算法策略班级：计算机技术14学号：姓名：指导老师：完成日期：成绩：旅行商问题的求解方法摘要旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。关键字：旅行商问题；动态规划法；贪心法；回溯法；深度优先搜索策略1引言旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法、回溯法和深度优先搜索策略。2正文2.1动态规划法2.1.1动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。2.1.2TSP问题的动态规划函数假设从顶点i出发，令'(,)diV表示从顶点i出发经过'V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，'VVi，于是，TSP问题的动态规划函数为：''(,)min(,)()(,)()ikkidiVcdkVkkVdkcki2.1.3算法分析（1）for(i=1;iN;i++)//初始化第0列d[i][0]=c[i][0];（2）for(j=1;jn-12-1;j++)for(i=1;in;i++)//依次进行第i次迭代if(子集V[j]中不包含i)对V[j]中的每个元素k，计算V[m]==V[j]-k;d[i][j]=min(c[i][k]+d[k][m]);（3）对V[n-12-1]中的每一个元素k，计算V[m]==V[n-12-1]-k;d[0][n-12-1]=min(c[0][k]+d[k][m]);（4）输出最短路径长度d[0][n-12-1];2.1.4时间复杂性T()(2)nnOn动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。2.2贪心法2.2.1贪心法的设计思想贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。2.2.2最近邻点策略求解TSP问题贪心法求解TSP问题的贪心策略是显然的，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。最近邻点策略：从任意城市出发，每次在没有到过的城市中选择距离已选择的城市中最近的一个，直到经过了所有的城市，最后回到出发城市。2.2.3算法分析1．P={};2．V=V-{u0};u=u0;//从顶点u0出发3．循环直到集合P中包含n-1条边3.1查找与顶点u邻接的最小代价边(u,v)并且v属于集合V；3.2P=P+{(u,v)};3.3V=V-{v};3.4u=v;//从顶点v出发继续求解2.2.4时间复杂性2()TOn但需注意，用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。2.3回溯法2.3.1回溯法的设计思想回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），In,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。2.3.2算法分析（回溯法+深度优先搜索策略）因为是采用回溯法来做，肯定是递归，然后还需要现场清理。要设置一个二维数组来标识矩阵内容，然后回溯还需要设计一个二维标记数组来剪枝，设定一个目标变量，初始为无穷大，后续如果有比目标变量值小的就更新。剪枝的条件就是如果走到当前节点的耗费值=目标变量，就直接不再往下面走，向上走。深度优先=递归递归基:如果到达叶子节点的上一个节点，那么就进行是否更新的判断递归步:如果没有到达叶子节点，就进行剪枝操作，判断能否进入下一个节点，如果能，更新最优值2.3.3关键实现（回溯法+深度优先搜索策略）1//递归基：如果已经遍历到叶子节点的上一层节点，i标识递归深度if(i==g_n){//判断累加和是否超过最大值,如果有0，应该排除;满足这个条件，才打印if((g_iArr[pArr[i-1]][pArr[i]]!=0)&&(g_iArr[pArr[g_n]][1]!=0)&&(g_iCurResult+g_iArr[pArr[i-1]][pArr[i]]+g_iArr[pArr[g_n]][1]g_iResult)){g_iResult=g_iCurResult+g_iArr[pArr[i-1]][pArr[i]]+g_iArr[pArr[g_n]][1];//用当前最优路径去更新最优路径，防止下一次没有for(intk=1;k=g_n;k++){g_iBestPath[k]=pArr[k];2//递归步:判断能否进入子树，需要尝试每一个节点else{//尝试不同的组合for(intj=i;j=g_n;j++){//判断能否进入子树:如果当前值+下一个连线值的和最优值，就进入,0要passif((g_iArr[pArr[i-1]][pArr[j]]!=0)&&(g_iCurResult+g_iArr[pArr[i-1]][pArr[j]]g_iResult))3//交换i与j,则i为当前可以尝试的范围//为完成后面k个元素的排列，逐一对数组第n-k~n个元素互换。数组第一个元素为1，生成后面n-1个元素的排列//数组第一个元素与第二个元素互换，第一个元素为2，第2个元素为1，生成后面的n-1个元素的排列...swap(&pArr[i],&pArr[j]);//更新当前累加值,是i-1与i的g_iCurResult+=g_iArr[pArr[i-1]][pArr[i]];//递归backTrace(i+1,pArr);//回溯，清空累加值；能够走到这里，说明上述结果不是最优解，需要向求解树上一层回退g_iCurResult-=g_iArr[pArr[i-1]][pArr[i]];swap(&pArr[i],&pArr[j]);*/2.3.4时间复杂性T=O(n!),该方法并没有有效的提高时间效率。3结论本文主要重点讨论了动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP问题算法，并附录给出了相应程序，并通过对比得到动态规划法和贪心法相对更有优势，下面对这两种方法进行详述和进一步对比。3.1动态规划法思想动态规划法中对于顶点元素生成的子集本文中用字符串形式存储，然后再用递归方法按照子集中元素个数从小到大开始赋值。因为后面元素个数较多的子集与前面比其元素个数少1的子集间有一定对应关系，所以用递归方式，可以简便很多。个人觉得这算本文的一大特色。另，在计算d[i][j]=min(c[i][k]+d[k][j-1])时，获得d[k][j-1]的过程比较困难，运用字符串后，我们就可以首先找到指定字符，然后去掉该字符，返回剩余字符串，在与V[]逐个比较，找到与其相等的V[]中元素对应下标，此下标即为j-1；具体求解过程可参考附录源程序，有详细说明。在求解最佳路径所经过城市顺序时，本文是通过边查找d[i][j]边记录路径的，这样可以省掉很多麻烦，另，路径也是采用字符串形式的数组，数组规模与存储城市间距离的c[][]数组相同，由于很多元素均不需赋值，这样做可能会浪费内存空间，但是目前还没找到更好地求解方法。3.2贪心法思想贪心法中，由于贪心法相对动态规划法要简单很多，每次在查找最近城市时所得的顶点均为最后该法最佳路径所经过的城市编号，规模相对较小，容易确定，操作相对简单，所以本文用数组V[]存放最佳路径所经过的城市编号顺序相对来说方便很多。另外，本文用path[]整型数组存放所经路径的长度，最后相加即可得最短路径。3.3两者比较动态规划法相对贪心法来说虽然要精确些，但代码相对繁杂很多，对时间和空间要求很多，仅适用于城市数量较小的情况。贪心法虽然比较简单，实现起来比较容易，但不是很精确，当图中顶点个数较多并且各边的代价值分布比较均匀时，贪心法可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。另外，动态规划法有一个明显的缺点，就是出发城市只能是第0个城市（城市从0开始编号），若出发城市改变，则必须以该城市为第0个城市顺序给其他城市编号，输入城市间距离。由于若出发城市任意，编码的难度大大增加，所以最后不得已放弃，但这大大地限制了程序的通用性。而对于贪心法，本文很好地避免了这个问题，一旦城市编号确定，可以从任意城市出发，这也是本文中贪心法优于动态规划法的一点。3.4优点本文程序优点，各个子函数功能分隔很明显，没有大量集中在一个函数里面，而是分成了几个不同功能的小函数，这样程序可阅读性提高。另外，程序中有详细注释，程序中变量取名都是根据变量的性质和所代表的含义命名的，也相应提高了程序的可读性。对于动态规划法，城市个数可以在算法时间允许的范围内任意，于这点来说，通用性较好；对于贪心法，出发城市可以任意，城市个数也可以任意，通用性较好。3.5建议当城市个数较少时，用动态规划法求出最优解；当城市个数较多并且各边的代价值分布比较均匀时，贪心法可以给出较好的近似解。4参考文献（1）《计算机算法分析与设计》第二版，王晓东编著，电子工业出版社（2）Java语言与面向对象程序设计（第2版）印旻、王行言编著，清华大学出版社（3）求解TSP算法，周康、强小利、同小军、许进，计算机工程与应用（4）《算法设计与分析》，王红梅编著，清华大学出版社（5）《ACM/ICPC算法训练教程》，余立功主编，清华大学出版社6附录6.1动态规划法6.1.1源代码packageTsp;importjava.util.Scanner;publicclassTSPDP{String[]V;//顶点生成的子集，这里把每一个子集用一个字符串表示int[][]c;//顶点间距离int[][]d;//存放迭代结果intN;//城市个数String[][]path;//用于存放每种选择下经过的城市staticintIFINITE=99999;//无穷大距离表示城市自己到达自己时，距离无穷大，不作为考虑因素//构造函