第6章分枝限界法

第6章分枝限界法第6章分枝限界法6.1分枝限界法的基本思想6.20-1背包问题6.3作业调度问题第6章分枝限界法6.1分枝限界法的基本思想如果把回溯法看作深度优先搜索解空间树的过程，那么，分枝限界法则可看作广度优先或者按照最大价值(或最小成本)搜索解空间树的过程。它也是一种系统地搜索问题解的方法。按照从活结点表中选择扩展结点的方法，分枝限界法又可细分为：(1)先进先出(firstinfirstout，简称FIFO)分枝限界法(FIFOBB)。在先进先出的分枝限界法中，用队列作为组织活结点表的数据结构，并按照队列先进先出的原则选择结点作为扩展结点。第6章分枝限界法(2)优先队列(priorityqueue，简称PQ)分枝限界法(PQBB)。在优先队列分枝限界法中，用优先队列作为组织活结点表的数据结构，每个结点都有一个成本或价值，按照最大价值(greatestvalue)/最小成本(leastcost)的原则选择结点作为扩展结点。我们以0-1背包问题为例，讨论这两种分枝限界法的异同。某商店有n个物品，第i个物品价值为vi，容量(或称权值)为wi，其中vi和wi为非负数。背包的容量为W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大。这个问题的形式描述如下：niiixv1max第6章分枝限界法约束条件为nixWxwiniii1,1,0,1考虑n=4个物品的一个例子，其中(w1,w2,w3,w4)=(10,20,30,45)，(v1,v2,v3,v4)=(20,20,24,36)，W=75，物品已经按照每单位权值从大到小排列。第6章分枝限界法1．先进先出状态空间树设T是一棵状态空间树，c(*)是T中结点的价值函数。如果X是T中的一个结点，c(X)可定义为其根为X的子树中任一答案结点的最大价值(或最小成本)。这个c(*)是难于构造的，通常使用一个对c(*)估值的启发式函数来代替。这个启发式函数易于计算，具有性质：如果X是一个答案结点或一个叶结点，则。对于0-1背包问题，结点X处的估值函数定义为，其中k表示结点X所在的层。用队列作为组织活结点表的数据结构，按照结点进入队列的先后顺序选择下一个扩展结点，得到0-1背包问题先进先出状态空间树，如图6-1所示。)(c)((*)cckiiixv1)(Xc第6章分枝限界法图6-1先进先出状态空间树011010000001111000101101055,201065,2045,400,6015,6475,035,4425,4410,5630,360,7620,561789425136710111213141519212325262728293031182245,24第6章分枝限界法基于上述分析，0-1背包问题FIFO状态空间树中使用的主要数据结构及其变化过程如下：(1)主要数据结构：先进先出队列Q，用于维持待扩展结点的活结点表。(2)主要数据结构的变化状态：(a)当前队列：Q={1}；下一个E结点：1。(b)当前队列：Q={2,3}；下一个E结点：2。(c)当前队列：Q={3,4,5}；下一个E结点：3。(d)当前队列：Q={4,5,6,7}；下一个E结点：4。(e)当前队列：Q={5,6,7,8,9}；下一个E结点：5。(f)当前队列：Q={6,7,8,9,10,11}；下一个E结点：6。第6章分枝限界法(g)当前队列：Q={7,8,9,10,11,12,13}；下一个E结点：7。(h)当前队列：Q={8,9,10,11,12,13,14,15}；下一个E结点：8。产生问题的可行结点17，对应的价值为64。(i)当前队列：Q={9,10,11,12,13,14,15,16}；下一个E结点：9。产生问题的可行结点18，填充背包，对应的价值为76。继续这一过程直到队列Q空为止。在产生的所有可行解中，结点18产生问题的最大价值的可行解值，称为问题的最优解的值，对应的最优解为(1,1,0,1)。由此可见，0-1背包问题FIFO状态空间树中结点的扩展过程与从根结点扩展的广度优先搜索树非常相似，它们的主要区别在于FIFO分枝限界法不扩展不可行结点。第6章分枝限界法2．优先队列状态空间树当用优先队列作为组织活结点表的数据结构，并按照结点估值函数值的大小选择下一个扩展结点时，就得到0-1背包问题优先队列状态空间树，如图6-2所示。第6章分枝限界法图6-2优先队列状态空间树01101000000111100010110101065,2045,4015,6475,055,2035,4425,4445,2430,360,7620,5610,569674518191213202126271115172324252829303110160,60123第6章分枝限界法基于上述分析，0-1背包问题优先队列状态空间树中使用的主要数据结构及其变化过程如下：(1)主要数据结构：优先队列Q，用于维持待扩展结点的活结点表。(2)主要数据结构的变化状态：(a)当前优先队列：Q={1}；下一个E结点：1。(b)当前优先队列：Q={2,3}；下一个E结点：2。(c)当前优先队列：Q={4,3,5}；下一个E结点：4。(d)当前优先队列：Q={6,7,5,3}；下一个E结点：6。(e)当前优先队列：Q={7,5,3}，生成价值为64的答案结点9；下一个E结点：7。第6章分枝限界法(f)当前优先队列：Q={5,3}，生成价值分别为76、40的答案结点10和11；下一个E结点：5。(g)当前优先队列：Q={12,3,13}；下一个E结点：12。(h)当前优先队列：Q={13,3}，生成价值为44的答案结点15；下一个E结点：13。(i)当前优先队列：Q={3}，生成价值分别为56、20的答案结点16和17；下一个E结点：3。(j)当前优先队列：Q={18,19}；下一个E结点：18。(k)当前优先队列：Q={20,19,21}；下一个E结点：20。(l)当前优先队列：Q={21,19}，生成价值44的答案结点23；下一个E结点：21。第6章分枝限界法(m)当前优先队列：Q={19}，生成价值分别为56、20的答案结点24和25；下一个E结点：19。(n)当前优先队列：Q={26,27}；下一个E结点：26。(o)当前优先队列：Q={27}，生成价值分别为60、24的答案结点28和29；下一个E结点：27。(p)当前优先队列：Q={}，生成价值分别为36、0的答案结点30和31，队列为空，循环结束，产生问题的最优解的值76，对应的结点为结点10。由此可见，0-1背包问题优先队列状态空间树中结点的扩展过程与从根结点扩展的深度优先搜索树非常相似，它们的主要区别在于优先队列分枝限界法不扩展不可行结点。第6章分枝限界法6.20-1背包问题1．限界设T是一棵状态空间树，c(*)是T中结点的成本函数。如果X是T中的一个结点，则c(X)是其根为X的子树中任一答案结点的最小成本。这个c(*)是难于构造的，通常使用一个对c(*)估值的启发式函数l(*)来代替，这个启发式函数易于计算，具有性质：如果X是一个答案结点或一个叶结点，则c(*)=l(*)。第6章分枝限界法搜索问题状态空间树的各种分枝限界法都是在生成当前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。第6章分枝限界法2．定义结点的限界函数通过构造和设计结点处的限界函数，可以减小问题的状态搜索空间。为了讨论方便起见，我们将最大值优化问题转变成最小值优化问题。替代目标函数，就使背包问题从一个最大值优化问题变成最小值优化问题。显然，取最大。重新定义了目标函数之后，背包问题描述如下：niiixv1niiixv1niiixv1niiixv1niiixv1min(6.1)第6章分枝限界法约束条件为nixWxwniiii1},1,0{,1式(6.1)中各量的意义同6.1节。第6章分枝限界法我们仍然采用固定元组表示问题的解。图6-1和图6-2中那些满足，其他的叶结点是不可行结点。对于每一个答案结点X定义它的成本函数为，而对于不可行结点定义它的成本为+∞。对于内结点及根结点，则将成本函数c(X)递归定义为min{c(Lchild(X)),c(Rchild(X))}。对于每个结点X，构造两个函数l(X)和u(X)，满足l(X)≤c(X)≤u(X)。这两个函数的构造及导出过程如下:首先构造结点X处的上界函数u(X)，设X是第k层上的一个结点，1≤k≤n+1，在结点X处，已决定了前k-1个物品的装包情况xi，1≤ik。这时，装包开销为，因此，。因而定义结点X处的上界函数u(X)为。UPBOUND是针对上界函数u(X)对过程BOUND(见5.4节)所做的一种改变。对于结点X，有。niiiWxw1niiixvXc1)(kiiixvXu1)(kiiixvXc1)(kiiixvXu1)(kikiiiiiWjxwxvXu11,1,,UPBOUND)(第6章分枝限界法UPBOUND(cv,cw,k,W)1b←cv2c←cw3fori←k+1tondo4ifc+w［i］≤W5thenc←c+w［i6b←b-v［i7return(b)由于，因此，结点X处的下界函数l(X)可定义为：kikiiiiiWkxwxvXc11,1,,BOUND)(kikiiiiiWkxwxvXl11,1,,BOUND)(第6章分枝限界法3．0-1背包问题优先队列分枝限界法示例对于上述构造的限界函数l(X)和u(X)，再次考虑6.1节的0-1背包问题实例。用优先队列作为组织活结点表的数据结构，并按照结点l(X)值的大小选择下一个扩展结点，得到0-1背包问题优先队列分枝限界树，如图6-3所示。第6章分枝限界法1010100011×－40－4076－64－764－64－762－64－7615×－44－723×－44－64l＝－76u＝－64－64－64－76－769×101－76－76图6-30-1背包问题优先队列分枝限界树第6章分枝限界法扩展过程开始时，将根结点1作为E结点，计算它的下界l(1)和上界u(1)：由于结点1不是答案结点，设置初值ans=0，Up=-64+ε，ε为一常数。扩展结点1，生成它的两个子结点2和3:l(2)=-BOUND(20,10,1,75)=-76u(2)=UPBOUND(-20,10,1,75)=-64l(3)=-BOUND(0,0,1,75)=-64u(3)=UPBOUND(0,0,1,75)=-4464)75,0,0,0()1(76)75,0,0,0(,1,,BOUND1)1(11UPBOUNDuBOUNDWkxwxvlkikiiiii第6章分枝限界法将结点2和3插入优先队列中。结点2成为下一个E结点，它生成结点4和5:l(4)=-BOUND(40,30,2,75)=-76u(4)=UPBOUND(-40,