现在位置: >

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

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

旅行商问题的求解方法

摘要

旅行商问题(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;

相关文档
相关主题
返回顶部
热门文档