分支限界法——TSP问题.ppt

《分支限界法——TSP问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分支限界法旅行售货员问题（TSP）小燕子6.1分支限界法的基本思想1.分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。6.1分支限界法的基本思想2.分支限界法基本思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次

2、机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。6.1分支限界法的基本思想3.常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现

3、最大效益优先最小优先队列：使用最小堆，体现最小费用优先旅行售货员问题（TSP）某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。该问题是一个NP完全问题，有(n-1)!条可选路线。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。问题陈述:旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的

4、周游路线。即：设G(V,E)是一带权有向图,V={1,2,…n},其耗费矩阵C=(ci,j)，当(i,j)E时,记ci,j=且ci,j=.问如何选择周游路线使耗费最小？TSP问题算法思路:设周游路线从结点1开始,解为等长数组X=(1,x2,...xn)xi{2,...,n}.则解空间树为排列树，在树中做广度优先搜索。约束条件:xixj,ij;目标函数:解向量对应的边权之和∑Cij目标函数限界初值:U=活结点队列：CDEFGHIJK队列式分支限界法：初始扩展结点为B，活结点队列为空。C=301142662514592524算法描

5、述：①算法开始时创建一个最小堆，用于表示活结点优先队列②堆中每个结点的子树费用的下界lcost值是优先队列的优先级。③接着算法计算出图中每个顶点的最小费用出边并用minout记录。④如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。⑤如果每个顶点都有出边，则根据计算出的minout作算法初始化。优先队列式分支限界法用极小堆存储活结点表E46DC30B被扩展后，它的三个儿子结点C,D,E被依次插入堆中D6C30D6C30JK1424E被扩展后，它的儿子结点J,K被依次插入当前堆中J14C30K24HJ1430K2411I2

6、6CKH1130J1424I26CD被扩展后，它的儿子结点H,I被依次插入当前堆中初始扩展结点为B，优先队列为空。{}；B{E,D,C}；E{D,J,K,C}；D{H,J,K,I,C}；H{J,K,I,C}；J{K,I,C}；K{I,C}；I{C}；C{}.K被扩展后，得到可行解费用为59，高于当前最优解25H被扩展后，得到一条旅行售货员回路（1,3,2,4,1），相应的费用为25结点I本身的费用已高于当前最优解，故没必要扩展结点IIJ1430K2426CJ被扩展后，得到另一条费用为25的回路（1,4,2,3,1）K2426IC30I26C

7、30C300结点C本身的费用也已高于当前最优解，故没必要扩展结点C此时，优先队列为空，算法终止。算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：①首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。②当s

8、x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。当lcost