旅行售货员问题.ppt

旅行售货员问题计算复杂性理论介绍2023/5/241问题的描述 售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。旅行售货员问题虽然易于被人理解，但其计算复杂度却是问题的输入规模的指数函数,是一个NP完全问题。2023/5/242问题的描述l路线是一个带权图带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。l用图论的术语来描述旅行售货员问题：即在一个正权完全图中寻找一个具有最小权的哈密顿回路，对于此问题，由于完全图中必然存在哈密顿回路完全图中必然存在哈密顿回路，目前可以用于求解的方法有枚举法，分枝限界法，这两种算法可以求得此问题的精确解精确解，但到目前为止，还没有求解这一问题的有效算法，我们可以利用分支限界法，回溯法求解此问题的近似解近似解，以求得与最优解最为接近的解。2023/5/243旅行售旅行售货员问货员问题题枚举法枚举法复杂度极高，可以求出复杂度极高，可以求出精确解精确解通过对问题的排列树的通过对问题的排列树的合理剪枝，大大缩减了合理剪枝，大大缩减了问题需要求解的时间。问题需要求解的时间。可以求出可以求出精确解精确解基于三角不等式性基于三角不等式性质等，进一步抽象质等，进一步抽象求解过程，可以求求解过程，可以求出出近似解近似解，复杂度，复杂度为多项式级别为多项式级别问题的精确解和近似解分支限界分支限界法法NP问题问题近似算法近似算法回溯法回溯法 通过对排列树的剪枝，缩减通过对排列树的剪枝，缩减问题需要的求解时间。可求问题需要的求解时间。可求精确解精确解及及近似解近似解2023/5/244共有6条周游路线：（1,2,4,3,1）66（1,2,3,4,1）59（1,3,2,4,1）25（1,3,4,2,1）66（1,4,2,3,1）25（1,4,3,2,1）59设G=(V,E)是一个带权图。图中各边的权值为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径从树的根结点到任一叶结点的路径定义了图G的一条周游路线。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题要找出费用最小费用最小的周游路线。实例：实例：4个城市个城市 n=4 叶节点个数(周游线路)=(n-1)!枚举法枚举法66 59 25 66 25 592023/5/245l从第一个城市到第二个城市有n-1种走法，从第二个城市到第三个城市有n-2种走法因而共有(n-1)!种走法。l若考虑v1v2vnv1和v1 vn vn-1v2 v1是同一条回路，还共有(1/2)(n-1)!条不同的哈密顿回路。l为了比较权的大小，对每条哈密顿回路要做n-1次加法，故加法的总数为(1/2)(n-1)(n-1)!。时间复杂度时间复杂度O(n!)例如当有40个城市时，(1/2)(n-1)(n-1)!的近似值为3.771047，假设一台计算机每秒完成1011次（百亿）次加法，将需要超过1.191029年才能完成所需的加法次数，显然是不可能的。算法效率算法效率 2023/5/2461、有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件约束条件的最佳解时，往往要使用回溯法。2、回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷穷举式搜索法举式搜索法。这种方法适用于解一些组合数相当大组合数相当大的问题。3、回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。生成问题状态的基本方法生成问题状态的基本方法扩展结点:一个正在产生儿子的结点活结点:一个自身已生成但其儿子还没有全部生成的结点死结点:一个所有儿子已经产生的结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）回溯法2023/5/247基本思想一.解空间树的动态搜索 回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。初始时，根结点成为一个活结点，同时也称为当前的扩展结点。在当前扩展结点处，搜索向纵深纵深方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向深方向移动，则当前的扩展结点就成为一个死结点。此时，应往回移动回溯至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。2023/5/248二.常用剪枝函数：用约束函数约束函数在扩展结点处剪去不满足约束的子树；用限界函数限界函数剪去得不到最优解的子树。为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。回溯法=穷举+剪枝2023/5/249解空间树的动态搜索解空间树的动态搜索将图中n个顶点编号为1,2,n，以顶点1为起点，旅行回路描述为1,x1,x2,.,xn,1，其中x1,x2,.,xn为顶点2,3,4,n的1个排列，因此解空间大小为(n-1)!ABDHN2023/5/2410剪枝剪枝2023/5/2411算法描述算法描述 旅行售货员问题的解空间是一棵排列树。开始时，x=1,2,n相应的排列树由x=1:n的所有排列构成。在递归算法Backtrack中，1.当当i=n时，当前扩展节点是排列树的时，当前扩展节点是排列树的叶节点的父节点叶节点的父节点。检测图G是否存在一条从顶点xn-1到顶点xn的边和一条从顶点xn到顶点1的边。如果这两条边都存在，则找到一条旅行员售货回路。此时，算法还需要还需要判断这条回路的费用是否优于优于已找到的当前最优回流的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。2.当当in时，当前扩展节点位于排列树的第时，当前扩展节点位于排列树的第i-1层层。图G中存在从顶点xi-1到顶点xi的边时，x1:i构成图G的一条路径，且当x1:i的费用小于当前最优值时算法进入树的第i层，否则将剪去相应的子树。2023/5/2412private static void backtrack(int i)if(i=n)/当前扩展结点是排列树的叶结点的父结点当前扩展结点是排列树的叶结点的父结点 if(axn-1xnmax_value&/顶点顶点n-1和和n之间有边之间有边 axn1 max_value|/顶点顶点n到到1之间有边之间有边 cc+axn-1xn+axn1bestc)for(int j=1;j=n;j+)bestxj=xj;/得到最优解得到最优解 bestc=cc+axn-1xn+axn1;/得到最优值得到最优值 else /in,当前扩展结点位于第当前扩展结点位于第i-1层层 cc:记录当前路径x1:i的费用a:图G的邻接矩阵2023/5/2413 for(int j=i;j=n;j+)/搜索第搜索第i层的所有子树层的所有子树 /是否可进入是否可进入xj子树？子树？if(axi-1xj max_value&(bestc=max_value|cc+axi-1xjbestc)/搜索子树搜索子树 swap(x,i,j);/交换交换xi,xj的值的值 cc+=axi-1xi;backtrack(i+1);/进入下一层子树进入下一层子树 cc-=axi-1xi;/还原还原cc的值的值 swap(x,i,j);/还原还原xi,xj的值的值 2023/5/2414Backtrack最坏情况下时间复杂度O(n-1)!)更新bestx时间复杂度 O(n)时间复杂度很高时间复杂度很高O(n!)算法效率算法效率2023/5/24151.分支限界法基本思想分支限界法基本思想 分支限界法常以广度优先广度优先或以最小耗费以最小耗费(最大效益最大效益)优先优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.常见的两种分支限界法常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的（1）队列式(FIFO)分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点（2）优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点为当前扩展结点 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先分支限界法2023/5/24161.求解目标回溯法：找出解空间中满足约束条件的所有解分支限界法找出满足约束条件的一个解在满足约束条件的解中找出使某一目标函数值极大或极小的解分支限界法和回溯法一样都是在解空间上搜索问题解的算法2.搜索方式深度优先 DFS回溯法：分支限界法 广度优先BFS或最小损耗优先2023/5/2417C=301142662514592524算法描述算法描述：准备工作：建立小根堆，用于存储活活动节点动节点。计算每个顶点的最小出边，若存在某个顶点没有出边，则算法终止。初始化树根（顶点1）为第一个活动节点。判断节点是否是叶结点的父节点：是的话，则检查是否一定有最低耗费，若是加入小根堆；不是叶结点的父节点，则生成子节点，并判断子节点是否有可能取得最低耗费，若可能则加入小根堆；取出下一个节点作为活动节点，若该节点已经是叶结点，返回当前最低耗费值，即为最优旅行。若不是叶结点则循环2、3步。邻接矩阵2023/5/2418优先队列式分支限界法用极小堆存储活结点表E46DC30B B被扩展后，它的三个儿子结被扩展后，它的三个儿子结点点C,D,EC,D,E被依次插入堆中被依次插入堆中D6C 30D6C30JK1424E E被扩展后，它的儿子结点被扩展后，它的儿子结点J,KJ,K被依次插入当前堆中被依次插入当前堆中J14C30K24HJ1430K2411I26CKH1130J1424I26CD D被扩展后，它的儿子结点被扩展后，它的儿子结点H,IH,I被依次插入当前堆中被依次插入当前堆中初始扩展结点为初始扩展结点为B B，优先队列为空。，优先队列为空。2023/5/2419；BE,D,C；ED,J,K,C；DH,J,K,I,C；HJ,K,I,C；JK,I,C；KI,C；IC；C.K K被扩展后，得到可行解费用被扩展后，得到可行解费用为为5959，高于当前最优解，高于当前最优解2525H H被扩展后，得到一条旅行被扩展后，得到一条旅行售货员回路（售货员回路（1,3,2,4,11,3,2,4,1），），相应的费用为相应的费用为2525结点结点I I本身的费用已高于当前本身的费用已高于当前最优解，故没必要扩展结点最优解，故没必要扩展结点I IIJ1430K2426CJ J被扩展后，得到另一条费用被扩展后，得到另一条费用为为2525的回路（的回路（1,4,2,3,11,4,2,3,1）K2426IC30I26C30C300结点结点C C本身的费用也已高于当本身的费用也已高于当前最优解，故没必要扩展结点前最优解，故没必要扩展结点C C此时，优先队列为空，算法终此时，优先队列为空，算法终止。止。2023/5/2420NP问题近似算法l从实际应用中抽象出的旅行售货员问题具有一些特殊性质。比如，费用函数c往往具有三角不等式性质，即对任意3个顶点u,v,w有c(u,v)1，不存在性能比为的解旅行售货员问题的多项式时间近似算法。2023/5/2421NP问题近似算法void approxTSP(Gragh g)(1)选择g的任意顶点r；(2)用Prim算法找出带权图g的一颗以r为根的最小生成树T；(3)前序遍历树T得到顶点表L；(4)将r加入到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；2023/5/2422NP问题近似算法(a)图G顶点集abcdefgh)(b)(b)找到的最小生成树找到的最小生成树(MST)T(MST)T完全遍历完全遍历DFS abcbh ba def egeda (c)(c)对对T T作前序遍历的顺序作前序遍历的顺序 abch def g aabch def g a(d)L(d)L产生的哈密顿回路产生的哈密顿回路H H取捷径生成解取捷径生成解(e)G(e)G的一个最小费用旅行售货员回路的一个最小费用旅行售货员回路2023/5/2423NP问题近似算法其中，a表示所给的图G顶点集；b表示由算法找到的一颗最小生成树T；c表示对树T所做的前序遍历访问各顶点的次序；d表示由T的前序遍历顶点表示L产生的哈密顿回路H；e表示图G的一个最小费用旅行售货员回路。在b时，对T的完全遍历W=abcbhbadefegeda，还不是一个旅行售货员回路，它访问了图G中某些顶点多次。由于费用函数满足三角不等式，可以在W的基础上，从中删去已访问过的顶点已访问过的顶点，而不会增加旅行费用。若在W中删去顶点u和w间的一个顶点v，就用边(u,w)代替原来从u到w的一条路。反复用这个办法删去W中多次访问的顶点，可得到图G的一条旅行售货员回路H=abchdefga。2023/5/2424总结(1)枚举法 枚举法是最差的一种算法，即将所有可能的结果都排列一次，并比较解与当前最优解的大小，因此其时间复杂度很高O(n!)，在实际应用中当结点数很多时不可取。(2)回溯法 如果不考虑更新bestx所需的计算时间，则算法backtrack需要O(n-1)!)计算时间。由于算法backtrack在最坏的情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需O(n)计算时间，从而整个算法的计算时间复杂性为O(n!)。2023/5/2425(3)分支限界法 由于是NP问题，其时间复杂度很高，当相对于回溯法而言，分支限界法剪掉了一些不必要的计算，效率有很大的提高，但是在最坏的情况下可能需要满历所有的结点。此时的时间复杂度也是很高的。O(2 n)搜索状态空间O(2)指数时间对每个结点的计算O(n)(4)NP问题近似算法 作为NP完全问题，相对于其他算法，基于三角不等式性质的旅行售货员近似算法，效率有很大的提高。其不存在最坏的情况，算法稳定性较好，且性价比在常数级别。在采用朴素Prim算法时算法复杂度为O(n2)，还可以使用二叉堆优化Prim算法达到O(Elog(V)。E 边边 V结结点点 多项式时间2nn22023/5/2426O(1)O(logn)(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)2023/5/2427TSP_旅行商问题旅行商问题-动态规划动态规划 精确精确解解TSP_旅行商问题旅行商问题-贪心算法贪心算法 近似最优解近似最优解TSP_旅行商问题旅行商问题-模拟退火算法模拟退火算法TSP_旅行商问题旅行商问题-遗传算法遗传算法TSP_旅行商问题旅行商问题-粒子群算法粒子群算法TSP_旅行商问题旅行商问题-神经网络神经网络拓展2023/5/2428