logo资料库

TSP旅行商问题各种解法 详细.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.03M 资料格式：docx 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    旅行商问题的几种求解算法比较 作者: (xxx 学校) 摘要:TSP 问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运 筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回 溯 法 分 别 来 实 现 这 个 题 目, 并 比 较 哪 种 更 优 越, 来 探 索 这 个 经 典 的NP(Nondeterministic Polynomial)难题. 关键词:旅行商问题 求解算法 比较 一.引言 旅行商问题(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)} uinS f(V,1)即为所求 2.分支限界法解TSP 问题 旅行商问题的解空间是一个排列树,与在子集树中进行最大收益和最小耗费分枝定界搜 索类似,使用一个优先队列,队列中的每个元素 中都包含到达根的路径. 假设我们要寻找的是最小耗费的旅行路径,那可以使用最小耗费分枝定界法.在实现 过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为MinHea pNode.每个节点包括如下区域:x(从1 到n 的整数排列,其中x[0]=1),s( 一个整数,使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而 剩余待访问的节点是x[s+1:n-1]),cc(旅行路径前缀,即解空间树中从根 节点到当前节点的耗费),lcost(该节点子树中任意叶节点中的最小耗费),r cost(从顶点x[s:n-1]出发的所有边的最小耗费之和).当类型为MinH eapNode(T)的数据被转换成为类型T 时,其结果即为lcost 的值.分枝定界 算法的代码见程序. 程序首先生成一个容量为1000 的最小堆,用来表示活节点的最小优先队列.活节点按其lcost 值从最小堆中取出.接下来,计算有向图中从每个顶点出发的边中 耗费最小的边所具有的耗费Mi nOut.如果某些顶点没有出边,则有向图中没有旅行 路径,搜索终止.如果所有的顶点都有出边,则 可以启动最小耗费分枝定界搜索.根的孩子(图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. template TAdjacencyWDigraph::BBTSP(intv[]) {// 旅行商问题的最小耗费分枝定界算法 // 定义一个最多可容纳1000 个活节点的最小堆 MinHeap>H(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]
    }// 把E-节点初始化为树根 MinHeapNodeE; E.x=newint[n]; for(i=0;i
    H.Insert(N);} }// 结束可行的孩子 delete[]E.x;}// 对本节点的处理结束 try{H.DeleteMin(E);}// 取下一个E-节点 catch(OutOfBounds){break;}// 没有未处理的节点 }if(bestc==NoEdge)returnNoEdge;// 没有旅行路径 // 将最优路径复制到v[1:n] 中 for(i=0;i
    员.TSP(v)返回旅行售货员回路最小费用.整型数组v 返回相应的回路.如果所给的图G 不含旅行售 货员回路,则返回NoEdge.函数TSP 所作的工作主要是为调用Backtrack 所需要变量初始化.由TSP 调用Backtrack(2)搜索整个解空间. 在递归函数Backtrack 中,当i=n 时,当前扩展结点是排列树的叶结点的父结点.此时,算法检测图G 是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1 的边.如果这两条边都 存在,则找一条旅行售货员回路.此时,算法还需判断这条回路的费用是否优于已找到的当前最优 回路的费用best.如果是,则必须更新当前最优值bestc 和当前最优解bestx. 当i
    Backtrack(I+1); cc-=a[x[i-1]][x[i]]; Swap(x[i],x[j]);} }}template TypeTSP(Type**a,intv[],intn,TypeNoEdge) {TravelingY; //初始化Y Y.x=newint[n+1]; // 置x 为单位排列 for(inti=1;i<=n;i++) Y.x[i]=I; Y.a=a; Y.n=n; Y.bestc=NoEdge; Y.bestc=v; Y.cc=0; Y.NoEdge=NoEdge; //搜索x[2:n]的全排列 Y.Backtrack(2); Delete[]Y.x; 三.三种方法的比较 1.动态规划法和回朔法的比较: 这本来就是两个完全不同的领域,一个是算法领域,一个是数据结构问题.但两者又交叉,又有区别. 从本质上讲就是算法与数据结构的本质区别,回朔是一个具体的算法,动态规划是数据结构中的一 个概念.动态规划讲究的是状态的转化,以状态为基准,确定算法,动态规划法所针对的问题有一个 显著的特征,即它所对应的子问题树中的子问题呈现大量的重复.动态规划法的关键就在于,对于 重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不 必重新求解.简单的说就是:动态规划法是从小单元开始积累计算结果.回朔讲究过程的推进与反 还,随数据的搜索,标记,确定下一步的行进方向,回朔是去搜索. 如果想要搜索时,发现有很多重复计算,就应该想到用动态规划了.动态规划和搜索都可以解决具 有最优子结构的问题,然而动态规划在解决子问题的时候不重复计算已经计算过的子问题,对每个 子问题只计算一次;而简单的搜索则递归地计算所有遇到的的子问题.比如一个问题的搜索树具有 如下形式: ........A ......./.......B...C ...../.\./.....D...E...F 如果使用一般深度优先的搜索,依次搜索的顺序是A-B-D-E-C-E-F,注意其中节点E 被重复搜索了两 次;如果每个节点看作是一个子问题的话,节点E 所代表的子问题就被重复计算了两次; 但是如果是用动态规划,按照树的层次划分阶段,按照自底向上的顺序,则在第一阶段计算D,E,F;第
    二阶段计算B,C;第三阶段计算A;这样就没有重复计算子问题E. 搜索法的优点是实现方便,缺点是在子问题有大量的重复的时候要重复计算子问题,效率较低;动 态规划虽然效率高,但是阶段的划分和状态的表示比较复杂,另外,搜索的时候只要保存单前的结 点;而动态规划则至少要保存上一个阶段的所有节点,比如在动态规划进行到第2 阶段的时候,必须 把第三阶段的D,E,F 三个节点全部保存起来,所以动态规划是用空间换时间. 另外,有一种折衷的办法,就是备忘录法,这是动态规划的一种变形.该方法的思想是:按照一般的搜 索算法解决子问题,但是用一个表将所有解决过的子问题保存起来,遇到一个子问题的时候,先查 表看是否是已经解决过的,如果已解决过了就不用重复计算.比如搜索上面那棵树,在A-B-D-E 的时 候,已经将E 记录在表里了,等到了A-B-D-E-C 的时候,发现E 已经被搜索过,就不再搜索E,而直接搜 索F,因此备忘录法的搜索顺序是A-B-D-E-C-(跳过E)-F 自底向上的动态规划还有一个缺点,比如对于下面的树: ........A ......./.......B...C......G ...../.\./.\..../.....D...E...F..H...I 如用自底向上的动态规划,各个阶段搜索的节点依次是: D,E,F,H,I B,C,GAA 才是我们最终要解决的问题,可以看到,G,H,I 根本与问题A 无关,但是动态规划还是将它们也解决 了一遍,这就造成了效率降低.而备忘录法则可以避免这种问题,按照备忘录法,搜索的次序仍然 是:A-B-D-E-C-(跳过E)-F.备忘录法的优点是实现简单,且在子问题空间中存在大量冗余子问题的 时候效率较高;但是要占用较大的内存空间(需要开一个很大的表来记录已经解决的子问题),而且 如果用递归实现的话递归压栈出栈也会影响效率;而自底向上的动态规划一般用for 循环就可以 了.值得一提的是,用动态规划法来计算旅行商的时间复杂度是指数型的. 2. 分支限界法和回朔法的比较: 分支限界法类似于回溯法,也是一种在问题的解空间树T 上搜索问题解的算法.但在一般情况下, 分支限界与回溯法的求解目标不同.回溯法的求解目标是找出T 中满足约束条件的所有解,而分支 限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标 函数值达到极大或极小的解,即在某种意义下的最优解.我们先看一个列子: 设G=(V,E)是一个带权图.图1 中各边的费用(权)为一正数.图中的一条周游线是包括V 中的每个顶 点在内的一条回路.一条周游路线的费用是这条路线上所有边的费用之和.所谓旅行售货员问题就 是要在图G 中找出一条有最小费用的周游路线. 给定一个有n 个顶点的带权图G,旅行售货员问题要找出图G 的费用(权)最小的周游路线.图1 是 一个4 顶点无向带权图.顶点序列1,2,4,3,1;1,3,2,4,1 和1,4,3,2,1 是该图中3 条不同的周游路线. 301256104
    A1B234CDE32423 3204 图14 顶点带权图 该问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图G 的一条周游路 线.图1 是当n=4 时这种树结构的示例.其中从根结点A 到叶结点L 的路径上边的标号组成一条周 游路线1,2,3,4,1.而从根结点到叶结点O 的路径则表示周游路线1,3,4,2,1.图G 的每一条周游路线 都恰好对应解空间树中一条从根结点到叶结点的路径.因此,解空间树中叶结点个数为(n-1)!. FGHIJK 434232 LMNOPQ 图2 旅行售货员问题的解空间树 对于图1 中的图G,用回溯法找最小费用周游路线时,从解空间树的根结点A 出发,搜索至B,C,F,L. 在叶结点L 处记录找到的周游路线1,2,3,4,1,该周游路线的费用为59.从叶结点L 返回至最近活动 结点F 处.由于F 处已没有可扩展结点,算法又返回到结点C 处.结点C 成为新扩展结点,由新扩展结 点,算法再移至结点G 后又移至结点M,得到周游路线1,2,4,3,1,其费用为66.这个费用不比已有周 游路线1,2,3,4,1 的费用小.因此,舍弃该结点.算法有依次返回至结点G,C,B.从结点B,算法继续搜索 至结点D,H,N.在叶结点N 算法返回至结点H,D,然后再从结点D 开始继续向纵深搜索至结点O.依 次方式算法继续搜索遍整个解空间,最终得到1,3,2,4,1 是一条最小费用周游路线. 以上便是回溯法找最小费用周游路线的实列,但如果我们用分支限界法来解的话,会更适合.由于 求解目标不同,导致分支限界法与回溯法在解空间树T 上的搜索方式也不相同.回溯法以深度优先 的方式搜索解空间树T,而分支限界法则以广度优先或以最小消耗优先的方式搜索解空间树T.分 支限界法的搜索策略是,在扩展结点处,先生成所有的儿子结点(分支),然后再从当前的活动点表中 选择下一个扩展结点.为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一 个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩 展结点,使搜索朝着解空间树上的最优解的分支推进,以便尽快的找出一个最优解. 四.结论: 参考文献:
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料