旅行商问题的几种求解算法比较

旅行商问题的几种求解算法比较作者:(xxx学校)摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回溯法分别来实现这个题目,并比较哪种更优越,来探索这个经典的NP(NondeterministicPolynomial)难题.关键词:旅行商问题求解算法比较一.引言旅行商问题(TravellingSalesmanProblem),是计算机算法中的一个经典的难解问题,已归为NP一完备问题类.围绕着这个问题有各种不同的求解方法,已有的算法如动态规划法,分支限界法,回溯法等,这些精确式方法都是指数级(2n)[2,3]的,根本无法解决目前的实际问题,贪心法是近似方法,而启发式算法不能保证得到的解是最优解,甚至是较好的解释.所以我认为很多问题有快速的算法(多项式算法),但是,也有很多问题是无法用算法解决的.事实上,已经证明很多问题不可能在多项式时间内解决出来.但是,有很多很重要的问题他们的解虽然很难求解出来,但是他们的值却是很容易求可以算出来的.这种事实导致了NP完全问题.NP表示非确定的多项式,意思是这个问题的解可以用非确定性的算法猜出来.如果我们有一个可以猜想的机器,我们就可以在合理的时间内找到一个比较好的解.NP-完全问题学习的简单与否,取决于问题的难易程度.因为有很多问题,它们的输出极其复杂,比如说人们早就提出的一类被称作NP-难题的问题.这类问题不像NP-完全问题那样时间有限的.因为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)}uinSf(V,1)即为所求2.分支限界法解TSP问题旅行商问题的解空间是一个排列树,与在子集树中进行最大收益和最小耗费分枝定界搜索类似,使用一个优先队列,队列中的每个元素中都包含到达根的路径.假设我们要寻找的是最小耗费的旅行路径,那可以使用最小耗费分枝定界法.在实现过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为MinHeapNode.每个节点包括如下区域: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时,其结果即为lcost的值.分枝定界算法的代码见程序.程序首先生成一个容量为1000的最小堆,用来表示活节点的最小优先队列.活节点按其lcost值从最小堆中取出.接下来,计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut.如果某些顶点没有出边,则有向图中没有旅行路径,搜索终止.如果所有的顶点都有出边,则可以启动最小耗费分枝定界搜索.根的孩子(图16-5的节点B)作为第一个E-节点,在此节点上,所生成的旅行路径前缀只有一个顶点1,因此s=0,x[0]=1,x[1:n-1]是剩余的顶点(即顶点2,3,.,n).旅行路径前缀1的开销为0,即cc=0,并且,rcost=ni=1MinOut.在程序中,bestc给出了当前能找到的最少的耗费值.初始时,由于没有找到任何旅行路径,因此bestc的值被设为NoEdge.程序旅行商问题的最小耗费分枝定界算法templateTAdjacencyWDigraph::BBTSP(intv[]){//旅行商问题的最小耗费分枝定界算法//定义一个最多可容纳1000个活节点的最小堆MinHeapH(1000);T*MinOut=newT[n+1];//计算MinOut=离开顶点i的最小耗费边的耗费TMinSum=0;//离开顶点i的最小耗费边的数目for(inti=1;i=n;i++){TMin=NoEdge;for(intj=1;j=n;j++)if(a[j]!=NoEdge&&(a[j]Min||Min==NoEdge))Min=a[j];if(Min==NoEdge)returnNoEdge;//此路不通MinOut=Min;MinSum+=Min;}//把E-节点初始化为树根MinHeapNodeE;E.x=newint[n];for(i=0;in;i++)E.x=i+1;E.s=0;//局部旅行路径为x[1:0]E.cc=0;//其耗费为0E.rcost=MinSum;Tbestc=NoEdge;//目前没有找到旅行路径//搜索排列树while(E.sn-1){//不是叶子if(E.s==n-2){//叶子的父节点//通过添加两条边来完成旅行//检查新的旅行路径是不是更好if(a[E.x[n-2]][E.x[n-1]]!=NoEdge&&a[E.x[n-1]][1]!=NoEdge&&(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]bestc||bestc==NoEdge)){//找到更优的旅行路径bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1];E.cc=bestc;E.lcost=bestc;E.s++;H.Insert(E);}elsedelete[]E.x;}else{//产生孩子for(inti=E.s+1;in;i++)if(a[E.x[E.s]][E.x]!=NoEdge){//可行的孩子,限定了路径的耗费Tcc=E.cc+a[E.x[E.s]][E.x];Trcost=E.rcost-MinOut[E.x[E.s]];Tb=cc+rcost;//下限if(bbestc||bestc==NoEdge){//子树可能有更好的叶子//把根保存到最大堆中MinHeapNodeN;N.x=newint[n];for(intj=0;jn;j++)N.x[j]=E.x[j];N.x[E.s+1]=E.x;N.x=E.x[E.s+1];N.cc=cc;N.s=E.s+1;N.lcost=b;N.rcost=rcost;H.Insert(N);}}//结束可行的孩子delete[]E.x;}//对本节点的处理结束try{H.DeleteMin(E);}//取下一个E-节点catch(OutOfBounds){break;}//没有未处理的节点}if(bestc==NoEdge)returnNoEdge;//没有旅行路径//将最优路径复制到v[1:n]中for(i=0;in;i++)v[i+1]=E.x;while(true){//释放最小堆中的所有节点delete[]E.x;try{H.DeleteMin(E);}catch(OutOfBounds){break;}}returnbestc;}while循环不断地展开E-节点,直到找到一个叶节点.当s=n-1时即可说明找到了一个叶节点.旅行路径前缀是x[0:n-1],这个前缀中包含了有向图中所有的n个顶点.因此s=n-1的活节点即为一个叶节点.由于算法本身的性质,在叶节点上lcost和cc恰好等于叶节点对应的旅行路径的耗费.由于所有剩余的活节点的lcost值都大于等于从最小堆中取出的第一个叶节点的lcost值,所以它们并不能帮助我们找到更好的叶节点,因此,当某个叶节点成为E-节点后,搜索过程即终止.while循环体被分别按两种情况处理,一种是处理s=n-2的E-节点,这时,E-节点是某个单独叶节点的父节点.如果这个叶节点对应的是一个可行的旅行路径,并且此旅行路径的耗费小于当前所能找到的最小耗费,则此叶节点被插入最小堆中,否则叶节点被删除,并开始处理下一个E-节点.其余的E-节点都放在while循环的第二种情况中处理.首先,为每个E-节点生成它的两个子节点,由于每个E-节点代表着一条可行的路径x[0:s],因此当且仅当是有向图的边且x[i]是路径x[s+1:n-1]上的顶点时,它的子节点可行.对于每个可行的孩子节点,将边的耗费加上E.cc即可得到此孩子节点的路径前缀(x[0:s],x)的耗费cc.由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边,因此任何叶节点对应的耗费都不可能小于cc加上离开各剩余顶点的出边耗费的最小值之和,因而可以把这个下限值作为E-节点所生成孩子的lcost值.如果新生成孩子的lcost值小于目前找到的最优旅行路径的耗费bestc,则把新生成的孩子加入活节点队列(即最小堆)中.如果有向图没有旅行路径,程序返回NoEdge;否则,返回最优旅行路径的耗费,而最优旅行路径的顶点序列存储在数组v中.3.回朔法解TSP问题回朔法有通用解题法之称,它采用深度优先方式系统地搜索问题的所有解,基本思路是:确定解空间的组织结构之后,从根结点出发,即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点,这个结点成为新的活结点,并成为当前扩展结点.如果在当前扩展结点处不能再向纵深方向转移,则当前扩展结点成为死结点.此时,回溯到最近的活结点处,并使其成为当前扩展结点,回溯到以这种工作方式递归地在解空间中搜索,直到找到所求解空间中已经无活结点为止.旅行商问题的解空间是一棵排列树.对于排列树的回溯搜索与生成1,2,……,n的所有排列的递归算法Perm类似.设开始时x=[1,2,…n],则相应的排列树由x[1:n]的所有排列构成.旅行商问题的回溯算法找旅行商回路的回溯算法Backtrack是类Treveling的私有成员函数,TSP是Treveling的友员.TSP(v)返回旅行售货员回路最小费用.整型数组v返回相应的回路.如果所给的图G不含旅行售货员回路,则返回NoEdge.函数TSP所作的工作主要是为调用