《算法设计与分析》课件第6章

第6章分枝限界法6.1分枝限界法的基本思想

6.2

0-1背包问题

6.3作业调度问题

习题

6.1分枝限界法的基本思想

如果把回溯法看做深度优先搜索解空间树的过程，那么分枝限界法则可看做广度优先或者按照最大价值(或最小成本)搜索解空间树的过程。它也是一种系统地搜索问题解的方法。按照从活结点表中选择扩展结点的方法，分枝限界法又可细分为以下两种：

(1)先进先出(FirstInFirstOut，FIFO)分枝限界法(FIFOBB)。

(2)优先队列(PriorityQueue，PQ)分枝限界法(PQBB)。我们以0-1背包问题为例，讨论这两种分枝限界法的异同。某商店有n个物品，第i个物品价值为vi，容量(或称权值)为wi，其中vi和wi为非负数。背包的容量为W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大。这个问题的形式描述如下：

约束条件为

1．先进先出状态空间树

对于0-1背包问题，结点X处的估值函数 定义为 ，其中k表示结点X所在的层。用队列作为组织活结点表的数据结构，按照结点进入队列的先后顺序选择下一个扩展结点，得到0-1背包问题先进先出状态空间树，如图6-1所示。图6-1先进先出状态空间树

2．优先队列状态空间树

当用优先队列作为组织活结点表的数据结构，并按照结点估值函数值的大小选择下一个扩展结点时，就得到0-1背包问题优先队列状态空间树，如图6-2所示。图6-2优先队列状态空间树正如在回溯法中所做的那样，我们可以设计一个限界函数，以减少解空间的大小，加速搜索的速度。这个限界函数给出每一个可行结点对应子树可能得到的最小成本(最大价值)的下界(上界)，如果这个下界(上界)不小于(不大于)当前最优解的值，则说明这个结点对应的子树中不含问题的最优解，因而可以剪掉。此外，我们也可以将限界函数确定的每个结点的下界(上界)值作为优先级，并以该优先级的大小作为选择当前E结点的原则。这种策略有时可以更快地找到问题的最优解。

6.2

0-1背包问题

1．限界

设T是一棵状态空间树，c(*)是T中结点的成本函数。如果X是T中的一个结点，则c(X)是其根为X的子树中任一答案结点的最小成本。这个c(*)是难于构造的，通常使用一个对c(*)估值的启发式函数l(*)来代替，这个启发式函数易于计算：如果X是一个答案结点或一个叶结点，则c(*)=l(*)。搜索问题状态空间树的各种分枝限界法都是在生成当前E结点的所有子结点之后再将另一结点变成E结点的。假定每个答案结点X有一个与其相联系的c(X)，并且假定会找到最小成本的答案结点，利用一个满足l(X)≤c(X)的成本估值函数l(X)则可以给出任一结点X解的下界。采用下界函数可以减少搜索的盲目性，此外还可通过设置最小成本上界使算法进一步加速。如果Up是最小成本解的成本上界，则满足l(X)>Up的所有活结点都可以被杀死，这是因为由X到达的

所有答案结点都满足c(X)≥l(X)>Up。在已经到达一个具有成本Up的答案结点的情况下，那些满足l(X)>Up的所有活结点都可以被杀死。Up的初始值可以用某种启发式算法得到,也可以设置成∞。只要Up的初始值不小于最小成本结点的成本，上述杀死活结点的规则就不会杀死可以到达最小成本答案结点的活结点。每当找到一个新的答案结点时，就可以修改Up的值，即如果某个结点的上界u(X)<Up，则用该结点的上界u(X)更新Up。根据上述思想，我们考虑最小值优化问题的分枝限界法。为了找问题的最优解，需要将最优解的搜索表示成对状态空间树答案结点的搜索，可将问题最优答案结点的成本函数定义为所有结点成本的最小值。简单的方法是直接将目标函数作为成本函数c(*)。在这种定义下，可行解结点的c(X)就是那个结点可行解的目标函数值，不可行结点的c(X)为+∞，部分解结点的c(X)是以X为根的子树中结点的最小成本。

2．定义结点的限界函数

通过构造和设计结点处的限界函数，可以减小问题的状态搜索空间。为了讨论方便起见，我们将最大值优化问题转变成最小值优化问题。如果用目标函数－ 替代目标函数 ，就使背包问题从一个最大值优化问题变成最小值优化问题。显然， 取最小即 取最大。重新定义了目标函数之后，背包问题描述如下：(6.1)约束条件为

式(6.1)中各量的意义同6.1节。UPBOUND(cv,cw,k-1,W)

1 b

cv

2 c

cw

3 for

i

k

to

n

do

4

ifc+w[i]

W

5

then

c

c+w[i]

6 b

b–v[i]

7 return(b)

3．0-1背包问题优先队列分枝限界法示例

对于上述构造的限界函数l(X)和u(X)，再次考虑6.1节的0-1背包问题实例。用优先队列作为组织活结点表的数据结构，并按照结点l(X)值的大小选择下一个扩展结点，得到0-1

背包问题优先队列分枝限界树，如图6-3所示。图6-3

0-1背包问题优先队列分枝限界树

4．算法中使用的主要数据结构及变量

由此可见，通过限界函数，大大减小了问题的搜索空间，提高了算法的效率。但另一方面，仅从路径10,7,4,2,1不能确定哪些物品装入背包，使得－∑vixi=Up,即不能确定装入背包中物品xi的取值情况。因此，在实现中，需通过设置一些变量来记录xi的取值信息。一种办法是在每一个结点上增设一个标志域Tag，由答案结点到根结点的这些标志域给出xi的取值信息。

1)结点的结构

结点结构取决于用定长元组表示状态空间树，还是用变长元组表示状态空间树。这里仍然采用定长元组表示。活结点表中的每一个结点都有六个域的信息，如图6-4所示。图6-4结点的数据结构

2)扩展给定E结点的子结点

利用结点数据结构中的信息，可以确定任一活结点X的两个子结点。当且仅当CW(X)≥wLevel(X)时，X的左孩子Y是可行结点，可以生成结点Y，在这种情况下，有

Parent(Y)=X，Level(Y)=Level(X)+1

CW(Y)=CW(X)–wLevel(X)，CV(Y)=CV(X)+vLevel(X)

Tag(Y)=1，UB(Y)=UB(X)

当CW(X)<wLevel(X)时，生成X的右孩子Y，在这种情况下，有

Parent(Y)=X，Level(Y)=Level(X)+1

CW(Y)=CW(X)，CV(Y)=CV(X)，Tag(Y)=0

3)识别答案结点

答案结点的识别比较容易，当且仅当Level(X)=n+1时，X是答案结点。

4)活结点表的数据结构

采用优先队列作为组织活结点表的数据结构。需要在优先队列上执行三个操作：判定优先队列是否为空、向优先队列中插入结点(类似于过程INSERT，见4.4节)和从优先队列中摘取具有最小l(X)值的结点(类似于过程EXTRACT-MIN，见4.4节)。我们用最小堆实现优先队列数据结构，如果堆中有n个结点，则判断优先队列是否为空的操作可在常数时间

O(1)内完成，插入操作和摘取操作的运行时间为O(lbn)，因为这两个操作不会超过树的深度O(lbn)。详细的分析见4.4节。

5．0-1背包问题优先队列分枝限界算法

在过程PQBB中，调用6个子过程，分别是LUBOUND、INSERTNODE、PRINT、INIT、GETNODE和EXTRACT-MAX。过程LUBOUND用于计算－l(X)和－u(X)。INSERTNODE生成一个6个数据域的结点，并对各个域进行赋值，最后插入到活结点表中。算法PRINT输出问题最优解

的值和最优解。算法INIT对可用结点表和活结点表初始化。算法GETNODE取一个可用结点。算法EXTRACT-MAX从活结点表中摘取一个具有最大UB值的结点作为E结点，用最大堆实现时即摘取堆顶结点。LUBOUND(v,w,cw,cv,

n,k,LBB,UBB)

//cw表示背包可用权值，cv表示已得价值，LBB=–u(X)，UBB=–l(X)

1 LBB

cv

2 c

cw

3 fori

k

to

n

do

4

ifc<w[i]

5

thenUBB

LBB+c

v[i]/w[i]

6

forj

i+1tondo

7

if

c

w[j]

8

then

c

c–w[i]

9

LBB

LBB+v[j]

10

return

11 c

c–w[i]

12

LBB

LBB+v[i]

13 UBB

LBBINSERTNODE(par,lev,t,cap,valu,ub)

1 GETNODE(Node)//生成一个新结点Node

2 Parent(Node)

par

3 Level(Node)

lev

4 Tag(Node)

t

5 CW(Node)

cap

6 CV(Node)

valu

7 ADD(Node) PRINT(Lower,ans,n)

1 print(''valueofoptimalsolutionis'',Lower)

2 forj

n

downto1do

3

ifTag(ans)=1

4

thenprint(j)

5

ans

Parent(ans)

假设物品已经按照每单位权值非增排序，即v［i］/w［i］≥v［i+1］/w［i+1］。算法LCBB中使用了一个小的正参数ε，算法如下：LCBB(v,w,W,n,

)

1 INIT//初始化可用结点及活结点表

2 INSERT-NODE(E)//根结点

3 Parent(E)

0

4 Level(E)

1

5 CW(E)

W

6 CV(E)

0

7 LUBOUND(v,w,W,n,0,1,LBB,UBB)

8 Lower

LBB–

9 UB(E)

UBB

10 do11 i

Level(E)

12 cap

CW(E)

13 valu

CV(E)

14 if(i=n+1)//叶结点

15

if

valu>Lower

16 thenLower

valu

17

ans

E

18 elseif

cap

w[i]//左孩子可行

19

thenINSERTNODE(E,i+1,1,cap–w[i],valu+v[E],UB[E])20

LUBOUND(v,w,cap,valu,n,i+1,LBB,UBB)//右孩子是否成为活结点

21

ifUBB>Lower//判断右孩子是否成为活结点

22 thenINSERTNODE(E,i+1,0,cap,valu,UBB)

23 Lower

max{Lower,LBB–

}

24

if

不存在活结点thenbreak//退出do…while

循环

25

EXTRACT-MAX(E)//下一个E结点是UB中最大的结点

26 while(UB(E)>Lower)

27 PRINT(Lower,ans,n)

6．0-1背包问题先进先出分枝限界算法

考虑6.1节的0-1背包问题实例，限界函数l(X)和u(X)的定义如前所述。用先进先出队列作为组织活结点表的数据结构，并按照结点l(X)值的大小选择下一个扩展结点，得到0-1背包问题先进先出分枝限界树，如图6-5所示。图6-5

0-1FIFO分枝限界树

0-1背包问题FIFOBB的算法中，结点的生成和E结点的选择是逐层进行的。因此，无需为每个结点专门设置一个Level域，只需要在队列中加上一个符号“＃”，作为层结束标志。状态空间树中每个结点可用五个域表示，如图6-6所示。对LCBB算法做适当修改，就可得到0-1背包问题的FIFOBB算法，在此从略。图6-6

FIFOBB算法中结点的数据结构

6.3作业调度问题

1．定义结点的限界函数

图6-7表示变长元组表示的状态空间树，结点左边值表示结点的l(X)值，结点右边值表示当前最好上界Up值，一旦找到满足l(X)>Up

的结点，该结点就被杀死。标有“×”的结点表示该结点被杀死，其中标有“×”的阴影结点表示由于是

不可行结点而被杀死，除阴影结点之外的所有结点都是答案结点。结点9是问题的最优解，它是惟一的最小成本答案结点，此时，最优解为J={2,3}，罚金为16，即最小成本。对于这棵树中的结点，定义成本函数c(*)如下：对于不可行结点(阴影结点)，c(X)=+∞；对于其他结点，c(X)定义为根为X的子树中结点的最小罚金。在图6-7中，c(1)=16，c(2)=18，c(3)=16。图6-7变长元组对应的状态空间树

2．作业调度问题FIFOBB算法示例

我们利用FIFOBB求解作业调度问题，假设利用图6-7中的变长元组表示法。初始时，设置最小成本答案结点的成本上界为

结点1作为E结点，依次生成结点2、3、4和5。在结点2处，有

由于u(2)=38<Up，Up被修改为38。在结点3处，有

由于u(3)=28<Up，Up被修改为28。在结点4处，有

由于l(4)=30>Up，结点4被杀死。

在结点5处，有

由于l(5)=42>Up，结点5也被杀死。基于FIFO原则，结点2成为下一个E结点，生成它的子结点6、7和8。在结点6处，有

由于u(2)=18<Up=28，Up被修改为18。在结点7处，有

结点7被杀死。

结点8是不可行结点，也被杀死。结点3成为下一个E结点，生成它的子结点9和10。在结点9处，有

由于u(9)=16<Up=18，Up被修改为16。在结点10处，有

由于l(10)=22>Up，结点10被杀死。结点6成为下一个E结点，生成它的子结点11和12。结点11和12都为不可行结点，均被杀死。结点9成为下一个E结点，生成它的子结点13。结点13为不可行结点，被杀死。因此，结点9为最小成本答案结点，成本为16，问题的解J={2,3}。

3．作业调度问题FIFOBB-JS算法

过程FIFOBB-JS描述了找最小成本答案结点的作业调度问题的算法。过程中调用了两个子过程，它们是INSERTQ(X)和EXTRACTQ(X)，分别表示向队列插入一个结点和从队列中删除一个结点。对于状态空间树中的每个答案结点X，cost(X)是结点X对应的解的成本。在FIFOBB-JS中，假设不可行结点的估值l(X)=+∞,可行结点的估值l(X)≤c(X)≤u(X)。FIFOBB-JS(T,l,u,

,cost)

1 E

T

2 Parent(E)

0

3 ifT

是解结点

4

thenUp

min{cost(T),u(T)+

}

5

ans

T

6

elseUp

u(T)+

7 ans

0

8 Q

//初始化队列为空

9 while(1)do10

forE的每个子结点Xdo//对当前E结点进行扩展

11

ifl(X)<Up

12 thenINSERTQ(X)

13

Parent(X)

E

14

if

X

是解结点&cost(X)<Up

15

thenUp

min{cost(X),u(X)+

}

16

ans

X

17

if

u(X)+

<Up

18

thenUp

u(X)+

19

while(1)do

20 ifEmpty(Q)//如果队列Q为空

21

thenprint(“leastcost=”,Up)

22

while

ans

0do

23

print(ans)

24

ans

Parent(ans)

25

return//返回

26 EXTRACTQ(X)

27 ifl(X)<Up

28

then

exit//杀死l(X)

Up的结点，退出第19行的while循环体第1～8行进行初始化。第10行扩展E的每个子结点X。第11行，如果l(X)<Up，调用INSERTQ，将E