TSP问题及其解法研究

-50-510405【摘要】【关键词】【中图分类号】【文献标识码】【文章编号】（一）引言计算机科学是一种创造性思维活动的科学。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。它由有限条可执行的、有确定结果的程序指令组成。算法设计是一件非常困难的工作，常用的算法设计方法有：分治法、贪心方法、动态规划、回溯法、分枝－限界法、基本检索与周游方法、遗传算法等。本文将分别就贪心方法、动态规划、回溯法、遗传算法这几种算法设计方法研究0/1背包问题的求解方法进行分析，并对各种算法的复杂度进行分析。（二）常见算法设计方法概要1.动态规划基本思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划基本步骤：（1）找出昀优解的性质，并刻划其结构特征。（2）递归地定义昀优值。（3）以自底向上的方式计算出昀优值。（4）根据计算昀优值时得到的信息，构造昀优解。2.贪心算法顾名思义，贪心算法总是做出在当前看来昀好的选择。也就是说贪心算法并不从整体昀优考虑，它所做出的选择只是在某种意义上的局部昀优选择。当然，希望贪心算法得到的昀终结果也是整体昀优的。虽然贪心算法不能对所有问题都得到整体昀优解，但对许多问题它能产生整体昀优解。如单源昀短路经问题，昀小生成树问题等。在一些情况下，即使贪心算法不能得到整体昀优解，其昀终结果却是昀优解的很好近似。3.回溯法回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。4.遗传算法遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息。因此它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题。遗传算法是一种群体型操作，该操作以群体中所有个体为对象。选择、交叉和变异是遗传算法的三个主要算子，他们构成了遗传算法的主要操作，使遗传算法具有了其它传统方法所没有的特性。（三）TSP问题1.问题的提出设有n个城市，其中每两个城市之间都有道路相连，城市i和城市j之间的距离为Cij。从某城市出发周游所有城市，【收稿日期】【作者简介】-51-经过每个城市一次且仅一次，最后回到出发地，求总行程最短的周游路线。（1）使用动态规划解决动态规划方程：d(i,V-{i})=d(i,V)=min{ctk+d(k,V-{k})}k∈Vd(k,ά)=ckt时间复杂性：在整个计算过程中需要计算大小为j的不同城市集合个数为Cjn-1，j=0,1,……n-1。所以总个数为：Nt=∑−=10njcjn-1Tt=∑−=10njcjn-1*j=n∑−=10njcjn-1由二项式定理：（x+y）n=∑−=10njcjnxjyn-1所以T=∑=niT1i=O(n222)（2）使用贪心算法解决问题下面把城市和到目的地之间的关系用一个矩阵表示1234512345由于使用贪婪算法，每次都选择当前最短的目的地，所以应该会这么走：1－5－4－3－2－1花费值是2＋2＋1＋2＋3＝10。可以明显看出选择一个城市出发，时间复杂性为O(n2)。（3）使用回溯法解决问题加入n=4时，TSP的状态空间树的表示，很容易就能计算出它的时间复杂性O(n)=n!。（4）使用遗传算法解决问题初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1)。[随机规划与模糊规划]选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。1）对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj)j=1,…,i;i=1,…pop-size.2）从区间(0,pop-size)中产生一个随机数r；3）若qi-1step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：815216107431114612951813171对应：81421386325734324221。交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果rpc将所选的父代两两组队，随机产生一个位置进行交叉，如：814213863257343242216123568563185633211交叉后为：814213863251856332116123568563734324221变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点变异为x'k=ukmin+r(ukmax-ukmin)）操作。如：81421386325734324221变异后：814213106322734524121反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。（四）各种算法的比较设计方法时间复杂度优点缺点动态规划O(n222)不太适合解决TSP问题，时间太长。贪心算法O(n2)速度快，容易求解不一定能求最优解回溯法O(n!)能获得所有可行解，包括最优解时间过长遗传算法O(2n)能获得最优解，速度快算法不是很成熟（五）结束语以上是对动态规划，贪心算法，回溯法，遗传算法这四种常用算法设计方法原理的概要介绍，并具体应用于求解0/1背包问题中，以及对各种设计方法的算法分析。通过论述研究，得出各种算法在求解特定问题领域的优缺点【参考文献】∞34623∞46532∞44231∞64652∞