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