文档介绍：旅行商问题的几种求解算法比较
作者:
(xxx学校)
摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,,分支界限法,回溯法分别来实现这个题目,并比较哪种更优越,来探索这个经典的NP(Nondeterministic Polynomial)难题.
关键词:旅行商问题求解算法比较
旅行商问题(Travelling Salesman Problem),是计算机算法中的一个经典的难解问题,,已有的算法如动态规划法,分支限界法,回溯法等,这些精确式方法都是指数级(2n)[2,3]的,根本无法解决目前的实际问题,贪心法是近似方法,而启发式算法不能保证得到的解是最优解,(多项式算法),但是,,,有很多很重要的问题他们的解虽然很难求解出来,,意思是这个问题的解可以用非确定性的算法"猜",-完全问题学****的简单与否,,它们的输出极其复杂,比如说人们早就提出的一类被称作NP---问题由上述那些特征,所以很容易想到一些简单的算法――(通常时间复杂度为O(2^n)),,或许你就是成功者.
本篇论文就是想用几种方法来就一个销售商从几个城市中的某一城市出发,不重复地走完其余N—1个城市,并回到原出发点,在所有可能的路径中求出路径长度最短的一条,比较是否是最优化,哪种结果好.
动态规划法解TSP问题
我们将具有明显的阶段划分和状态转移方程的规划称为动态规划,这种动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,,许多问题的阶段划分并不明显,,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),,因此,动态规划是一种将问题实例分解为更小的,相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略.
旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小),,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算.
关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k个城市的可能集合,动态规划的递推关系为:
gk(i,S)=min[gk-1(j,S\{j})+dji] j属于S,dji表示j-i的距离.
或者我们可以用:
f(S,v)表示从v出发,经过S中每个城市一次且一次,最短的路径.
f(S,v)=min { f(S-{u},u)+dist(v,u) }
u in S
f(V,1)即为所求
旅行商问题的解空间是一个排列树,与在子集树中进行最大收益和最小耗费分枝定界搜
索类似,使用一个优先队列,队列中的每个元素中都包含到达根的路径.
假设我们要寻找的是最小耗费的旅行路径,
过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为M i n H e a
p N o d : x(从1到n的整数排列,其中x [ 0 ] = 1 ),s(
一个整数,使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而
剩余待访问的节点是x [ s + 1 : n - 1 ]),c c(旅行路径前缀,即解空间树中从根
节点到当前节点的耗费),l c o s