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+rbestw时,可将其右子
树剪去,因为此时若要船装最多集装箱,就应该把此箱装上船。
另外,为了确保右子树成功剪枝,应该在算法每一次进入左
子树的时候更新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)。如果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的最大团。
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