4.2.2 0/1背包问题
0 / 1背包问题是一个N P-复杂问题，为了解决该问题，在1 . 4节采用了贪婪算法，在3 . 2节又采用了动态规划算法。在本节，将用回溯算法解决该问题。既然想选择一个对象的子集，将它们装入背包，以便获得的收益最大，则解空间应组织成子集树的 形状（如图1 6 - 2所示）。该回溯算法与4 . 2节的装载问题很类似。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包 中的对象的集合。
与程序1 6 - 2一样，左孩子表示一个可行的节点，无论何时都要移动到它；当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是 令r 为还未遍历的对象的收益之和，将r 加到c p（当前节点所获收益）之上，若（ r + c p）≤b e s t p（目前最优解的收益），则不需搜索右子树。一种更有效的方法是按收益密度pi / wi 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放入背包的对象时，就使用它的一部分。
例4-7 考察一个背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。这些对象的收益密度为[ 3 , 2 , 3 . 5 , 4 ]。当背包以密度递减的顺序被填充时，对象4首先被填充，然后是对象3、对象1。在这三个对象被装入背包之后，剩余容量为1。这个容量可容纳对象2的0 . 2倍的重量。将0 . 2倍的该对象装入，产生了收益值2。被构造的解为x= [ 1 , 0 . 2 , 1 , 1 ]，相应的收益值为2 2。尽管该解不可行（x2 是0 . 2，而实际上它应为0或1），但它的收益值2 2一定不少于要求的最优解。因此，该0 / 1背包问题没有收益值多于2 2的解。
解空间树为图1 6 - 2再加上一层节点。当位于解空间树的节点B时，x1= 1，目前获益为c p= 9。该节点所用容量为c w= 3。要获得最好的附加收益，要以密度递减的顺序填充剩余容量c l e f t=ccw= 4。也就是说，先放对象4，然后是对象3，然后是对象2的0 . 2倍的重量。因此，子树A的最优解的收益值至多为2 2。当位于节点C时，c p=c w= 0，c l e f t= 7。按密度递减顺序填充剩余容量，则对象4和3被装入。然后是对象2的0 . 8倍被装入。这样产生出收益值1 9。在子树C中没有节点可产生出比1 9还大的收益值。
在节点E，c p= 9，c w= 3，c l e f t= 4。仅剩对象3和4要被考虑。当对象按密度递减的顺序被考虑时，对象4先被装入，然后是对象3。所以在子树E中无节点有多于c p+ 4 + 7 = 2 0的收益值。如果已经找到了一个具有收益值2 0或更多的解，则无必要去搜索E子树。
一种实现限界函数的好方法是首先将对象按密度排 序。假定已经做了这样的排序。定义类K n a p（见程序1 6 - 5）来减少限界函数B o u n d（见程序1 6 - 6）及递归函数K n a p s a c k（见程序1 6 - 7）的参数数量，该递归函数用于计算最优解的收益值。参数的减少又可引起递归栈空间的减少以及每一个K n a p s a c k的执行时间的减少。注意函数K n a p s a c k和函数m a x L o a d i n g（见程序1 6 - 2）的相似性。同时注意仅当向右孩子移动时，限界函数才被计算。当向左孩子移动时，左孩子的限界函数的值与其父节点相同。
程序16-5 Knap类
template
class Knap {
friend Tp Knapsack(Tp *, Tw *, Tw, int);
p r i v a t e :
Tp Bound(int i);
void Knapsack(int i);
Tw c; / /背包容量
int n; // 对象数目
Tw *w; // 对象重量的数组
Tp *p; // 对象收益的数组
Tw cw; // 当前背包的重量
Tp cp; // 当前背包的收益
Tp bestp; // 迄今最大的收益
} ;
程序16-6 限界函数
template
Tp Knap
{// 返回子树中最优叶子的上限值Return upper bound on value of
// best leaf in subtree.
Tw cleft = c - cw; // 剩余容量
Tp b = cp; // 收益的界限
// 按照收益密度的次序装填剩余容量
while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i + + ; } // 取下一个对象的一部分 if (i <= n) b += p[i]/w[i] * cleft; return b; } 程序16-7 0/1背包问题的迭代函数 template
void Knap
{// 从第i 层节点搜索
if (i > n) {// 在叶节点上
bestp = cp;
r e t u r n ; }
// 检查子树
if (cw + w[i] <= c) {//尝试x[i] = 1 cw += w[i]; cp += p[i]; K n a p s a c k ( i + 1 ) ; cw -= w[i]; cp -= p[i];} if (Bound(i+1) > bestp) // 尝试x[i] = 0
K n a p s a c k ( i + 1 ) ;
}
在 执行程序1 6 - 7的函数Kn a p s a c k之前，需要按密度对对象排序，也要确保对象的重量总和超出背包的容量。为了完成排序，定义了类O b j e c t（见程序1 6 - 8）。注意定义操作符< =是为了使归并排序程序（见程序1 4 - 3）能按密度递减的顺序排序。 程序16-8 Object类 class Object { friend int Knapsack(int *, int *, int, int); p u b l i c : int operator<=(Object a) const {return (d >= a.d);}
p r i v a t e :
int ID; // 对象号
float d; // 收益密度
} ;
程 序1 6 - 9首先验证重量之和超出背包容量，然后排序对象，在执行K n a p : : K n a p s a c k之前完成一些必要的初始化。K n a p : K n a p s a c k的复杂性是O (n2n )，因为限界函数的复杂性为O (n)，且该函数在O ( 2n )个右孩子处被计算。
程序16-9 程序1 6 - 7的预处理代码
template
Tp Knapsack(Tp p[], Tw w[], Tw c, int n)
{// 返回最优装包的值
// 初始化
Tw W = 0; // 记录重量之和
Tp P = 0; // 记录收益之和
// 定义一个按收益密度排序的对象数组
Object *Q = new Object [n];
for (int i = 1; i <= n; i++) { // 收益密度的数组 Q[i-1].ID = i; Q[i-1].d = 1.0*p[i]/w[i]; P += p[i]; W += w[i]; } if (W <= c) return P; // 可容纳所有对象 MergeSort(Q,n); // 按密度排序 // 创建K n a p的成员 K n a p <> K;
K.p = new Tp [n+1];
K.w = new Tw [n+1];
for (i = 1; i <= n; i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.c = c; K.n = n; K.bestp = 0; // 寻找最优收益 K . K n a p s a c k ( 1 ) ; delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; }
4.2.3 最大完备子图
令U为无向图G的顶点的子集，当且仅当对于U中的任意点u 和v，(u , v)是图G的一条边时，U定义了一个完全子图（complete subgraph）。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G的一个更大的完全子图中时，它是图G的一个完备子图。最大的完备子图 是具有最大尺寸的完备子图。
例4-8 在图16-7a 中，子集{ 1 , 2 }定义了一个尺寸为2的完全子图。这个子图不是一个完备子图，因为它被包含在一个更大的完全子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }定义了该图的一个最大的完备子图。点集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定义了其他的最大的完备子图。
当且仅当 对于U中任意点u 和v，(u , v) 不是G的一条边时，U定义了一个空子图。当且仅当一个子集不被包含在一个更大的点集中时，该点集是图G的一个独立集（independent set），同时它也定义了图G的空子图。最大独立集是具有最大尺寸的独立集。对于任意图G，它的补图（c o m p l e m e n t） 是有同样点集的图，且当且仅当（ u,v）不是G的一条边时，它是的一条边。
例4-9 图16-7b 是图16-7a 的补图，反之亦然。{ 2 , 4 }定义了16-7a 的一个空子图，它也是该图的一个最大独立集。虽然{ 1 , 2 }定义了图16-7b 的一个空子图，它不是一个独立集，因为它被包含在空子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }是图16-7b 中的一个最大独立集。
如果U定义了G的一个完全子图，则它也定义了的一个空子图，反之亦然。所以在G的完备子图与的独立集之间有对应关系。特别的， G的一个最大完备子图定义了的一个最大独立集。
最 大完备子图问题是指寻找图G的一个最大完备子图。类似地，最大独立集问题是指寻找图G的一个最大独立集。这两个问题都是N P-复杂问题。当用算法解决其中一个问题时，也就解决了另一个问题。例如，如果有一个求解最大完备子图问题的算法，则也能解决最大独立集问题，方法是首先 计算所给图的补图，然后寻找补图的最大完备子图。
例4-10 假定有一个n 个动物构成的集合。可以定义一个有n 个顶点的相容图（c o m p a t i b i l i t yg r a p h）G。当且仅当动物u 和v 相容时，（u,v）是G的一条边。G的一个最大完备子图定义了相互间相容的动物构成的最大子集。
3 . 2节考察了如何找到一个具有最大尺寸的互不交叉的网组的集合问题。可以把这个问题看作是一个最大独立集问题。定义一个图，图中每个顶点表示一个网组。当且 仅当两个顶点对应的网组交叉时，它们之间有一条边。所以该图的一个最大独立集对应于非交叉网组的一个最大尺寸的子集。当网组有一个端点在路径顶端，而另一 个在底端时，非交叉网组的最大尺寸的子集能在多项式时间（实际上是(n2 )）内用动态规划算法得到。当一个网组的端点可能在平面中的任意地方时，不可能有在多项式时间内找到非交叉网组的最大尺寸子集的算法。最大完备子图问题和 最大独立集问题可由回溯算法在O (n2n )时间内解决。两个问题都可使用子集解空间树（如图1 6 - 2所示）。考察最大完备子图问题，该递归回溯算法与程序1 6 - 3非常类似。当试图移动到空间树的i 层节点Z的左孩子时，需要证明从顶点i 到每一个其他的顶点j（xj = 1且j 在从根到Z的路径上）有一条边。当试图移动到Z的右孩子时，需要证明还有足够多的顶点未被搜索，以便在右子树有可能找到一个较大的完备子图。
回溯算法可作为类A d j a c e n c y G r a p h（见程序1 2 - 4）的一个成员来实现，为此首先要在该类
中加入私有静态成员x（整型数组，用于存储到当前节点的路径），b e s t x（整型数组，保存目
前的最优解），b e s t n（b e s t x中点的数量），c n（x 中点的数量）。所以类A d j a c e c y G r a p h的所有实
例都能共享这些变量。
函数m a x C l i q u e（见程序1 6 - 1 0）是类A d j a c e n c y G r a p h的一个私有成员，而M a x C l i q u e是一个
共享成员。函数m a x C l i q u e对解空间树进行搜索，而M a x C i q u e初始化必要的变量。M a x c l i q u e ( v )
的执行返回最大完备子图的尺寸，同时它也设置整型数组v，当且仅当顶点i 不是所找到的最大
完备子图的一个成员时，v [ i ] = 0。
程序16-10 最大完备子图
void AdjacencyGraph::maxClique(int i)
{// 计算最大完备子图的回溯代码
if (i > n) {// 在叶子上
// 找到一个更大的完备子图，更新
for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; r e t u r n ; } // 在当前完备子图中检查顶点i是否与其它顶点相连 int OK = 1; for (int j = 1; j < ok =" 0;"> bestn) {// 尝试x[i] = 0
x[i] = 0;
m a x C l i q u e ( i + 1 ) ; }
}
int AdjacencyGraph::MaxClique(int v[])
{// 返回最大完备子图的大小
// 完备子图的顶点放入v [ 1 : n ]
// 初始化
x = new int [n+1];
cn = 0;
bestn = 0;
bestx = v;
// 寻找最大完备子图
m a x C l i q u e ( 1 ) ;
delete [] x;
return bestn;
}
没有评论:
发表评论