第6讲分支界限法分析课件.ppt

第第1 1页页第第6章章 分支限界法分支限界法1 1广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2 2页页·学习要点学习要点·理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略·掌握分支限界法的算法框架掌握分支限界法的算法框架·（（1）队列式）队列式(FIFO)分支限界法分支限界法·（（2）优先队列式分支限界法）优先队列式分支限界法 2 2广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3 3页页学习要点学习要点·通过应用范例学习分支限界法的设计策略通过应用范例学习分支限界法的设计策略·（（1）单源最短路径问题）单源最短路径问题·（（2）装载问题；）装载问题；·（（3）布线问题）布线问题·（（4））0-1背包问题；背包问题；·（（5）最大团问题；）最大团问题；·（（6）旅行售货员问题）旅行售货员问题·（（7）电路板排列问题）电路板排列问题·（（8）批处理作业调度问题）批处理作业调度问题3 3广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4 4页页6.1分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法分支限界法与回溯法（（1）求解目标：）求解目标：回溯法的求解目标是找出解空间树回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

束条件的解中找出在某种意义下的最优解 （（2）搜索方式的不同：）搜索方式的不同：回溯法以深度优先的方式回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树小耗费优先的方式搜索解空间树 4 4广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5 5页页6.1分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树效益）优先的方式搜索问题的解空间树 此后，从活结点表中取下一结点成为当前扩展此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程这个过程一直持结点，并重复上述结点扩展过程这个过程一直持续到找到所需的解或活结点表为空时为止续到找到所需的解或活结点表为空时为止 在分支限界法中，每一个活结点只有一次机会成在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产为扩展结点活结点一旦成为扩展结点，就一次性产生其所有儿子结点在这些儿子结点中，导致不可行生其所有儿子结点在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中被加入活结点表中5 5广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第6 6页页6.1分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法常见的两种分支限界法（（1 1）队列式）队列式( (FIFO)FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO））原则选取下一原则选取下一个节点为扩展节点个节点为扩展节点 （（2 2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点最高的节点成为当前扩展节点。

6 6广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第7 7页页6.2单源最短路径问题单源最短路径问题1. 问题描述问题描述 下面以一个例子来说明单源最短路径问题：下面以一个例子来说明单源最短路径问题：在在下图所给的有向图下图所给的有向图G G中，每一边都有一个非负边权中，每一边都有一个非负边权要求图要求图G G的从源顶点的从源顶点s s到目标顶点到目标顶点t t之间的最短路径之间的最短路径 7 7广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第8 8页页6.2单源最短路径问题单源最短路径问题1. 问题描述问题描述 下图是用优先队列式分支限界法解有向图下图是用优先队列式分支限界法解有向图G G的单的单源最短路径问题产生的解空间树。

其中，每一个结点源最短路径问题产生的解空间树其中，每一个结点旁边的数字表示该结点所对应的当前路长旁边的数字表示该结点所对应的当前路长8 8广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第9 9页页2. 算法思想算法思想 解单源最短路径问题的优先队列式分支限界法用解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表其优先级是结点所对应的一极小堆来存储活结点表其优先级是结点所对应的当前路长当前路长 算法从图算法从图G G的源顶点的源顶点s s和空优先队列开始结点和空优先队列开始结点s s被扩被扩展后，它的儿子结点被依次插入堆中此后，算法从堆展后，它的儿子结点被依次插入堆中此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点如果从当前依次检查与当前扩展结点相邻的所有顶点如果从当前扩展结点扩展结点i i到顶点到顶点j j有边可达，且从源出发，途经顶点有边可达，且从源出发，途经顶点i i再再到顶点到顶点j j的所相应的路径的长度小于当前最优路径长度，的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

这个则将该顶点作为活结点插入到活结点优先队列中这个结点的扩展过程一直继续到活结点优先队列为空时为止结点的扩展过程一直继续到活结点优先队列为空时为止9 9广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1010页页3. 剪枝策略剪枝策略 在在算算法法扩扩展展结结点点的的过过程程中中，，一一旦旦发发现现一一个个结结点点的的下下界界不不小小于于当当前前找找到到的的最最短短路路长长，，则则算算法法剪剪去去以以该该结结点为根的子树点为根的子树 在在算算法法中中，，利利用用结结点点间间的的控控制制关关系系进进行行剪剪枝枝从从源源顶顶点点s s出出发发，，2 2条条不不同同路路径径到到达达图图G G的的同同一一顶顶点点由由于于两两条条路路径径的的路路长长不不同同，，因因此此可可以以将将路路长长长长的的路路径径所所对对应的树中的结点为根的子树剪去应的树中的结点为根的子树剪去 1010广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1111页页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的路径长的路径长 1111广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1212页页6.3 装载问题装载问题1. 问题描述有有一一批批共共个个集集装装箱箱要要装装上上2 2艘艘载载重重量量分分别别为为C1C1和和C2C2的的轮轮船船，，其中集装箱其中集装箱i i的重量为的重量为WiWi，，且且装载问题要求确定是否有一个合理的装载方案可将这装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这个集装箱装上这2 2艘轮船。

如果有，找出一种装载方案如果有，找出一种装载方案 容容易易证证明明：：如如果果一一个个给给定定装装载载问问题题有有解解，，则则采采用用下下面面的策略可得到最优装载方案的策略可得到最优装载方案 (1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船将剩余的集装箱装上第二艘轮船 1212广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1313页页6.3 装载问题装载问题2. 队列式分支限界法队列式分支限界法 在在算算法法的的whilewhile循循环环中中，，首首先先检检测测当当前前扩扩展展结结点点的的左左儿儿子子结结点点是是否否为为可可行行结结点点如如果果是是则则将将其其加加入入到到活活结结点点队队列列中中然然后后将将其其右右儿儿子子结结点点加加入入到到活活结结点点队队列列中中( (右右儿儿子子结结点点一一定定是是可可行行结结点点) )2 2个个儿儿子子结结点点都都产产生生后后，，当前扩展结点被舍弃。

当前扩展结点被舍弃 活活结结点点队队列列中中的的队队首首元元素素被被取取出出作作为为当当前前扩扩展展结结点点，，由由于于队队列列中中每每一一层层结结点点之之后后都都有有一一个个尾尾部部标标记记-1-1，，故故在在取取队队首首元元素素时时，，活活结结点点队队列列一一定定不不空空当当取取出出的的元元素素是是-1-1时时，，再再判判断断当当前前队队列列是是否否为为空空如如果果队队列列非非空空，，则则将将尾尾部部标标记记-1-1加加入入活活结结点点队队列列，，算算法法开开始始处处理理下下一一层层的的活活结点1313广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1414页页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++;} // 进入下一层进入下一层 } }1414广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1515页页6.3 装载问题装载问题3. 算法的改进算法的改进 节点的左子树表示将此集装箱装上船，右子树表示节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。

设不将此集装箱装上船设bestwbestw是当前最优解；是当前最优解；ewew是当是当前扩展结点所相应的重量；前扩展结点所相应的重量；r r是剩余集装箱的重量则是剩余集装箱的重量则当当ew+rew+r bestwbestw时，可将其右子树剪去，因为此时若要时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船船装最多集装箱，就应该把此箱装上船 另外，为了确保右子树成功剪枝，应该在算法每另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新一次进入左子树的时候更新bestwbestw的值1515广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1616页页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); // 取下一扩展结点取下一扩展结点右儿子剪右儿子剪枝枝 1616广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1717页页6.3 装载问题装载问题4. 构造最优解构造最优解 为了在算法结束后能方便地构造出与最优值相应为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根的最优解，算法必须存储相应子集树中从活结点到根结点的路径。

为此目的，可在每个结点处设置指向其结点的路径为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志父结点的指针，并设置左、右儿子标志 class QNode { QNode *parent; // 指向父结点的指针指向父结点的指针 bool LChild; // 左儿子标志左儿子标志 Type weight; // 结点所相应的载重量结点所相应的载重量1717广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1818页页找到最优值后，可以根据找到最优值后，可以根据parentparent回溯到根节点，找回溯到根节点，找到最优解到最优解4. 构造最优解构造最优解// 构造当前最优解构造当前最优解for (int j = n - 1; j > 0; j--) { bestx[j] = bestE->LChild; bestE = bestE->parent; }1818广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1919页页6.3 装载问题装载问题5. 优先队列式分支限界法优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。

活结点列存储活结点表活结点x x在优先队列中的优先级定义为在优先队列中的优先级定义为从根结点到结点从根结点到结点x x的路径所相应的载重量再加上剩余集装的路径所相应的载重量再加上剩余集装箱的重量之和箱的重量之和 优先队列中优先级最大的活结点成为下一个扩展结优先队列中优先级最大的活结点成为下一个扩展结点以结点点以结点x x为根的子树中所有结点相应的路径的载重量为根的子树中所有结点相应的路径的载重量不超过它的优先级子集树中叶结点所相应的载重量与不超过它的优先级子集树中叶结点所相应的载重量与其优先级相同其优先级相同 在优先队列式分支限界法中，一旦有一个叶结点成在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为为当前扩展结点，则可以断言该叶结点所相应的解即为最优解此时可终止算法此时可终止算法 1919广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2020页页6.4 布线问题布线问题1. 算法思想算法思想 解解此此问问题题的的队队列列式式分分支支限限界界法法从从起起始始位位置置a a开开始始将将它它作作为为第第一一个个扩扩展展结结点点。

与与该该扩扩展展结结点点相相邻邻并并且且可可达达的的方方格格成成为为可可行行结结点点被被加加入入到到活活结结点点队队列列中中，，并并且且将将这这些些方方格标记为格标记为1 1，即从起始方格，即从起始方格a a到这些方格的距离为到这些方格的距离为1 1 接接着着，，算算法法从从活活结结点点队队列列中中取取出出队队首首结结点点作作为为下下一一个个扩扩展展结结点点，，并并将将与与当当前前扩扩展展结结点点相相邻邻且且未未标标记记过过的的方方格格标标记记为为2 2，，并并存存入入活活结结点点队队列列这这个个过过程程一一直直继继续续到到算算法法搜搜索索到到目目标标方方格格b b或或活活结结点点队队列列为为空空时时为为止止即即加加入入剪剪枝的广度优先搜索枝的广度优先搜索2020广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2121页页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; // 左翼和右翼左翼和右翼设置边界的设置边界的围墙围墙2121广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2222页页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);} }找到目标位置找到目标位置后，可以通过后，可以通过回溯方法找到回溯方法找到这条最短路径。

这条最短路径2222广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2323页页6.5 0-1背包问题背包问题算法的思想算法的思想 首先，要对输入数据进行预处理，将各物品依其单首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列节点的优先级由已装袋位重量价值从大到小进行排列节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和余容量的价值和 算法首先检查当前扩展结点的左儿子结点的可行算法首先检查当前扩展结点的左儿子结点的可行性如果该左儿子结点是可行结点，则将它加入到子性如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中当前扩展结点的右儿子结集树和活结点优先队列中当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。

当扩展到叶节才将它加入子集树和活结点优先队列当扩展到叶节点时为问题的最优值点时为问题的最优值2323广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2424页页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为上界函数为上界函数2424广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2525页页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); // 取下一个扩展节点（略）取下一个扩展节点（略）}分支限界搜分支限界搜索过程索过程2525广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2626页页分支限界法解分支限界法解0-1背包问题背包问题n=3,w=[16,15,15],p=[45,25,25],c=30FIFO队列：队列：A活结点队列： { }BC{B,C}DEJKFGLMNO{C,E}{E,F,G}{F,G}{G}{ }4550252502626广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2727页页 一般情况下，解空间树中第一般情况下，解空间树中第i层的每个结点，都代表了对物层的每个结点，都代表了对物品品1～～i做出的某种特定选择，这个特定选择由从根结点到该结做出的某种特定选择，这个特定选择由从根结点到该结点的路径唯一确定：左分支表示装入物品，右分支表示不装入点的路径唯一确定：左分支表示装入物品，右分支表示不装入物品。

对于第物品对于第i层的某个结点，假设背包中已装入物品的重量是层的某个结点，假设背包中已装入物品的重量是w，获得，获得的价值是的价值是v，计算该结点的目标函数上界的一个简单方，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值法是把已经装入背包中的物品取得的价值v，加上背包剩余容量，加上背包剩余容量c-w与剩下物品的最大单位重量价值与剩下物品的最大单位重量价值vi+1/wi+1的积，于是，得到限的积，于是，得到限界函数：界函数： 2727广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2828页页分支限界法解分支限界法解0-1背包问题背包问题n=3,w=[16,15,15],p=[45,25,25],c=30FIFO队列，带上界函数。

队列，带上界函数A活结点队列： { }BC{B,C}DEJKFGLM{C,E}{E,F,G}{F,G}{G}{ }45502568.3>050>068.3>050>4525<502828广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2929页页分支限界法解分支限界法解0-1背包问题背包问题n=3,w=[16,15,15],p=[45,25,25],c=30价值大者优先队列：价值大者优先队列：A活结点队列： { }BC{B,C}DEJKFGLMNO{E,C}{C}{F,G}{G}{ }455025250454525002929广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3030页页分支限界法解分支限界法解0-1背包问题背包问题n=3,w=[16,15,15],p=[45,25,25],c=30价值上界大者优先队列，带上界函数。

价值上界大者优先队列，带上界函数A活结点队列： { }BC{B,C}DEJKFGLM{E,C}{C,K}{F,K,G}{L,K,G}L为叶子结点，算法结束455068.368.3505068.3>4550>4545=4525<50253030广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3131页页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. 问题描述3131广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3232页页6.6 最大团问题最大团问题2. 上界函数用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。

在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素 3232广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3333页页6.6 最大团问题最大团问题3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0 算法在扩展内部结点时，首先考察其左儿子结点在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点 接 着 继 续 考 察 当 前 扩 展 结 点 的 右 儿 子 结 点 当upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。

3333广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3434页页6.6 最大团问题最大团问题3. 算法思想 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点 对于子集树中的叶结点，有upperSize＝cliqueSize此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解 3434广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3535页页6.7 旅行售货员问题旅行售货员问题1. 问题描述问题描述 某售货员要到若干城市去推销商品，已知各城市之间的某售货员要到若干城市去推销商品，已知各城市之间的路程路程( (或旅费或旅费) )。

他要选定一条从驻地出发，经过每个城市一他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程次，最后回到驻地的路线，使总的路程( (或总旅费或总旅费) )最小 路线是一个带权图图中各边的费用（权）为正数图路线是一个带权图图中各边的费用（权）为正数图的一条周游路线是包括的一条周游路线是包括V V中的每个顶点在内的一条回路周中的每个顶点在内的一条回路周游路线的费用是这条路线上所有边的费用之和游路线的费用是这条路线上所有边的费用之和 旅行售货员问题的解空间可以组织成一棵树，从树的根旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线旅行售结点到任一叶结点的路径定义了图的一条周游路线旅行售货员问题要在图货员问题要在图G G中找出费用最小的周游路线中找出费用最小的周游路线 3535广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3636页页6.7 旅行售货员问题旅行售货员问题2. 算法描述算法描述 算法开始时创建一个最小堆，用于表示活结点优先算法开始时创建一个最小堆，用于表示活结点优先队列。

堆中每个结点的子树费用的下界队列堆中每个结点的子树费用的下界lcostlcost值是优先队值是优先队列的优先级接着算法计算出图中每个顶点的最小费用列的优先级接着算法计算出图中每个顶点的最小费用出边并用出边并用minoutminout记录如果所给的有向图中某个顶点没记录如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束如果每有出边，则该图不可能有回路，算法即告结束如果每个顶点都有出边，则根据计算出的个顶点都有出边，则根据计算出的minoutminout作算法初始化作算法初始化 算法的算法的whilewhile循环体完成对排列树内部结点的扩展对循环体完成对排列树内部结点的扩展对于当前扩展结点，算法分于当前扩展结点，算法分2 2种情况进行处理：种情况进行处理：3636广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3737页页6.7 旅行售货员问题旅行售货员问题2. 算法描述算法描述 1 1、首先考虑、首先考虑s=n-2s=n-2的情形，此时当前扩展结点是排的情形，此时当前扩展结点是排列树中某个叶结点的父结点。

如果该叶结点相应一条可列树中某个叶结点的父结点如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点优先队列中，否则舍去该叶结点 2 2、当、当s

先队列中 3737广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3838页页6.7 旅行售货员问题旅行售货员问题2. 算法描述算法描述 算法中算法中whilewhile循环的终止条件是排列树的一个叶结点循环的终止条件是排列树的一个叶结点成为当前扩展结点当成为当前扩展结点当s=n-1s=n-1时，已找到的回路前缀是时，已找到的回路前缀是x[0:n-1]x[0:n-1]，，它已包含图它已包含图G G的所有的所有n n个顶点因此，当个顶点因此，当s=n-s=n-1 1时，相应的扩展结点表示一个叶结点此时该叶结点时，相应的扩展结点表示一个叶结点此时该叶结点所相应的回路的费用等于所相应的回路的费用等于cccc和和lcostlcost的值剩余的活结的值剩余的活结点的点的lcostlcost值不小于已找到的回路的费用它们都不可值不小于已找到的回路的费用它们都不可能导致费用更小的回路因此已找到的叶结点所相应的能导致费用更小的回路。

因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束回路是一个最小费用旅行售货员回路，算法可以结束 算法结束时返回找到的最小费用，相应的最优解由算法结束时返回找到的最小费用，相应的最优解由数组数组v v给出 3838广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3939页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654FIFO队列：队列：活结点队列： { }BCDEGIKFHJMOQLNP222223333344444592525666659{C,D,E }{D,E,F,G}{E,F,G,H,I }{F,G,H,I,J,K }{G,H,I,J,K }{H,I,J,K }{I,J,K }{J,K }{K }{ }3939广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4040页页某某条条路路径径的的一一些些边边被被确确定定后后，，就就可可以以并并入入这这些些信信息息并并计计算算部部分分解解的的目目标标函函数数值值的的下下界界。

一一般般情情况况下下，，对对于于一一个个正正在在生生成成的的路路径径，，假假设设已已确确定定的的顶顶点点集集合合U=(r1, r2, …, rk)，，即即路路径径上上已已确确定了定了k个顶点个顶点 该部分解的目标函数值的计算方法如下：该部分解的目标函数值的计算方法如下： 4040广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4141页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654FIFO队列，带下界函数队列，带下界函数活结点队列： { }BCDEGIKFHJMLNP222333334444459252566{C,D,E }{D,E,F,G}{E,F,G,H,I }{F,G,H,I,J,K }{G,H,I,J,K }{H,I,J,K }{I,J,K }{J,K }{K }{ }44<10120<10118<10144<10149<5920<5935>2524<2534>254141广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4242页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654最小费用优先队列：最小费用优先队列：活结点队列： { }BCDEGIKFHJMOQLNP2222233333444443064402624351114592525666659{E,D,C }{D,J,K,C }{H,J,K,I,C }{J,K,I,C }{K,I,C }{I,C }{C }{F,G }{G }{ }4242广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4343页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654最小费用优先队列，带下界函数。

最小费用优先队列，带下界函数活结点队列： { }CDEIKHJNP2223334443064262411142525{E,D,C }{D,J,K,C }{H,J,K,I,C }{J,K,N,I,C }{K,N,P,I,C }{N,P,I,C}18<10120<10120<10124<2534>25N为叶结点，结束B4343广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4444页页6.8 电路板排列问题电路板排列问题算法描述算法描述 算法开始时，将排列树的根结点置为当前扩展结点算法开始时，将排列树的根结点置为当前扩展结点在在do-whiledo-while循环体内算法依次从活结点优先队列中取出循环体内算法依次从活结点优先队列中取出具有最小具有最小cdcd值的结点作为当前扩展结点，并加以扩展值的结点作为当前扩展结点，并加以扩展 首先考虑首先考虑s=n-1s=n-1的情形，当前扩展结点是排列树中的的情形，当前扩展结点是排列树中的一个叶结点的父结点。

一个叶结点的父结点x x表示相应于该叶结点的电路板排表示相应于该叶结点的电路板排列计算出与列计算出与x x相应的密度并在必要时更新当前最优值和相应的密度并在必要时更新当前最优值和相应的当前最优解相应的当前最优解 当当s

比较4545广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4646页页6.8 电路板排列问题电路板排列问题算法描述算法描述else {// 产生当前扩展结点的所有儿子结点产生当前扩展结点的所有儿子结点 for (int i = E.s + 1; i <= n; i++) { BoardNode N; N.now = new int [m+1]; for (int j = 1; j <= m; j++) // 新插入的电路板新插入的电路板 N.now[j] = E.now[j] + B[E.x[i]][j]; 4646广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4747页页6.8 电路板排列问题电路板排列问题int ld = 0; // 新插入电路板的密度 for (int j = 1; j <= m; j++) if (N.now[j] > 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时加入队列时加入队列4747广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4848页页6.9 批处理作业调度问题批处理作业调度问题1. 问题的描述问题的描述 给定给定n n个作业的集合个作业的集合J={J1,J2,…,Jn}J={J1,J2,…,Jn}。

每一个作业每一个作业JiJi都有都有2 2项任务要分别在项任务要分别在2 2台机器上完成每一个作业必须台机器上完成每一个作业必须先由机器先由机器1 1处理，然后再由机器处理，然后再由机器2 2处理作业处理作业JiJi需要机器需要机器j j的处理时间为的处理时间为tjitji，，i=1,2,…,ni=1,2,…,n；；j=1,2j=1,2对于一个确定对于一个确定的作业调度，设是的作业调度，设是FjiFji是作业是作业i i在机器在机器j j上完成处理的时间上完成处理的时间则所有作业在机器则所有作业在机器2 2上完成处理的时间和上完成处理的时间和 称为该作业调度的完成时间和批处理作业调度问题称为该作业调度的完成时间和批处理作业调度问题要求对于给定的要求对于给定的n n个作业，制定最佳作业调度方案，使其个作业，制定最佳作业调度方案，使其完成时间和达到最小完成时间和达到最小4848广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4949页页6.9 批处理作业调度问题批处理作业调度问题2. 限界函数限界函数在结点在结点E E处相应子树中叶结点完成时间和的下界是：处相应子树中叶结点完成时间和的下界是：注意到如果选择注意到如果选择PkPk，，使使t1pkt1pk在在k>=r+1k>=r+1时依非减序排列，时依非减序排列，S1S1则取得极小值则取得极小值。

同理如果选择同理如果选择PkPk使使t2pkt2pk依非减序排列，依非减序排列，则则S2S2取得极小值取得极小值 这可以作为优先队列式分支限界法中的限界函数这可以作为优先队列式分支限界法中的限界函数 4949广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5050页页6.9 批处理作业调度问题批处理作业调度问题3. 算法描述算法描述 算法的算法的whilewhile循环完成对排列树内部结点的有序扩展循环完成对排列树内部结点的有序扩展在在whilewhile循环体内算法依次从活结点优先队列中取出具有循环体内算法依次从活结点优先队列中取出具有最小最小bbbb值（完成时间和下界）的结点作为当前扩展结点，值（完成时间和下界）的结点作为当前扩展结点，并加以扩展并加以扩展 5050广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5151页页6.9 批处理作业调度问题批处理作业调度问题3. 算法描述算法描述 首先考虑首先考虑E.s=nE.s=n的情形，当前扩展结点的情形，当前扩展结点E E是排列树中的是排列树中的叶结点。

叶结点E.sf2E.sf2是相应于该叶结点的完成时间和当是相应于该叶结点的完成时间和当E.sf2 E.sf2 < bestc< bestc时更新当前最优值时更新当前最优值bestcbestc和相应的当前最优解和相应的当前最优解bestxbestx 当当E.s