为了正常的体验网站,请在浏览器设置里面开启Javascript功能!
首页 > 第6章 分支限界法

第6章 分支限界法

2010-05-20 41页 pdf 1010KB 40阅读

用户头像

is_612760

暂无简介

举报
第6章 分支限界法 1 第六章 分支限界法 2 第六章 分支限界法 本章主要知识点 • 6.1 分支限界法的基本思想 • 6.2 单源最短路径问题 • 6.3 装载问题 • 6.4 布线问题 • 6.5 0-1背包问题 • 6.6 最大团问题 • 6.7 旅行售货员问题 • 6.8 电路板排列问题 • 6.9 批处理作业调度 3 6.1分支限界法的基本思想 1.分支限界法与回溯法的不同 (1)求解目标:回溯法的求...
第6章 分支限界法
1 第六章 分支限界法 2 第六章 分支限界法 本章主要 • 6.1 分支限界法的基本 • 6.2 单源最短路径问题 • 6.3 装载问题 • 6.4 布线问题 • 6.5 0-1背包问题 • 6.6 最大团问题 • 6.7 旅行售货员问题 • 6.8 电路板排列问题 • 6.9 批处理作业调度 3 6.1分支限界法的基本思想 1.分支限界法与回溯法的不同 (1)求解目标:回溯法的求解目标是找出解空间树中满 足约束条件的所有解,而分支限界法的求解目标则是 找出满足约束条件的一个解,或是在满足约束条件的 解中找出在某种意义下的最优解。 (2)搜索方式的不同:回溯法以深度优先的方式搜索解 空间树,而分支限界法则以广度优先或以最小耗费优 先的方式搜索解空间树。 4 6.1分支限界法的基本思想 2.分支限界法基本思想 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜 索问题的解空间树。 在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结 点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿 子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其 余儿子结点被加入活结点中。 此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结 点扩展过程。这个过程一直持续到找到所需的解或活结点表为空 时为止。 5 6.1分支限界法的基本思想 3.常见的两种分支限界法 (1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个节点为 扩展节点。 (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节 点成为当前扩展节点。 6 6.2单源最短路径问题 1.问题描述 下面以一个例子来说明单源最短路径问题:在下图所给的有 向图G中,每一边都有一个非负边权。要求图G的从源顶点s到目 标顶点t之间的最短路径。 7 6.2单源最短路径问题 下图是用优先队列式分支限界法解有向图G的单源最短路径问 题产生的解空间树。其中,每一个结点旁边的数字表示该结点所对 应的当前路长。 8 6.2单源最短路径问题 2.算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来 存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它 的儿子结点被依次插入堆中。此后,算法从堆中取出具有最小当 前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相 邻的所有顶点。如果从当前扩展结点i到顶点j有边可达,且从源 出发,途经顶点i再到顶点j的所相应的路径的长度小于当前最优 路径长度,则将该顶点作为活结点插入到活结点优先队列中。这 个结点的扩展过程一直继续到活结点优先队列为空时为止。 9 6.2单源最短路径问题 3.剪枝策略 在算法扩展结点的过程中,一旦发现一个结点的下界不小于 当前找到的最短路长,则算法剪去以该结点为根的子树。 在算法中,利用结点间的控制关系进行剪枝。从源顶点s出 发,2条不同路径到达图G的同一顶点。由于两条路径的路长不 同,因此可以将路长长的路径所对应的树中的结点为根的子树剪 去。 10 6.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和j间有边,且此 路径长小于原先从原点 到j的路径长 11 6.3装载问题 1.问题描述 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船,其中集 装箱i的重量为Wi,且 21 1 ccw n i i   装载问题要求确定是否有一个合理的装载可将这个集装箱装上 这2艘轮船。如果有,找出一种装载方案。 容易证明:如果一个给定装载问题有解,则采用下面的策略可得到 最优装载方案。 (1)首先将第一艘轮船尽可能装满; (2)将剩余的集装箱装上第二艘轮船。 12 6.3装载问题 2.队列式分支限界法 在算法的while循环中,首先检测当前扩展结点的左儿子结点 是否为可行结点。如果是则将其加入到活结点队列中。然后将其 右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2 个儿子结点都产生后,当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点,由于队列 中每一层结点之后都有一个尾部标记-1,故在取队首元素时,活 结点队列一定不空。当取出的元素是-1时,再判断当前队列是否 为空。如果队列非空,则将尾部标记-1加入活结点队列,算法开 始处理下一层的活结点。 13 6.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++; //进入下一层 } } 14 6.3装载问题 3.算法的改进 节点的左子树表示将此集装箱装上船,右子树表示不将此集 装箱装上船。设bestw是当前最优解;ew是当前扩展结点所相应的 重量;r是剩余集装箱的重量。则当ew+rbestw时,可将其右子 树剪去,因为此时若要船装最多集装箱,就应该把此箱装上船。 另外,为了确保右子树成功剪枝,应该在算法每一次进入左 子树的时候更新bestw的值。 15 6.3装载问题 3.算法的改进 //检查左儿子结点 int wt = ew + w[i]; if (wt <= c) { //可行结点 if (wt > bestw) bestw = wt; //加入活结点队列 if (i < n) queue.put(new Integer(wt)); } 提前更新 bestw //检查右儿子结点 if (ew + r > bestw && i < n) //可能含最优解 queue.put(new Integer(ew)); ew=((Integer)queue.remove()) .intValue(); //取下一扩展结点 右儿子剪枝 16 6.3装载问题 4.构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解, 算法必须存储相应子集树中从活结点到根结点的路径。为此目 的,可在每个结点处设置指向其父结点的指针,并设置左、右儿 子标志。 private static class QNode { QNode parent; //父结点 boolean leftChild; //左儿子标志 int weight; //结点所相应的载重量 17 6.3装载问题 找到最优值后,可以根据parent回溯到根节点,找到最优解。 //构造当前最优解 for (int j = n; j > 0; j--) { bestx[j] = (e.leftChild) ? 1 : 0; e = e.parent; } 18 6.3装载问题 5.优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活 结点表。活结点x在优先队列中的优先级定义为从根结点到结点x 的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结 点x为根的子树中所有结点相应的路径的载重量不超过它的优先 级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中,一旦有一个叶结点成为当前扩 展结点,则可以断言该叶结点所相应的解即为最优解。此时可终 止算法。 19 6.4布线问题 算法的思想 解此问题的队列式分支限界法从起始位置a开始将它作为第 一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结 点被加入到活结点队列中,并且将这些方格标记为1,即从起 始方格a到这些方格的距离为1。 接着,算法从活结点队列中取出队首结点作为下一个扩展 结点,并将与当前扩展结点相邻且未标记过的方格标记为2, 并存入活结点队列。这个过程一直继续到算法搜索到目标方格 b或活结点队列为空时为止。即加入剪枝的广度优先搜索。 20 6.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; //左翼和右翼 } 设置边界的围墙 21 6.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)); } } 找到目标位置后,可以通过回溯方法找到这条最短路径。 22 6.5 0-1背包问题 •算法的思想 首先,要对输入数据进行预处理,将各物品依其单位重量价值 从大到小进行排列。 在下面描述的优先队列分支限界法中,节点的优先级由已装 袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量 的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该 左儿子结点是可行结点,则将它加入到子集树和活结点优先队列 中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结 点满足上界约束时才将它加入子集树和活结点优先队列。当扩展 到叶节点时为问题的最优值。 23 6.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为上界函数 24 6.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); // 取下一个扩展节点(略) } 分支限界搜索 过程 25 6.6最大团问题 1. 问题描述 给定无向图G=(V,E)。如果UV,且对任意u,vU有(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的最大团。 26 6.6最大团问题 2.上界函数 用变量cliqueSize表示与该结点相应的团的顶点数;level 表示结点在子集空间树中所处的层次;用cliqueSize +n-level+1 作为顶点数上界upperSize的值。 在此优先队列式分支限界法中,upperSize实际上也是优先 队列中元素的优先级。算法总是从活结点优先队列中抽取具有最 大upperSize值的元素作为下一个扩展元素。 27 6.6最大团问题 3.算法思想 子集树的根结点是初始扩展结点,对于这个特殊的扩展结 点,其cliqueSize的值为0。 算法在扩展内部结点时,首先考察其左儿子结点。在左儿子 结点处,将顶点i加入到当前团中,并检查该顶点与当前团中其他 顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边 相连,则相应的左儿子结点是可行结点,将它加入到子集树中并 插入活结点优先队列,否则就不是可行结点。 接 着 继 续 考 察 当 前 扩 展 结 点 的 右 儿 子 结 点 。 当 upperSize>bestn时,右子树中可能含有最优解,此时将右儿子结 点加入到子集树中并插入到活结点优先队列中。 28 6.6最大团问题 算法的while循环的终止条件是遇到子集树中的一个叶结点 (即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点,有upperSize=cliqueSize。此时 活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点 的upperSize值,从而进一步搜索不可能得到更大的团,此时算法 已找到一个最优解。 29 6.7旅行售货员问题 1.问题描述 某售货员要到若干城市去推销商品,已知各城市之间的路程 (或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后 回到驻地的路线,使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用(权)为正数。图的一 条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费 用是这条路线上所有边的费用之和。 旅行售货员问题的解空间可以组织成一棵树,从树的根结点 到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题 要在图G中找出费用最小的周游路线。 30 6.7旅行售货员问题 2.算法描述 算法开始时创建一个最小堆,用于表示活结点优先队列。堆 中每个结点的子树费用的下界lcost值是优先队列的优先级。接着 算法计算出图中每个顶点的最小费用出边并用minout。如果 所给的有向图中某个顶点没有出边,则该图不可能有回路,算法 即告结束。如果每个顶点都有出边,则根据计算出的minout作算 法初始化。 算法的while循环体完成对排列树内部结点的扩展。对于当前 扩展结点,算法分2种情况进行处理: 31 6.7旅行售货员问题 1、首先考虑s=n-2的情形,此时当前扩展结点是排列树中某 个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于 当前最小费用,则将该叶结点插入到优先队列中,否则舍去该叶 结点。 2、当s 0 && total[j] != node.now[j]) ld++; node.cd = Math.max(ld, enode.cd); if (node.cd < bestd) {//可能产生更好的叶结点 node.s = enode.s + 1; for (int j = 1; j <= n; j++) node.x[j] = enode.x[j]; node.x[node.s] = enode.x[i]; node.x[i] = enode.x[node.s]; heap.put(node); } } } 算法描述 计算出每一个儿子结点 的密度与bestd进行比较 大于bestd时加入队列 37 6.9批处理作业问题 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 i iFf 1 2 称为该作业调度的完成时间和。批处理作业调度问题要求对于给定 的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。 38 6.9批处理作业问题 2.限界函数 在结点E处相应子树中叶结点完成时间和的下界是: },max{ 212 SSFf Mi i   注意到如果选择Pk,使t1pk在k>=r+1时依非减序排列,S1则取得极 小值。同理如果选择Pk使t2pk依非减序排列,则S2取得极小值。 }ˆ,ˆmax{ 212 SSFf Mi i   这可以作为优先队列式分支限界法中的限界函数。 39 6.9批处理作业问题 3.算法描述 算法的while循环完成对排列树内部结点的有序扩展。在while 循环体内算法依次从活结点优先队列中取出具有最小bb值(完成时 间和下界)的结点作为当前扩展结点,并加以扩展。 首先考虑enode.s=n的情形,当前扩展结点enode是排列树中的 叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx。 当enode.s
/
本文档为【第6章 分支限界法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索