A={v,w2,…,wn}中的元素是按不降的次序排列的,则上述继续搜 索的条件还可以加强为 ∑x+∑≥Mamd∑wx+Wk+1≤M 7.3) k+l≤ 上述不等式记做Bk。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r)/寻找W[1:n]中元素和为M的所有子集。 //w[l:n]中元素按不降次序排列,进入此过程时,X[1], //X[k-1]的值已经确定。记s=∑W小X[小,r=∑W l≤j≤k-1 k≤j≤n //假定W[1]≤M,∑W[门≥M l≤j≤n 1 global integer M, n; global real W[l: n]; 2 global boolean X[l: n] 3 real, s: integer k, j: //由于B-=true,因此s+W[k]≤M 4X[k]=1;//生成左儿子。 5 if s+Wk print (X[j], j from 1 to k) else fs+W[k]+W[k+1]≤Mthe Sum Subset(s+Wlk, k+1, r-WLkD 9 endif 10 dif
{ , , , } A = w 1 w2 L wn 中的元素是按不降的次序排列的，则上述继续搜 索的条件还可以加强为 w x w M and w xi wk M i k i k i n i i i k i + ≥ + + ≤ ≤ ≤ + ≤ ≤ ≤ ≤ ∑ ∑ ∑ 1 1 1 1 (7.3) 上述不等式记做 Bk。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r) // 寻找 W[1:n]中元素和为 M 的所有子集。 //W[1:n]中元素按不降次序排列，进入此过程时，X[1], . . . , //X[k-1]的值已经确定。记 ∑ ≤ ≤ − = 1 1 [ ] [ ] j k s W j X j ， ∑ ≤ ≤ = k j n r W[ j] //假定 W[1] ≤ M, ∑ ≤ ≤ ≥ j n W j M 1 [ ] 1 global integer M, n; global real W[1:n]; 2 global boolean X[1:n]; 3 real r, s; integer k, j; //由于 Bk-1=true，因此 s + W[k]≤ M 4 X[k]=1; // 生成左儿子。 5 if s + W[k]= M then print (X[j],j from 1 to k); 6 else 7 if s + W[k] + W[k+1] ≤ M then 8 SumSubset(s+W[k], k+1, r-W[k]); 9 endif 10 endif
11ifs+r-W[k]≥ M and s+W[k+1]≤ m then 12 X[k]=0;//生成右儿子 13 SumSubset(s, k+l, r-WLkD 14 endif 15 end Sum Subset 因为假定W[1]≤M,∑W门≥M,所以程序开始执行时, l≤j≤n B=true。同样,程序在递归执行过程中,总是以前提条件B-1=true 开始处理第k级顶点的儿子们的生成过程,由第3~10语句完成,并 在此过程中决定是否转动生成下一级顶点的儿子的生成过程,由11~ 14语句完成。语句11是一个判断条件,如果这个条件不能满足,则 没有必要生成k级顶点的右儿子。而在左儿子被生成后,语句4和语 句7决定是否沿着这个左儿子继续搜索。所以该算法所生成的子树的 叶顶点或是某个左儿子,此时找到一个可行解;或者是某个右儿子 此时由根顶点到该顶点的路径不能延伸为可行解 例子:n=6,M30;W[1:6]=(5,10,12,13,15,18).由算法 SumSubset所生成的解空间树的子树参看文档 Sum Subset树。 (二).0/1背包问题 0/1背包问题是一个优化问题,因此不仅可以使用约束函数,而且可以 使用限界函数做剪枝函数.如果当前背包中的物品总重量是cw,前面 k-1件物品都已经决定好是否放入包中,那么第k件物品是否放入包 中取决于不等式cw+w≤M是否满足.这即是搜索的约束函数.另外
11 if s + r – W[k]≥ M and s + W[k+1] ≤ M then 12 X[k]=0; //生成右儿子 13 SumSubset(s,k+1,r-W[k]); 14 endif 15 end SumSubset 因为假定 W[1] ≤ M， ∑ ≤ ≤ ≥ j n W j M 1 [ ] ，所以程序开始执行时， B0=true。同样，程序在递归执行过程中，总是以前提条件 Bk-1=true 开始处理第 k 级顶点的儿子们的生成过程，由第 3～10 语句完成，并 在此过程中决定是否转动生成下一级顶点的儿子的生成过程，由 11～ 14 语句完成。语句 11 是一个判断条件，如果这个条件不能满足，则 没有必要生成 k 级顶点的右儿子。而在左儿子被生成后，语句 4 和语 句 7 决定是否沿着这个左儿子继续搜索。所以该算法所生成的子树的 叶顶点或是某个左儿子，此时找到一个可行解；或者是某个右儿子， 此时由根顶点到该顶点的路径不能延伸为可行解。 例 子 ： n=6,M=30; W[1:6]=(5,10,12,13,15,18). 由 算 法 SumSubset 所生成的解空间树的子树参看文档 SumSubset 树。 (二).0/1 背包问题 0/1背包问题是一个优化问题,因此不仅可以使用约束函数,而且可以 使用限界函数做剪枝函数.如果当前背包中的物品总重量是 cw,前面 k-1 件物品都已经决定好是否放入包中,那么第 k 件物品是否放入包 中取决于不等式 cw + wk ≤ M 是否满足.这即是搜索的约束函数.另外
我们可以如下确定限界函数.回忆可分割的0/1背包问题的贪心算法, 当物品的按照P/w1≥P+1w的规则排序时,最优解是 (x1,…,x-1,x1,x1+1…,xn)=(1,…1,1,0,…,0)的形式,其中,0≤t≤1 设当前背包中物品的总效益值时cp,如下方式确定限界函数 构造限界函数 Bounde(cp,cw,k,M)//返回效益值的当前限界 gloal n, p[l:n], w[1:n] integer k, i; real b, c, cp, cw, M: B=cp; c=cw for i from k+1 to n do C-C if c< M then b=b+pli] else return (b+(1-(c-D)/wli])*p[i] endif enat or return(b) end bound 这样确定的限界函数表明,从当前确定的k-1定子解空间中寻求到的 可行解所能达到的效益值以当前限界函数的值为上界.所以,如果搜 索最优解的算法在此之前已经知道大于这个限界值的效益,则没有必 要在当前确定的k-1定子解空间中搜索.据此我们给出0/1背包问题 的回溯算法
我们可以如下确定限界函数.回忆可分割的 0/1 背包问题的贪心算法, 当物品的按照 1 1 / / i i ≥ i+ wi+ p w p 的规则排序时,最优解是 ( , , , , , , ) (1, ,1, ,0, ,0) x1 L xl −1 xl xl +1 L xn = L t L 的形式,其中,0 ≤ t ≤ 1. 设当前背包中物品的总效益值时 cp,如下方式确定限界函数: 构造限界函数 BoundF(cp,cw,k,M) //返回效益值的当前限界 gloal n, p[1:n],w[1:n]; integer k,i; real b,c,cp,cw,M; B=cp;c=cw; for i from k+1 to n do c=c+w[i]; if c < M then b=b+p[i]; else return (b+(1-(c-M))/w[i])*p[i]; endif endfor return (b); end BoundF 这样确定的限界函数表明,从当前确定的 k-1 定子解空间中寻求到的 可行解所能达到的效益值以当前限界函数的值为上界.所以,如果搜 索最优解的算法在此之前已经知道大于这个限界值的效益,则没有必 要在当前确定的 k-1 定子解空间中搜索.据此我们给出 0/1 背包问题 的回溯算法