算法论文：旅行商问题的求解方法(动态规划法和贪心法).doc

《算法论文：旅行商问题的求解方法(动态规划法和贪心法).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.旅行商问题的求解方法摘要旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。关键字：旅行商问题；动态规划法；贪心法；分支限界法1引言旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的

2、参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。2正文2.1蛮力法2.1.1蛮力法的设计思想蛮力法所依赖的基本技术

3、是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。在基本的数据结构中，一次处理每个元素的方法是遍历。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->

4、2->1；路径长度：11；..（1）路径：1->4->2->3->1；路径长度：18；（2）路径：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个可能解。一个5

5、0城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升水。因此，我们可以知道用蛮力法求解TSP问题，只能解决问题规模很小的实例。 2.2动态规划法2.2.1动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。2.2.2TSP问题的动态规划函数假设从顶点i出发，令表示从顶

6、点i出发经过中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，，于是，TSP问题的动态规划函数为： 2.2.3算法讨论（1）for(i=1;i

7、(c[0][k]+d[k][m]);（4）输出最短路径长度d[0][-1];2.3.4时间复杂性..和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。2.3贪心法2.3.1贪心法的设计思想贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优

8、解。2.3.2最近邻点策略求解TSP问题贪心法求解TSP问题的贪心策略是显然的，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及