旅行商问题的求解方法动态规划法和贪心法算法论文-毕业论文.doc

旅行商问题的求解方法摘要旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。关键字：旅行商问题；动态规划法；贪心法；分支限界法1引言旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。2正文2.1蛮力法2.1.1蛮力法的设计思想蛮力法所依赖的基本技术是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。在基本的数据结构中，一次处理每个元素的方法是遍历。2.1.2算法讨论用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。如对于图1，我们求解过程如下：（1） 路径：1-2-3-4-1；路径长度：18；（2） 路径：1-2-4-3-1；路径长度：11；（3） 路径：1-3-2-4-1；路径长度：23；（4） 路径：1-3-4-2-1；路径长度：11；（5） 路径：1-4-2-3-1；路径长度：18；（6） 路径：1-4-3-2-1；路径长度：18；从中，我们可以知道，路径（2）和（4）路径长度最短。我们还应注意到，图1中，有3对不同的路径，对每对路径来说，不同只是路径的方向，因此，可以将这个数量减半，则可能的解有（n-1）！/2个。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速增长。如：一个10城市的TSP问题有大约有180,000个可能解。一个20城市的TSP问题有大约有60,000,000,000,000,000个可能解。 一个50城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升水。因此，我们可以知道用蛮力法求解TSP问题，只能解决问题规模很小的实例。2.2动态规划法2.2.1动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。2.2.2TSP问题的动态规划函数假设从顶点i出发，令表示从顶点i出发经过中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，于是，TSP问题的动态规划函数为： 2.2.3算法讨论（1）for (i=1; iN; i+) /初始化第0列 di0=ci0; （2）for (j=1; j -1; j+) for (i=1; in; 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.3.4时间复杂性和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。2.3贪心法2.3.1贪心法的设计思想贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。2.3.2最近邻点策略求解TSP问题贪心法求解TSP问题的贪心策略是显然的，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。最近邻点策略：从任意城市出发，每次在没有到过的城市中选择距离已选择的城市中最近的一个，直到经过了所有的城市，最后回到出发城市。2.3.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.3.4时间复杂性但需注意，用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。2.4分支限界法2.4.1分支限界法的设计思想 假设求解最大化问题，解向量为，其中，的取值范围为某个有穷集合，。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界down, up，然后从根结点出发，扩展根结点的个孩子结点，从而构成分量的种可能的取值方式。对这个孩子结点分别估算可能取得的目标函数值，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于，也就是部分解应满足： 本文本欲详细讨论该算法，但无奈在编程问题中，尚有问题有待解决，时间所限，不得已放弃。本人编程过程中所用算法思想与老师课上所教略有不同，在寻找下界时，是首先把每个结点所能到达的各个结点及其可能的路径算出来，并添加到PT表中，但最后，不知是何原因，在还有一个城市尚未加入时，PT表的添加出现了问题，思忖良久，仍未解决，时间所限，迫不得已，留待以后有时间再另行研究，本文就只给出动态规划法和贪心法的具体求解过程。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优点本文程序优点，各个子函数功能分隔很明显，没有大量集中在一个函数里面，而是分成了几个不同功能的小函数，这样程序可阅读性提高。另外，程序中有详细注释，程序中变量取名都是根据变量的性质和所代表的含义命名的，也相应提高了程序的可读性。对于动态规划法，城市个数可以在算法时间允许的范围内任意，于这点来说，通用性较好；对于贪心法，出发城市可以任意，城市个数也可以任意，通用性较好。4建议当城市个数较少时，用动态规划法求出最优解；当城市个数较多并且各边的代价值分布比较均匀时，贪心法可以给出较好的近似解。5参考文献（1）计算机算法分析与设计第二版，王晓东编著，电子工业出版社（2）Java语言与面向对象程序设计（第2版）印旻、王行言编著，清华大学出版社（3）求解TSP算法，周康、强小利、同小军、许进，计算机工程与应用6附录6.1动态规划法6.1.1源代码package exp2;import java.util.Scanner;public class TSPDynamic String V;/顶点生成的子集，这里把每一个子集用一个字符串表示int c;/顶点间距离int d;/存放迭代结果int N; /城市个数String path;/用于存放每种选择下经过的城市static int IFINITE = 99999;/无穷大距离 表示城市自己到达自己时，距离无穷大，不作为考虑因素/构造函数public TSPDynamic()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 (int)Math.pow(2,N-1) - 1)return;/如果全部顶点已初始化完成，则返回。if(m = 0)Vm + = ;/初始化出发顶点，即V0elseint 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中第一个元素elseString 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;/如若存在，则返回falseelse return 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是最后一个元素，则返回其前面的元素 else return (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 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()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();for(int i = 0 ; i N ; i +)for(int j = 0 ; j N ; j +)System.out.print(cij + );System.out.println();for(int i = 0 ; i N ; i +)for(int j = 0 ; j = 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) TSPDynamic TSP = new TSPDynamic();TSP.dynamic();/求最短路径/TSP.print();TSP.printShortestPath();/输出最短路径/测试数据/*99999 3 6 75 99999 2 36 4 99999 23 7 5 99999 */6.1.2结果（1）（2）（3）（4）6.2贪心法6.2.1源代码package exp2;import java.util.Scanner;public class TSPGreedNode int V;/存放旅行所经过的城市顶点int c;/存放每两座城市间的距离，注意：若路径不存在或同一城市间距离为无穷大int path;/存放旅行所经过的每两座城市间的距离int N;/城市个数int shortestPath;/表示最短路径int u0;/出发城市编号static int IFINITE = 99999;/无穷大距离 表示城市自己到达自己时，距离无穷大，不作为考虑因素public TSPGreedNode ()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 tspGreedNode()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 + Vi + 1 + ,所经路程为： + pathi);shortestPath += pathi;System.out.println(总路程为： + shortestPath);/* * param args */public static void main(String args) / TODO Auto-generated method stubTSPGreedNode gd = new TSPGreedNode();gd.tspGreedNode();gd.print();/*99999 3 3 2 63 99999 7 3 23 7 99999 2 52 3 2 99999 36 2 5 3 99999*/6.2.2结果(1)(2)(3)(4)毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日致 谢时间飞逝，大学的学习生活很快就要过去，在这四年的学习生活中，收获了很多，而这些成绩的取得是和一直关心帮助我的人分不开的。首先非常感谢学校开设这个课题，为本人日后从事计算机方面的工作提供了经验，奠定了基础。本次毕业设计大概持续了半年，现在终于到结尾了。本次毕业设计是对我大学四年学习下来最好的检验。经过这次毕业设计，我的能力有了很大的提高，比如操作能力、分析问题的能力、合作精神、严谨的工作作风等方方面面都有很大的进步。这期间凝聚了很多人的心血，在此我表示由衷的感谢。没有他们的帮助，我将无法顺利完成这次设计。首先，我要特别感谢我的知道郭谦功老师对我的悉心指导，在我的论文书写及设计过程中给了我大量的帮助和指导，为我理清了设计思路和操作方法，并对我所做的课题提出了有效的改进方案。郭谦功老师渊博的知识、严谨的作风和诲人不倦的态度给我留下了深刻的印象。从他身上，我学到了许多能受益终生的东西。再次对周巍老师表示衷心的感谢。其次，我要感谢大学四年中所有的任课老师和辅导员在学习期间对我的严格要求，感谢他们对我学习上和生活上的帮助，使我了解了许多专业知识和为人的道理，能够在今后的生活道路上有继续奋斗的力量。另外，我还要感谢大学四年和我一起走过的同学朋友对我的关心与支持，与他们一起学习、生活，让我在大学期间生活的很充实，给我留下了很多难忘的回忆。最后，我要感谢我的父母对我的关系和理解，如果没有他们在我的学习生涯中的无私奉献和默默支持，我将无法顺利完成今天的学业。致 谢四年的大学生活就快走入尾声，我们的校园生活就要划上句号，心中是无尽的难舍与眷恋。从这里走出，对我的人生来说，将是踏上一个新的征程，要把所学的知识应用到实际工作中去。回首四年，取得了些许成绩，生活中有快乐也有艰辛。感谢老师四年来对我孜孜不倦的教诲，对我成长的关心和爱护。学友情深，情同兄妹。四年的风风雨雨，我们一同走过，充满着关爱，给我留下了值得珍藏的最美好的记忆。在我的十几年求学历程里，离不开父母的鼓励和支持，是他们辛勤的劳作，无私的付出，为我创造良好的学习条件，我才能顺利完成完成学业，感激他们一直以来对我的抚养与培育。最后，我要特别感谢我的导师刘望蜀老师、和研究生助教吴子仪老师。是他们在我毕业的最后关头给了我们巨大的帮助与鼓励，给了我很多解决问题的思路，在此表示衷心的感激。老师们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。他无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高这对于我以后的工作和学习都有一种巨大的帮助，感谢他耐心的辅导。在论文的撰写过程中老师们给予我很大的帮助，帮助解决了不少的难点，使得论文能够及时完成，这里一并表示真诚的感谢。