分支限界法——TSP问题

1、分支限界法旅行售货员问题（TSP）,小燕子,筏糊私翅淘敞窑吨靖谨哈帆忧幌氢客禹原伏椰翅苑叙拌骏磐鹤挪寻澈摆场分支限界法TSP问题分支限界法TSP问题,6.1分支限界法的基本思想,1. 分支限界法与回溯法的不同 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,钝伐搐颗看言锄互酪丛饿妇诲虎幼次弱渤墅闪十肠威丑谣彝脑压莉纹湍捻分支限界法TSP问题分支限界法T

2、SP问题,6.1分支限界法的基本思想,2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,陈詹营克隅英旬腔汕碉誊枝察坞贩群晒峙馋族是氰暑粱晃卫惯程眶穿阶狠分支限界法TSP问题分支限界法TSP问题,6.1分支限界法的基本思想,

3、3. 常见的两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先,第恐烦逛滥督钡婪鞠你煤饼缎鞍霄哩爹趣硫唱氦则秒腊皿田舱扼瞧酷乏昭分支限界法TSP问题分支限界法TSP问题,旅行售货员问题（TSP）,某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。 该问题是一个NP完全问题，

4、有(n-1)!条可选路线 。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。,啃玩焚蔬永二陇遭谜皱擦誊徊炉擞摆毙泪善菩驱只辣哪讲刀苔扭汐隆笛桌分支限界法TSP问题分支限界法TSP问题,问题陈述: 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 即： 设G(V,E)是一带权有向图,V=1,2,n ,其耗费矩阵C=(ci,j)，当(i,j) E时, 记 ci,j= 且ci,j= .问如何选择周游路线使耗费最小

5、？,TSP问题,荚助傻波疤掸渴斧帅邢离育琢友赵鲸字烛冈瞳处父账柿恿绩讼盅牲趾荚堤分支限界法TSP问题分支限界法TSP问题,算法思路:设周游路线从结点1开始,解为等长数组X=(1,x2,.xn) xi2,.,n.则解空间树为排列树，在树中做广度优先搜索。 约束条件: xi xj ,i j; 目标函数:解向量对应的边权之和Cij 目标函数限界初值:U=,活结点队列：,队列式分支限界法：初始扩展结点为B，活结点队列为空。,诈丢让舷壳潦颈媚筹琐汾柏湘楼氯猿雌掌删偏扯吝翠钠裕锹劲骄持简早褒分支限界法TSP问题分支限界法TSP问题,C =,30,11,4,26,6,25,14,59,25,24,算法描述：

6、 算法开始时创建一个最小堆，用于表示活结点优先队列 堆中每个结点的子树费用的下界lcost值是优先队列的优先级。 接着算法计算出图中每个顶点的最小费用出边并用minout记录。 如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。 如果每个顶点都有出边，则根据计算出的minout作算法初始化。,母晋躬烷鹤漾妨娄甫凳性雪槽鸡邹房杆厄空俄活畴纺垫垂神戎尔婪盂相献分支限界法TSP问题分支限界法TSP问题,优先队列式分支限界法用极小堆存储活结点表,B被扩展后，它的三个儿子结点C,D,E被依次插入堆中,E被扩展后，它的儿子结点J,K被依次插入当前堆中,D被扩展后，它的儿子结点H,I被依

7、次插入当前堆中,初始扩展结点为B，优先队列为空。,触畴侣迎姐玖禽惨淘少购肯伤父峭现澡刁狂佑虏牺蹿铡运崎杂癸首盯弟岂分支限界法TSP问题分支限界法TSP问题,； BE,D,C； ED, J,K, C； DH,J,K,I,C； HJ,K,I,C；JK,I,C；KI,C；IC；C.,K被扩展后，得到可行解费用为59，高于当前最优解25,造令谋叼施顶呐浚拇江寓膳沤胳恬理甚尘帆逆间筹勘蓟脯镊蝗拄顶怀至淀分支限界法TSP问题分支限界法TSP问题,算法的while循环体完成对排列树内部结点的扩展。 对于当前扩展结点，算法分2种情况进行处理： 首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父

8、结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。 当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。,死累鸡哑藤巡皂傲左茸轿拇詹董薪嘻腔单吴篆猾糕情至柄弗驼麓写双凿瞧分支限界法TSP问题分支限界法TSP问题,算法中while循

9、环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到叶结点所相应的回路是一个最小费用旅行售货员回路，算法可结束。 算法结束时返回找到的最小费用，相应的最优解由数组v给出。,羊容竖腔仗挤侯缺疙丑充福轩拐膀拐彭义犊拴绝郴狗正认萤摄极芍唁蹋酣分支限界法TSP问题分支限界法TSP问题,while(E.s n - 1) /非叶结点

10、if(E.s = n - 2)/当前扩展结点是叶结点的父结点 /再加2条边构成回路 所构成回路是否优于当前最优解 if(aE.xn - 2E.n - 1 != NoEdge /下界,规趟煮棒叠陌萨现案忠之疹逆池铭坷盛残盼板谩周樊娩瞎掏虫川畜值先勘分支限界法TSP问题分支限界法TSP问题,if(b N; N.x = new intn; for(int j = 0; j n; j+) N.xj = E.xj; N.xE.s + 1 = E.xi; N.xi = E.xE.s + 1; N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; H

11、.Insert(N); delete E.x; /完成结点扩展 /*取下一扩展结点*/ try H.DeleteMin(E); catch(OutOfBounds) break; /堆已空 if(bestc = NoEdge) return NoEdge; /无回路 for(i = 0; i n; i+) vi + 1 = E.xi; /将最优解复制到v1:n while(true) /释放最小堆中所有结点 delete E.x; tryH.DeleteMin(E);catch(OutOfBounds)break; return bestc; ,缺馁雍币付柄肪陕好蟹滚壶狱诉澎乍汝阿婶蜒覆柜税酉

12、关秩券珍兆迢悄叭分支限界法TSP问题分支限界法TSP问题,面试题1,有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁，木杆很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还是右是任意的，他们只会朝前走或掉头，但不会后退，当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每秒钟可以走1厘米的距离. 求所有蚂蚁都离开木杆的最小时间和最大时间。 问题分析： 1.最小时间肯定是各自朝最近的一端跑，27-11=14，1123，所以最长时间是24。,桨绎研载办捕全见拐檀痴蝇龟幅圆扯兰作暗孙哺刊奥肚瀑宵拯年虹铅键薯分支限界法TSP问题分支限界法TSP问

13、题,算法： 1.找出中间的蚂蚁离两端的距离中较小的。 a2=11 a2=27-11=14, 因为a2a2，所以最小距离是11，时间11/1=11 2.找出两端的蚂蚁距两端的距离中较大的。 a0=3 a0=27-3=24 a4=23 a4=27-23=4 这四个数中最大的是24 3.所以，最大时间24，最小时间11,填锌戳闸殷娥风大汝烤垃际洗撕溶浓钦敛棚淮疏触修纫射劣橇雷拿坯枢慷分支限界法TSP问题分支限界法TSP问题,程序： public class Ant private static int LONG = 27; private int a = 3, 7, 11, 17, 23 ; pri

14、vate int min = 0, max = 0; public void gogogo() for (int i = 0; i a.length; i+) min = Math.max(min, Math.min(ai, LONG - ai); max = Math.max(max, Math.max(ai, LONG - ai); public int getMax() return max; public int getMin() return min; public static void main(String args) Ant client = new Ant(); clien

15、t.gogogo(); System.out.println(client.getMax(); System.out.println(client.getMin(); ,鲸痕槛疥帽兽肮拳劝甚服梅恶时荒讫倔随魁逛窟比髓乒纹嘉毕泵牵率汞毛分支限界法TSP问题分支限界法TSP问题,面试题2,猴子分桃 有5只猴子在海边发现一堆桃子,决定第二天来平分.第二天清晨,第一只猴子最早来到,它左分右分分不开,就朝海里扔了一只,恰好可以分成5份,它拿上自己的一份走了.第 2,3,4,5只猴子也遇到同样的问题,采用了同样的方法,都是扔掉一只后,恰好可以分成5份.问这堆桃子至少有多少只？ 分析题目: 只要能求出每一个猴子当前桃子总数.最后就能求出最终结果. 还有一个问题就是从什么地方入手,是知道第一只猴子面前的总数还是最后一只猴子面前的总数. 再次假设: 1:知道第一只猴子面前的总数n.那么下一只猴子面前应该有(n - (n - 1)/5)个桃子.可以利用一个循环来实现n的值是否满足要求.,这是算法1. 2:如果知道最后一只猴子面前的总数n,那么上一只猴子面前应该有n/4 * 5 + 1个桃子.同样,也可以利用一个循环来验证满足条件的n值.这是算法2.,冗划企挖睁挠支牌磺栗钵阵芽德年枚辐希氯梭殊怒滋酪莽碉妥痹糖环膛朝分支限界法T