
第六章分支限界法.ppt
36页第六章 分支限界法塑夯橙谷沂聋杀抢罢翔全尧枕土替妮值薪捐啡兼婪于消稳它疵易畏胶唆太第六章分支限界法第六章分支限界法16.1分支限界法的基本思想1. 分支限界法与回溯法的不同(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解 (2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树 侦叭净止久馏塑蠢瓣腔苍咆镜努厉褪敖缉饶峭燎晴正迎础忽簧才磺帛宛阉第六章分支限界法第六章分支限界法26.1分支限界法的基本思想2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树 在分支限界法中,每一个活结点只有一次机会成为扩展结点活结点一旦成为扩展结点,就一次性产生其所有儿子结点在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中 此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程这个过程一直持续到找到所需的解或活结点表为空时为止。
叁遗饯誊番艳株逝角扒曙敦瑚谐缴拓飘跌葱楔慧摊瞧料芜欣焉想压登秆艰第六章分支限界法第六章分支限界法36.1分支限界法的基本思想3. 常见的两种分支限界法(1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个节点为扩展节点 (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点扛踌输侯萨单逮榜每吝惹萎纠绸科议见卫价眩傀枉兼署汉怎草谍螟驴汕链第六章分支限界法第六章分支限界法46.2单源最短路径问题1. 问题描述 下面以一个例子来说明单源最短路径问题:在下图所给的有向图G中,每一边都有一个非负边权要求图G的从源顶点s到目标顶点t之间的最短路径 猜童惯膨萌黑孙掩矢谦名踢嘘雅堆俐蒲寅把荣庭擂居嫁仇誓欣酞骚剿挟他第六章分支限界法第六章分支限界法56.2单源最短路径问题 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树其中,每一个结点旁边的数字表示该结点所对应的当前路长戊砚温氖龚囤锌击壹命笨市咋眼奸吭狙跪怂隶浓讼遮焙颜逗死鞘道外鹏刺第六章分支限界法第六章分支限界法66.2单源最短路径问题2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。
其优先级是结点所对应的当前路长 算法从图G的源顶点s和空优先队列开始结点s被扩展后,它的儿子结点被依次插入堆中此后,算法从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点如果从当前扩展结点i到顶点j有边可达,且从源出发,途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中这个结点的扩展过程一直继续到活结点优先队列为空时为止盎帛尊钳绳旧纽换虏豢尧返乡践栋县咎嫂卯食剐晚旨曝围踪颐楚筹痉寝资第六章分支限界法第六章分支限界法76.2单源最短路径问题3. 剪枝策略 在算法扩展结点的过程中,一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以该结点为根的子树 在算法中,利用结点间的控制关系进行剪枝从源顶点s出发,2条不同路径到达图G的同一顶点由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去 搁波来锌莫猜好盒枫藩矾妄拒踪仙蓉呕遣肝墩哼寸绘湾邱斌麦户报屉赴农第六章分支限界法第六章分支限界法86.2单源最短路径问题 while (true) { // 搜索问题的解空间 for (int j=1;j<=n;j++) if(a[enode.i][j] < Float.MAX_VALUE && enode.length+a[enode.i][j] < dist[j]) { // 顶点i到顶点j可达,且满足控制约束 dist[j]=enode.length+a[enode.i][j]; p[j]=enode.i; HeapNode node = new HeapNode(j,dist[j]); heap.put(node); // 加入活结点优先队列 } if (heap.isEmpty()) break; else enode = (HeapNode) heap.removeMin(); }顶点顶点I I和和j j间有边,且此间有边,且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 排拇缆田倒知串翁惠何寄优确貌脊聪礼窝睛准贩蓉酞封银婶弧廉墨潜友捏第六章分支限界法第六章分支限界法96.3 装载问题1. 问题描述有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船,其中集装箱i的重量为Wi,且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。
如果有,找出一种装载方案 容易证明:如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案 (1)首先将第一艘轮船尽可能装满;(2)将剩余的集装箱装上第二艘轮船 梦妖夕汇袍蜒饼塑院缠垮崔紫董文僵担喉枣忠评今遍饱卡御促髓颈追辕瞻第六章分支限界法第六章分支限界法106.3 装载问题2. 队列式分支限界法 在算法的while循环中,首先检测当前扩展结点的左儿子结点是否为可行结点如果是则将其加入到活结点队列中然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)2个儿子结点都产生后,当前扩展结点被舍弃 活结点队列中的队首元素被取出作为当前扩展结点,由于队列中每一层结点之后都有一个尾部标记-1,故在取队首元素时,活结点队列一定不空当取出的元素是-1时,再判断当前队列是否为空如果队列非空,则将尾部标记-1加入活结点队列,算法开始处理下一层的活结点虹竣腕摊加睛亢鹊毛歪闷仔枷洛豌惹堪腔竣佳惧勺馆鲸脐坞栏黍务硕俐磊第六章分支限界法第六章分支限界法116.3 装载问题2. 队列式分支限界法while (true) { if (ew + w[i] <= c) enQueue(ew + w[i], i); // 检查左儿子结点 enQueue(ew, i); //右儿子结点总是可行的 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 if (ew == -1) { if (queue.isEmpty()) return bestw; queue.put(new Integer(-1)); // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++; // 进入下一层 } }哦脚曙梳悉肩姬腊饰棍灿警橱鹰思号饲奥忱嫉亿殊绢损半熬变住页兼舟淄第六章分支限界法第六章分支限界法126.3 装载问题3. 算法的改进 节点的左子树表示将此集装箱装上船,右子树表示不将此集装箱装上船。
设bestw是当前最优解;ew是当前扩展结点所相应的重量;r是剩余集装箱的重量则当ew+rbestw时,可将其右子树剪去,因为此时若要船装最多集装箱,就应该把此箱装上船 另外,为了确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值喳识死盐隙借吻秽的尔诸篆勉难缉趁饥屎篆慷蘸安增沉脾长兴施忠妄芯垛第六章分支限界法第六章分支限界法136.3 装载问题3. 算法的改进// 检查左儿子结点 int wt = ew + w[i]; if (wt <= c) { // 可行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) queue.put(new Integer(wt)); }提前更新提前更新bestw bestw // 检查右儿子结点 if (ew + r > bestw && i < n) // 可能含最优解 queue.put(new Integer(ew)); ew=((Integer)queue.remove()) .intValue(); // 取下一扩展结点 右儿子剪枝右儿子剪枝 嚣出宝擦罚菜疫瞎袱滨基晋立悯闭焊缺匀完销锑耽室党昆镊仟葛乾拢票稼第六章分支限界法第六章分支限界法146.3 装载问题4. 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解,算法必须存储相应子集树中从活结点到根结点的路径。
为此目的,可在每个结点处设置指向其父结点的指针,并设置左、右儿子标志 private static class QNode { QNode parent; // 父结点 boolean leftChild; // 左儿子标志 int weight; // 结点所相应的载重量蝶络韦塔佐搬许肛劝纸爪膨局继狼儡辰产铝且缉搀咙函划据掘帅镭坎头亲第六章分支限界法第六章分支限界法156.3 装载问题找到最优值后,可以根据parent回溯到根节点,找到最优解// 构造当前最优解 for (int j = n; j > 0; j--) { bestx[j] = (e.leftChild) ? 1 : 0; e = e.parent; }排茄魏岛粕遵综聊划陡辫憾三膨涨熄奈饯胯溃蔼厨与茶盯幼沉砰戳蚤凸桨第六章分支限界法第六章分支限界法166.3 装载问题5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。
优先队列中优先级最大的活结点成为下一个扩展结点以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级子集树中叶结点所相应的载重量与其优先级相同 在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解此时可终止算法 甚姥寂仔铜锅肆巾澡眺牡隘罩豫臆昏西积空灵泵样促抽蔼尹徘扇臃奇蛮霜第六章分支限界法第六章分支限界法176.4 布线问题算法的思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中,并且将这些方格标记为1,即从起始方格a到这些方格的距离为1 接着,算法从活结点队列中取出队首结点作为下一个扩展结点,并将与当前扩展结点相邻且未标记过的方格标记为2,并存入活结点队列这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止即加入剪枝的广度优先搜索淹惰甭缆践盈睛怖卯辩暇该后朝走华随耻量洼讼寿南鳖贩嚎憎加弘冒汗沮第六章分支限界法第六章分支限界法186.4 布线问题Position [] offset = new Position [4];offset[0] = new Position(0, 1); // 右offset[1] = new Position(1, 0); // 下offset[2] = new Position(0, -1); // 左offset[3] = new Position(-1, 0); // 上 定义移动方向的定义移动方向的相对位移相对位移 for (int i = 0; i <= size + 1; i++) { grid[0][i] = grid[size + 1][i] = 1; // 顶部和底部 grid[i][0] = grid[i][size + 1] = 1; // 左翼和右翼 }设置边界的围墙设置边界的围墙低斯抗吹墅花位搜碴寂啥盖邻锥蚂吝玩露厉稼讶缚塘糠璃椽番忽夯殃厚悟第六章分支限界法第六章分支限界法196.4 布线问题for (int i = 0; i < numOfNbrs; i++){ nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 该方格未标记 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; q.put(new Position(nbr.row, nbr.col)); } }找到目标位置后,可以通过回溯方法找到这条最短路径。
袍荆阉喘裸拼绑栓硅衅丝纶糜汁骋近事熄桌例贮晌匹悠晴葡猜兜舵萍命兵第六章分支限界法第六章分支限界法206.5 0-1背包问题•算法的思想 首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列 在下面描述的优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和 算法首先检查当前扩展结点的左儿子结点的可行性如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列当扩展到叶节点时为问题的最优值呻萝智盈琅不授验押昼咙疯勒枯阎咳单皱鼻谊姜孕窑虞珍浸价多氢盖备金第六章分支限界法第六章分支限界法216.5 0-1背包问题上界函数while (i <= n && w[i] <= cleft) // n表示物品总数,cleft为剩余空间 { cleft -= w[i]; //w[i]表示i所占空间 b += p[i]; //p[i]表示i的价值 i++; }if (i <= n) b += p[i] / w[i] * cleft; // 装填剩余容量装满背包return b; //b为上界函数稗顿尸腿辣懒册阅随双蛊葱踊道匪桐夕拇踊钻昨乾割撒巷图拼荣呸膛着国第六章分支限界法第六章分支限界法226.5 0-1背包问题 while (i != n + 1) {// 非叶结点 double wt = cw + w[i]; if (wt <= c) {// 左儿子结点为可行结点 if (cp + p[i] > bestp) bestp = cp + p[i]; addLiveNode(up,cp + p[i],cw + w[i],i + 1, enode, true); } up = bound(i + 1); if (up >= bestp) //检查右儿子节点 addLiveNode(up,cp,cw,i + 1, enode, false); // 取下一个扩展节点(略)}分支限界搜索过分支限界搜索过程程矩胚弛丑绢龄她采芍帕醉越分愿汐谬浙迭姆见蔬刀账疟爽树菱中识醚孙掣第六章分支限界法第六章分支限界法236.6 最大团问题1.问题描述 给定无向图G=(V,E)。
如果UV,且对任意u,vU有(u,v)E,则称U是G的完全子图G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中G的最大团是指G中所含顶点数最多的团 下图G中,子集{1,2}是G的大小为2的完全子图这个完全子图不是团,因为它被G的更大的完全子图{1,2,5}包含{1,2,5}是G的最大团{1,4,5}和{2,3,5}也是G的最大团 辆脾枫钠悟悼旋沪硕坡趟胖瘤实曝阎塑缩贺通嚼裴布显巨惕因过稀呛被寻第六章分支限界法第六章分支限界法246.6 最大团问题2. 上界函数 用变量cliqueSize表示与该结点相应的团的顶点数;level表示结点在子集空间树中所处的层次;用cliqueSize +n-level+1作为顶点数上界upperSize的值 在此优先队列式分支限界法中,upperSize实际上也是优先队列中元素的优先级算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素 爸刹慌些猛芭责卯船氧莹添裤锤疤宝妹市守过掩号茵铲氖饿六基翌县徽长第六章分支限界法第六章分支限界法256.6 最大团问题3. 算法思想 子集树的根结点是初始扩展结点,对于这个特殊的扩展结点,其cliqueSize的值为0。
算法在扩展内部结点时,首先考察其左儿子结点在左儿子结点处,将顶点i加入到当前团中,并检查该顶点与当前团中其他顶点之间是否有边相连当顶点i与当前团中所有顶点之间都有边相连,则相应的左儿子结点是可行结点,将它加入到子集树中并插入活结点优先队列,否则就不是可行结点 接 着 继 续 考 察 当 前 扩 展 结 点 的 右 儿 子 结 点 当upperSize>bestn时,右子树中可能含有最优解,此时将右儿子结点加入到子集树中并插入到活结点优先队列中聋釉二靡域埠锌终砂椭辑日冲娠修碳欧拄盅窝舟敝印狄曳肢醒图娇率捷痰第六章分支限界法第六章分支限界法266.6 最大团问题 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点 对于子集树中的叶结点,有upperSize=cliqueSize此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值,从而进一步搜索不可能得到更大的团,此时算法已找到一个最优解 惰妥晶痊糠柔偿狮痊子特芒倪袍部毒皂凯涸峨娠套预芳誓训石淖诲测劈钵第六章分支限界法第六章分支限界法276.7 旅行售货员问题1. 问题描述 某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。
他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小 路线是一个带权图图中各边的费用(权)为正数图的一条周游路线是包括V中的每个顶点在内的一条回路周游路线的费用是这条路线上所有边的费用之和 旅行售货员问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图的一条周游路线旅行售货员问题要在图G中找出费用最小的周游路线 布匣试啸殖镇阴刺赂轴铭舒活延盟哼陷嫩忽色齐雇篙棠少够澳谦嗓纂思蒲第六章分支限界法第六章分支限界法286.7 旅行售货员问题2. 算法描述 算法开始时创建一个最小堆,用于表示活结点优先队列堆中每个结点的子树费用的下界lcost值是优先队列的优先级接着算法计算出图中每个顶点的最小费用出边并用minout记录如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法即告结束如果每个顶点都有出边,则根据计算出的minout作算法初始化 算法的while循环体完成对排列树内部结点的扩展对于当前扩展结点,算法分2种情况进行处理:蘸扯课钢锐点滩霓赐贼裹势财状造篮稿批仆篆窟十贵浪睦潭酷畸柔二宁伸第六章分支限界法第六章分支限界法296.7 旅行售货员问题 1、首先考虑s=n-2的情形,此时当前扩展结点是排列树中某个叶结点的父结点。
如果该叶结点相应一条可行回路且费用小于当前最小费用,则将该叶结点插入到优先队列中,否则舍去该叶结点 2、当s 算法结束时返回找到的最小费用,相应的最优解由数组v给出 简田恤餐利玫糟斧芽痢伎撇超乾姜姓浅女扎符刷沤兆冶极刻篙二加袜圾稻第六章分支限界法第六章分支限界法316.8 批处理作业问题1. 问题的描述 给定n个作业的集合J={J1,J2,…,Jn}每一个作业Ji都有2项任务要分别在2台机器上完成每一个作业必须先由机器1处理,然后再由机器2处理作业Ji需要机器j的处理时间为tji,i=1,2,…,n;j=1,2对于一个确定的作业调度,设是Fji是作业i在机器j上完成处理的时间则所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小榴命芍耻描弥佳冻仔特巢佑磷津箭善膀膛渴轩龚哇峰湿披胞互谈佐脓苟枷第六章分支限界法第六章分支限界法326.8 批处理作业问题2. 限界函数在结点E处相应子树中叶结点完成时间和的下界是:注意到如果选择Pk,使t1pk在k>=r+1时依非减序排列,S1则取得极小值同理如果选择Pk使t2pk依非减序排列,则S2取得极小值 这可以作为优先队列式分支限界法中的限界函数。 椽派虚杏丸尽梁句苑铰粥袋端浪藻獭胃猫返昏锻褂算秀琼叠喳氖子郝玖伞第六章分支限界法第六章分支限界法336.8 批处理作业问题3. 算法描述 算法的while循环完成对排列树内部结点的有序扩展在while循环体内算法依次从活结点优先队列中取出具有最小bb值(完成时间和下界)的结点作为当前扩展结点,并加以扩展 首先考虑enode.s=n的情形,当前扩展结点enode是排列树中的叶结点enode.sf2是相应于该叶结点的完成时间和当enode.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx 当enode.s












