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

精选优质文档-倾情为你奉上算法设计与课程设计题 目： TSP问题多种算法策略 班 级： 计算机技术14 学 号： 姓 名： 指导老师： 完成日期： 成 绩： 旅行商问题的求解方法摘要旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。关键字：旅行商问题；动态规划法；贪心法；回溯法；深度优先搜索策略1引言旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法、回溯法和深度优先搜索策略。2正文2.1动态规划法2.1.1动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。2.1.2 TSP问题的动态规划函数假设从顶点i出发，令表示从顶点i出发经过中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，于是，TSP问题的动态规划函数为： 2.1.3算法分析（1）for (i=1; i<N; i+) /初始化第0列 di0=ci0; （2）for (j=1; j< -1; j+) for (i=1; i<n; i+) /依次进行第i次迭代 if (子集Vj中不包含i) 对Vj中的每个元素k，计算Vm = Vj-k;dij=min(cik+dkm); （3）对V -1中的每一个元素k，计算Vm = V -1-k;d0 -1=min(c0k+dkm); （4）输出最短路径长度d0 -1;2.1.4时间复杂性动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。2.2贪心法2.2.1贪心法的设计思想贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。2.2.2最近邻点策略求解TSP问题贪心法求解TSP问题的贪心策略是显然的，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。最近邻点策略：从任意城市出发，每次在没有到过的城市中选择距离已选择的城市中最近的一个，直到经过了所有的城市，最后回到出发城市。2.2.3算法分析1P= ; 2V=V-u0; u=u0; /从顶点u0出发3循环直到集合P中包含n-1条边 3.1查找与顶点u邻接的最小代价边(u, v)并且v属于集合V； 3.2 P=P+(u, v); 3.3 V=V-v; 3.4 u=v; /从顶点v出发继续求解2.2.4时间复杂性但需注意，用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。2.3回溯法2.3.1回溯法的设计思想 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。若已有满足约束条件的部分解，不妨设为（x1,x2,x3,xi），I<n,则添加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_iArrpArri-1pArri != 0) && (g_iArrpArrg_n1 != 0) &&(g_iCurResult + g_iArrpArri-1pArri + g_iArrpArrg_n1 < g_iResult )g_iResult = g_iCurResult + g_iArrpArri-1pArri + g_iArrpArrg_n1;/用当前最优路径去更新最优路径，防止下一次没有for(int k = 1 ; k <= g_n ; k+)g_iBestPathk = pArrk;2 /递归步:判断能否进入子树，需要尝试每一个节点else/尝试不同的组合for(int j = i ; j <= g_n ; j+)/判断能否进入子树:如果当前值+下一个连线值的和 < 最优值，就进入,0要passif( (g_iArrpArri-1pArrj != 0) && (g_iCurResult + g_iArr pArri-1 pArrj < g_iResult) )3 /交换i与j,则i为当前可以尝试的范围/为完成后面k个元素的排列，逐一对数组第n-kn个元素互换。数组第一个元素为1，生成后面n-1个元素的排列/数组第一个元素与第二个元素互换，第一个元素为2，第2个元素为1，生成后面的n-1个元素的排列.swap(&pArri,&pArrj);/更新当前累加值,是i-1与i的g_iCurResult += g_iArr pArri-1 pArri ;/递归backTrace(i+1,pArr);/回溯，清空累加值；能够走到这里，说明上述结果不是最优解，需要向求解树上一层回退g_iCurResult -= g_iArrpArri-1 pArri ;swap(&pArri,&pArrj);*/2.3.4时间复杂性T = O(n!), 该方法并没有有效的提高时间效率。3结论本文主要重点讨论了动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP问题算法，并附录给出了相应程序，并通过对比得到动态规划法和贪心法相对更有优势，下面对这两种方法进行详述和进一步对比。3.1动态规划法思想动态规划法中对于顶点元素生成的子集本文中用字符串形式存储，然后再用递归方法按照子集中元素个数从小到大开始赋值。因为后面元素个数较多的子集与前面比其元素个数少1的子集间有一定对应关系，所以用递归方式，可以简便很多。个人觉得这算本文的一大特色。另，在计算dij =min(cik+dkj-1)时，获得dkj-1的过程比较困难，运用字符串后，我们就可以首先找到指定字符，然后去掉该字符，返回剩余字符串，在与V逐个比较，找到与其相等的V中元素对应下标，此下标即为j-1；具体求解过程可参考附录源程序，有详细说明。在求解最佳路径所经过城市顺序时，本文是通过边查找dij边记录路径的，这样可以省掉很多麻烦，另，路径也是采用字符串形式的数组，数组规模与存储城市间距离的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源代码package Tsp;import java.util.Scanner;public class TSPDP String V;/ 顶点生成的子集，这里把每一个子集用一个字符串表示int c;/ 顶点间距离int d;/ 存放迭代结果int N; / 城市个数String path;/ 用于存放每种选择下经过的城市static int IFINITE = 99999;/ 无穷大距离 表示城市自己到达自己时，距离无穷大，不作为考虑因素/ 构造函数public TSPDP() initialC();initialV1();/ 初始化数组c，即顶点间距离public void initialC() Scanner in = new Scanner(System.in);System.out.println("请输入城市个数： （注意根据实际情况城市个数不可小于1！）");N = in.nextInt();if (N <= 1) System.out.println("不符合要求，请认真核对！");System.exit(0);/ 输入错误，结束！System.out.println("请输入城市相邻城市间距离（城市从0开始编号，且出发城市为第0个城市！）： ");c = new intNN;/ 为c分配空间for (int i = 0; i < N; i+)for (int j = 0; j < N; j+) cij = in.nextInt(); / 输入时，按城市编号从小到大，如若两城市间没有公路相连，则距离为无穷大。本城市与本城市间距离也为无穷大。/ 初始化顶点生成的子集的对外调用函数public void initialV1() V = new String(int) Math.pow(2, N - 1);/ 为V分配空间initialV(0, 0);/ 具体的初始化顶点生成的子集/ 本程序使用递归调用方法初始化V，并按照数字大小顺序排序。另，子集使用字符型形式存放的/ 我们是按照子集中元素个数从小到大逐个添加的，后面的子集是前面对应子集加上一个元素组成的，故用递归public void initialV(int m, int len) / m代表下一个即将初始化的V数组的元素的下标；len是最后一个初始化的元素的长度if (m > (int) Math.pow(2, N - 1) - 1)return;/ 如果全部顶点已初始化完成，则返回。if (m = 0)Vm+ = ""/ 初始化出发顶点，即V0else int i = m - 1;while (i >= 0 && Vi.length() = len)/ 找与最后一个初始化的Vm-1子集内元素个数相同的集合，把指针i指向满足条件的集合i-;i+;/ 把指针i指向满足条件的第一个集合while (i < m) int ch;/ 用于表示下一个即将加入子集的数字if (i = 0)ch = 0;/ 如果i指向V中第一个元素else String chStr = "" + Vi.charAt(Vi.length() - 1);/ 找出Vi中最后一个数字ch = Integer.parseInt(chStr);/ 转换成整型/ 比ch大而又比N-1(因为这里顶点是从0开始的)小的数字应该加在子集中while (ch < N - 1)Vm+ = Vi + (+ch);i+;/ 对已存在的自己逐个扫描添加initialV(m, Vm - 1.length();/ 递归调用/ 判断自己Vj中是否存在指定元素，即行号iboolean exclude(int i, int j) String str = "" + i;/ 把i转换成字符串if (Vj.contains(str)/ System.out.println(i + "i");return false;/ 如若存在，则返回falseelsereturn true;/ 获得子集Vj中除指定元素k外的元素，用字符串形式表示public String getSubString(int k, int j) if (Vj.length() = 1)return ""/ 如果子集中只有一个元素，则返回空串else if (k = 0)return Vj.substring(1, Vj.length();/ 如果k是第一个元素，则返回其后面的元素else if (k = Vj.length() - 1)return Vj.substring(0, Vj.length() - 1);/ 如果k是最后一个元素，则返回其前面的元素elsereturn (Vj.substring(0, k) + Vj.substring(k + 1,Vj.length();/ 返回除k外的元素/ 找出V中与str相同元素的下标号,即找出上一个子集public int stringEqual(String str) / if(str.equals("")return 0;int i = 0;while (i < V.length) if (Vi.equals(str)return i;i+;return -1;/ 如若没找到，则返回错误符号-1/ 求最小距离public int min(int i, int j) int k = 0;/ 用于记录Vj中元素个数String vStr = "" + Vj.charAt(k);/ 铭记Vj.charAt(k)得到的是字符型，转换成整形后是字母对应的ASC码！int v = Integer.parseInt(vStr);/ 把位置k处的字符转换成整形String str = getSubString(k, j);/ 获得Vj中除位置k处外的字符串/ System.out.println("min" + str + stringEqual(str) + v);if (stringEqual(str) = -1)System.exit(0);int min = civ + dvstringEqual(str);/ 先把最小的距离赋值给从Vj中第一个顶点出发的距离/ System.out.println(min);/ /stringEqual(str)表示返回与上面获得的字符串相同的V中元素的下标，即找上一个子集pathij = pathvstringEqual(str) + i;k+;/ 寻找最小距离while (k < Vj.length() vStr = "" + Vj.charAt(k);v = Integer.parseInt(vStr);str = getSubString(k, j);if (min > civ + dvstringEqual(str) min = civ + dvstringEqual(str);pathij = pathvstringEqual(str) + i;k+;/ Vj.substring(beginIndex, endIndex)/ System.out.println(pathij);return min;/ 返回最小值/ 处理函数public void dynamic() d = new intN(int) Math.pow(2, N - 1);/ 分配空间path = new StringN(int) Math.pow(2, N - 1);for (int i = 1; i < N; i+) / 初始化第一列di0 = ci0;pathi0 = "0" + i;/ 初始化第一个元素，即为出发城市顶点/ System.out.print(di0 + " ");/ 初始化后面的元素int j = 1;for (; j < (int) Math.pow(2, N - 1) - 1; j+)for (int i = 1; i < N; i+) if (exclude(i, j)/ 判断V子集中是否包含当前顶点，即Vj中是否包含i/ System.out.println("done！" + i + " " + j);dij = min(i, j);/ 寻找最小距离d0j = min(0, j);/ 初始化组后一列/ 输出中间结果，各个数组，用于调试程序public void print() System.out.println("显示定点生成子集：");for (int i = 0; i < (int) Math.pow(2, N - 1); i+)System.out.print(Vi + " ");/ for(int i = 0 ; i < c.length ; )System.out.println();System.out.println("打印代价矩阵：");for (int i = 0; i < N; i+) for (int j = 0; j < N; j+)System.out.print(cij + " ");System.out.println();System.out.println("动态规划表填表结果：");for (int i = 0; i < N; i+) for (int j = 0; j < (int) Math.pow(2, N - 1); j+)System.out.print(dij + " ");System.out.println();/ 输出最短路径public void printShortestPath() / 输出所经城市System.out.print("经过城市：");String str = path0(int) Math.pow(2, N - 1) - 1;/ System.out.println(str);System.out.print(str.charAt(str.length() - 1);for (int i = str.length() - 2; i >= 0; i-) System.out.print("->" + str.charAt(i);System.out.println("会有最短路径");System.out.println("最短路径为：" + d0(int) Math.pow(2, N - 1) - 1);/ 主函数public static void main(String args) TSPDP TSP = new TSPDP();TSP.dynamic();/ 求最短路径TSP.print();/打印中间结果，测试和理解用TSP.printShortestPath();/ 输出最短路径/ 测试数据/* * 99999 3 6 7 * 5 99999 2 3 * 6 4 99999 2 * 3 7 5 99999 */6.1.2结果（1）（2）（3）（4）6.2贪心法6.2.1源代码/* * TSP：贪心法之最近邻点策略求解 */package Tsp;import java.util.Scanner;public class TSPGreedy int V;/ 存放旅行所经过的城市顶点int c;/ 存放每两座城市间的距离，注意：若路径不存在或同一城市间距离为无穷大int path;/ 存放旅行所经过的每两座城市间的距离int N;/ 城市个数int shortestPath;/ 表示最短路径int u0;/ 出发城市编号static int IFINITE = 99999;/ 无穷大距离 表示城市自己到达自己时，距离无穷大，不作为考虑因素public TSPGreedy() initialC();/ 得到最短路径public int getShortestPath() for (int i = 0; i < N; i+) shortestPath += pathi;return shortestPath;/ 初始化数组c，即顶点间距离public void initialC() Scanner in = new Scanner(System.in);System.out.println("请输入城市个数： （注意根据实际情况城市个数不可小于1！）");N = in.nextInt();if (N <= 1) System.out.println("不符合要求，请认真核对！");System.exit(0);/ 输入错误，结束！System.out.println("请输入城市相邻城市间距离（城市从0开始编号，且出发城市为第0个城市！）： ");c = new intNN;/ 为c分配空间for (int i = 0; i < N; i+)for (int j = 0; j < N; j+) cij = in.nextInt(); / 输入时，按城市编号从小到大，如若两城市间没有公路相连，则距离为无穷大。本城市与本城市间距离也为无穷大。public void tspGreedy() Scanner in = new Scanner(System.in);System.out.println("请输入出发城市编号（注意城市从0开始编号，请按照输入城市间距离即初始化c时顺序计算）：");u0 = in.nextInt();V = new intN + 1;path = new intN;int k = 0;Vk = u0;while (k < N) int min = IFINITE;k+;for (int i = 0; i < N; i+) int mark = 0;for (int j = 0; j < k; j+)if (Vj = i)mark = 1;if (mark = 0 && cVk - 1i < min) min = cVk - 1i;Vk = i;pathk - 1 = min;Vk = u0;pathk - 1 = cVk - 1Vk;/ 输出最短路径下所经城市，两城市间距离和最短路径public void print() shortestPath = 0;System.out.println("按照下列方式旅游会使所走路程最短：");for (int i = 0; i < N; i+) System.out.println("从" + Vi + "->" + Vi + 1 + ",所经路程为："+ pathi);shortestPath += pathi;System.out.println("总路程为：" + shortestPath);public static void main(String args) TSPGreedy tg = new TSPGreedy();tg.tspGreedy();/tg.print();/* * 99999 3 3 2 6 * 3 99999 7 3 2 * 3 7 99999 2 5 * 2 3 2 99999 3 * 6 2 5 3 99999 */6.2.2结果(1)(2)(3)(4)6.3回溯法（回溯法+深度优先搜索策略）6.3.1源代码#include <iostream>#include <cstdio>using namespace std;const int MAXSIZE = 100;const int MAX = ;int g_iArrMAXSIZEMAXSIZE;/邻接矩阵int g_iResult;/存放最优解int g_iPathMAXSIZE;/存放最优路径上int g_n;/元素个数int g_iCurResult;/当前累加路径和int g_iBestPathMAXSIZE;/还需要设置一个数组，用来保存最优解void swap(int* pI,int* pJ)int iTemp = *pI;*pI= *pJ;*pJ = iTemp;void printResult(int n,int* pArr) cout<<"最短距离为："<<endl; cout<<g_iResult<<endl; cout<<"最优路线为："<<endl;for(int i = 1 ; i <= n ; i+)if( i != 1)cout<<"->"<<pArri;elsecout<<pArri;cout<<"->1"<<endl;/可以做成字符串全排列的性质track(int i,int* pArr,int* pResult),其中pArr是用于存放最优解的路径void backTrace(int i,int* pArr)/递归基：如果已经遍历到叶子节点的上一层节点if(i = g_n)/判断累加和是否超过最大值,如果有0，应该排除;满足这个条件，才打印if(g_iArrpArri-1pArri != 0) && (g_iArrpArrg_n1 != 0) &&(g_iCurResult + g_iArrpArri-1pArri + g_iArrpArrg_n1 < g_iResult )g_iResult = g_iCurResult + g_iArrpArri-1pArri + g_iArrpArrg_n1;/用当前最优路径去更新最优路径，防止下一次没有for(int k = 1 ; k <= g_n ; k+)g_iBestPathk = pArrk;/递归步:判断能否进入子树，需要尝试每一个节点else/尝试不同的组合for(int j = i ; j <= g_n ; j+)/判断能否进入子树:如果当前值+下一个连线值的和 < 最优值，就进入,0要passif( (g_iArrpArri-1pArrj != 0) && (g_iCurResult + g_iArr pArri-1 pArrj