计算机算法设计与分析第4版第6章高教书苑.ppt

第6章 分支限界法1高级教育·学习要点学习要点·理解分支限界法的剪枝搜索策略·掌握分支限界法的算法框架·（1）队列式(FIFO)分支限界法·（2）优先队列式分支限界法 ·通过应用范例学习分支限界法的设计策略·（1）单源最短路径问题·（2）装载问题；·（3）布线问题·（4）0-1背包问题；·（5）最大团问题；·（6）旅行售货员问题·（7）电路板排列问题·（8）批处理作业调度问题2高级教育6.1 分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树 3高级教育6.1 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程这个过程一直持续到找到所需的解或活结点表为空时为止 在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中4高级教育6.1 分支限界法的基本思想常见的两种分支限界法（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点5高级教育6.2 单源最短路径问题1. 问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权要求图G的从源顶点s到目标顶点t之间的最短路径 6高级教育6.2 单源最短路径问题1. 问题描述 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树其中，每一个结点旁边的数字表示该结点所对应的当前路长7高级教育6.2 单源最短路径问题2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表其优先级是结点所对应的当前路长 算法从图G的源顶点s和空优先队列开始结点s被扩展后，它的儿子结点被依次插入堆中。

此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中这个结点的扩展过程一直继续到活结点优先队列为空时为止8高级教育6.2 单源最短路径问题3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树 在算法中，利用结点间的控制关系进行剪枝从源顶点s出发，2条不同路径到达图G的同一顶点由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去 9高级教育6.2 单源最短路径问题 while (true) { for (int j = 1; j <= n; j++) if ((c[E.i][j] N; N.i=j; N.length=dist[j]; H.Insert(N);} try {H.DeleteMin(E);} // 取下一扩展结点 catch (OutOfBounds) {break;} // 优先队列空 }} 顶点顶点I I和和j j间有边，且此间有边，且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 10高级教育6.3 装载问题1. 问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。

如果有，找出一种装载方案 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船 11高级教育6.3 装载问题2. 队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点如果是则将其加入到活结点队列中然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)2个儿子结点都产生后，当前扩展结点被舍弃 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空当取出的元素是-1时，再判断当前队列是否为空如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点12高级教育6.3 装载问题2. 队列式分支限界法while (true) { // 检查左儿子结点 if (Ew + w[i] <= c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n); // 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++;} // 进入下一层 } }13高级教育6.3 装载问题3. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。

设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值14高级教育6.3 装载问题3. 算法的改进// 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 if (wt <= c) { // 可行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) Q.Add(wt);}提前更新提前更新bestw bestw // 检查右儿子结点 if (Ew + r > bestw && i < n) Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点右儿子剪枝右儿子剪枝 15高级教育6.3 装载问题4. 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。

为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志 class QNode {QNode *parent; // 指向父结点的指针 bool LChild; // 左儿子标志 Type weight; // 结点所相应的载重量16高级教育6.3 装载问题找到最优值后，可以根据parent回溯到根节点，找到最优解4. 构造最优解// 构造当前最优解for (int j = n - 1; j > 0; j--) { bestx[j] = bestE->LChild; bestE = bestE->parent; }17高级教育6.3 装载问题5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和 优先队列中优先级最大的活结点成为下一个扩展结点以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级子集树中叶结点所相应的载重量与其优先级相同 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。

此时可终止算法 18高级教育6.4 布线问题1. 算法思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1 接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止即加入剪枝的广度优先搜索19高级教育6.4 布线问题Position offset[4]; offset[0].row = 0; offset[0].col = 1; // 右 offset[1].row = 1; offset[1].col = 0; // 下 offset[2].row = 0; offset[2].col = -1; // 左 offset[3].row = -1; offset[3].col = 0; // 上定义移动方向的定义移动方向的相对位移相对位移 for (int i = 0; i <= m+1; i++) grid[0][i] = grid[n+1][i] = 1; // 顶部和底部 for (int i = 0; i <= n+1; i++) grid[i][0] = grid[i][m+1] = 1; // 左翼和右翼设置边界的围墙设置边界的围墙20高级教育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.Add(nbr);} }找到目标位置后，可以通过回溯方法找到这条最短路径。

21高级教育6.5 0-1背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和 算法首先检查当前扩展结点的左儿子结点的可行性如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列当扩展到叶节点时为问题的最优值22高级教育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为上界函数23高级教育6.5 0-1背包问题 while (i != n+1) {// 非叶结点 // 检查当前扩展结点的左儿子结点 Typew wt = cw + w[i]; if (wt <= c) {// 左儿子结点为可行结点 if (cp+p[i] > bestp) bestp = cp+p[i]; AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);} up = Bound(i+1); // 检查当前扩展结点的右儿子结点 if (up >= bestp) // 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); // 取下一个扩展节点（略）}分支限界搜索过分支限界搜索过程程24高级教育6.6 最大团问题 给定无向图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的最大团 1. 问题描述25高级教育6.6 最大团问题2. 上界函数用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值 在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素 26高级教育6.6 最大团问题3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0 算法在扩展内部结点时，首先考察其左儿子结点在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。

当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点 接 着 继 续 考 察 当 前 扩 展 结 点 的 右 儿 子 结 点 当upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中27高级教育6.6 最大团问题3. 算法思想 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点 对于子集树中的叶结点，有upperSize＝cliqueSize此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解 28高级教育6.7 旅行售货员问题1. 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小 路线是一个带权图图中各边的费用（权）为正数图的一条周游路线是包括V中的每个顶点在内的一条回路。

周游路线的费用是这条路线上所有边的费用之和 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线旅行售货员问题要在图G中找出费用最小的周游路线 29高级教育6.7 旅行售货员问题2. 算法描述 算法开始时创建一个最小堆，用于表示活结点优先队列堆中每个结点的子树费用的下界lcost值是优先队列的优先级接着算法计算出图中每个顶点的最小费用出边并用minout记录如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束如果每个顶点都有出边，则根据计算出的minout作算法初始化 算法的while循环体完成对排列树内部结点的扩展对于当前扩展结点，算法分2种情况进行处理：30高级教育6.7 旅行售货员问题2. 算法描述 1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点 2、当s

对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost当lcost

计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解 当s 0 && total[j] != N.now[j]) ld++; N.cd = max(ld, E.cd); if (N.cd < bestd) {// 可能产生更好的叶结点 N.x = new int [n+1]; N.s = E.s + 1; for (int j = 1; j <= n; j++) N.x[j] = E.x[j]; N.x[N.s] = E.x[i]; N.x[i] = E.x[N.s]; H.Insert(N);} else delete [] N.now;} delete [] E.x;}算法描述计算出每一个儿子结点的计算出每一个儿子结点的密度与密度与bestdbestd进行比较大进行比较大于于bestdbestd时加入队列时加入队列36高级教育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个作业，制定最佳作业调度方案，使其完成时间和达到最小37高级教育6.9 批处理作业调度问题2. 限界函数在结点E处相应子树中叶结点完成时间和的下界是：注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值同理如果选择Pk使t2pk依非减序排列，则S2取得极小值 这可以作为优先队列式分支限界法中的限界函数 38高级教育6.9 批处理作业调度问题3. 算法描述 算法的while循环完成对排列树内部结点的有序扩展在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展 首先考虑E.s=n的情形，当前扩展结点E是排列树中的叶结点E.sf2是相应于该叶结点的完成时间和当E.sf2 < bestc时更新当前最优值bestc和相应的当前最优解bestx。

当E.s