【生日快乐】搜索技术【深度优先搜索】 - 子集树

搜索技术【深度优先搜索】 - 子集树

【子集树】

假设有n 个物品和1个背包，每个物品i 对应的价值都为vi ，重量都为wi ，背包的容量为W 。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选取物品装入背包，使背包所装入的物品的总价值最大？要求输出最优值（装入物品的最大价值）和最优解（装入了哪些物品）。

① 问题分析

从n 个物品中选择一些物品，相当于从n 个物品组成的集合S 中找到一个子集，这个子集内所有物品的总重量都不超过背包容量，并且这些物品的总价值最大。S 的所有子集都是问题的可能解，这些可能解组成解空间。我们在解空间中找总重量不超过背包容量且价值最大的物品集作为最优解。这些由问题的子集组成的解空间，其解空间树被称为子集树。

② 算法设计

[1] 定义问题的解空间。该问题属于典型的0-1背包问题，问题的解是从n 个物品中选择一些物品，使其在不超过容量的情况下价值最大。每个物品都有且只有两种状态：要么装入背包，要么不装入背包。那么第i 个物品被装入背包能够达到目标，还是不被装入背包能够达到目标呢？可以用变量xi 表示第i 种物品是否被装入背包，“0”表示不被装入背包，“1”表示被装入背包，则xi 的取值为0或1。第i （i=1,2,…,n ）个物品被装入背包，xi =1；不被装入背包，xi =0。该问题解的形式是一个n 元组，且每个分量的取值都为0或1。由此可得，问题的解空间为{x 1 ,x 2 ,…,xi ,…,xn }，其中显约束xi =0或1（i =1,2,…,n ）。

[2] 确定解空间的组织结构。问题的解空间描述了2n 种可能解，也可以说是由n 个元素组成的集合的所有子集的个数。比如3个物品的背包问题，解空间是{0,0,0}、{0,0,1}、{0,1,0}、{0,1,1}、{1,0,0}、{1,0,1}、{1,1,0}、{1,1,1}。该问题有23 个可能解。可见，问题的解空间树为子集树，解空间树的深度为问题的规模n ，如下图所示。

[3] 搜索解空间。根据解空间的组织结构，对于任何一个中间节点z （中间状态），从根节点到z 节点的分支所代表的状态（是否装入背包）已经确定，从z 到其子孙节点的分支的状态待确定。也就是说，如果z 在解空间树中所处的层次是t ，则说明第1种物品到第t -1种物品的状态已经确定了，只需沿着z 的分支扩展来确定第t 种物品的状态，那么前t 种物品的状态就确定了。在前t 种物品的状态确定后，对当前已被装入背包的物品的总重量用cw表示，对总价值用cp表示。

• 约束条件。判断第i 个物品被装入背包后总重量是否超出背包容量，如果超出，则为不可行解；否则为可行解。约束条件为cw+w [i]≤W 。其中，w [i ]为第i 个物品的重量，W 为背包容量。
• 限界条件。已被装入物品的价值高不一定就是最优的，因为还有剩余物品未确定。目前还不确定第t +1种物品到第n 种物品的实际状态，因此只能用估计值。假设第t +1种物品到第n 种物品都被装入背包，对第t +1种物品到第n 种物品的总价值用rp来表示。因此cp+rp是所有从根出发经过中间节点z 的可行解的价值上界，如下图所示。

如果价值上界小于或等于当前搜索到的最优值（最优值用bestp表示，初始值为0），则说明从中间节点z 继续向子孙节点搜索不可能得到一个比当前更优的可行解，没有继续搜索的必要；反之，继续向z 的子孙节点搜索。

限界条件为：cp+rp>bestp。

这里讲解搜索过程。从根节点开始，以深度优先的方式进行搜索。根节点首先成为活节点，也是当前的扩展节点。由于在子集树中约定左分支上的值为“1”，因此沿着扩展节点的左分支扩展，则代表装入物品。此时需要判断能否装入该物品，即判断约束条件成立与否，如果成立，即生成左孩子，左孩子成为活节点，并且成为当前的扩展节点，继续向纵深节点扩展；如果不成立，则剪掉扩展节点的左分支，沿着其右分支扩展，右分支代表物品不被装入背包，肯定有可能导致可行解。但是沿着右分支扩展有没有可能得到最优解呢？这一点需要由限界条件来判断。如果限界条件满足，则说明有可能得到最优解，即生成右孩子，右孩子成为活节点，并成为当前的扩展节点，继续向纵深节点扩展；如果不满足限界条件，则剪掉扩展节点的右分支，向最近的祖宗活节点回溯，继续搜索。直到所有活节点都变成死节点，搜索结束。

③ 举个栗子

假设现在有4个物品和1个背包，每个物品的重量w 都为(2,5,4,2)，价值v 都为(6,3,5,4)，背包的容量为10（W =10）。求在不超过背包容量的前提下把哪些物品放入背包，才能获得最大价值。

[1] 初始化。sumw和sumv分别用来统计所有物品的总重量和总价值。sumw=13，sumv=18，如果sumw≤W ，则说明可以全部装入，最优值为sumv。如果sumw>W ，则不能全部装入，需要通过搜索求解。初始化当前放入背包的物品重量cw=0；当前放入背包的物品价值cp=0；当前最优值bestp=0。

[2] 搜索第1层（t =1）。扩展节点1，判断cw+w [1]=2

[3] 扩展节点2（t =2）。判断cw+w [2]=7

[4] 扩展节点3（t =3）。判断cw+w [3]=11>W ，超过了背包容量，第3个物品不能被放入。那么判断bound(t +1)是否大于bestp。bound(4)中剩余的物品只有第4个，rp=4，cp+rp=13，bestp=0，满足限界条件，扩展右子树。令x [3]=0，生成节点4，如下图所示。

[5] 扩展节点4（t =4）。判断cw+w [4]=9

[6] 扩展节点5（t =5）。t >n ，找到一个当前最优解，用bestx[]保存当前最优解{1,1,0,1}，保存当前最优值bestp=cp=13，节点5成为死节点，如下图所示。

[7] 回溯到节点4（t =4），一直向上回溯到节点2。向上回溯到节点4，回溯时cw=cw−w [4]=7，cp=cp−v [4]=9。怎么加上的，怎么减回去。节点4的右子树还未生成，考查bound(t +1)是否大于bestp，在bound(5)中没有剩余的物品，rp=0，cp+rp=9，bestp=13，因此不满足限界条件，不再扩展节点4的右子树。节点4成为死节点。向上回溯，回溯到节点3，节点3的左右孩子均已被考查过，是死节点，继续向上回溯到节点2。回溯时，cw=cw−w [2]=2，cp=cp−v [2]=6。怎么加上的，怎么减回去，如下图所示。

[8] 扩展节点2（t =2）。节点2的右子树还未生成，考查bound(t+1)是否大于bestp，bound(3)中剩余的物品为第3、4个，rp=9，cp+rp=15，bestp=13，因此满足限界条件，扩展右子树。令x [2]=0，生成6号节点。

[9] 扩展节点6（t =3）。判断cw+w [3]=6

[10] 扩展节点7（t =4）。判断cw+w [4]=8

[11] 扩展节点8（t =5）。t >n ，找到一个当前最优解，用bestx[]保存当前最优解{1,0,1,1}，保存当前最优值bestp=cp=15，节点8成为死节点。向上回溯到节点7，回溯时cw=cw−w [4]=6，cp=cp−v[4]=11。怎么加上的，怎么减回去。

[12] 扩展节点7（t =4）。节点7的右子树还未生成，考查bound(t +1)是否大于bestp，在bound(5)中没有剩余的物品，rp=0，cp+rp=11，bestp=15，因此不满足限界条件，不再扩展节点7的右子树。节点7成为死节点。向上回溯，回溯到节点6，回溯时，cw=cw−w[3]=2，cp=cp−v [3]=6，怎么加上的，怎么减回去。

[13] 扩展节点6（t =3）。节点6的右子树还未生成，考查bound(t +1)是否大于bestp，bound(4)中剩余的物品是第4个，rp=4，cp+rp=10，bestp=15，因此不满足限界条件，不再扩展节点6的右子树。节点6成为死节点。向上回溯，回溯到节点2，节点2的左右孩子均已被考查过，是死节点，继续向上回溯到节点1。回溯时，cw=cw−w[1]=0，cp=cp−v [1]=0。怎么加上的，怎么减回去。

[14] 扩展节点1（t =1）。节点1的右子树还未生成，考查bound(t+1)是否大于bestp，bound(2)中剩余的物品是第2、3、4个，rp=12，cp+rp=12，bestp=15，因此不满足限界条件，不再扩展节点1的右子树，节点1成为死节点。所有节点都是死节点，算法结束。

④ 算法实现

[1] 计算上界。计算上界指计算已装入物品的价值cp及剩余的物品价值的总价值rp。我们已经知道已被装入背包的物品价值cp，对剩余的物品不确定要装入哪些，按照假设都被装入的情况计算，即按最大值计算（剩余的物品的总价值），因此得到的值是可装入物品价值的上界。

double Bound(int i){ //计算上界【即已装入物品价值 + 剩余物品的总价值】
	int rp = 0; //剩余的物品为第 i ~ n 种物品
	while(i <= n){ //依次计算剩余的物品价值
		rp += v[i];
		i ++;
	}
	return cp + rp; //返回上界
}
1
2
3
4
5
6
7
8

[2] 按约束条件和限界条件搜索求解。t 表示当前扩展节点在第t层，cw表示当前已被放入物品的重量，cp表示当前已被放入物品的价值。如果t >n ，则表示已经到达叶子，记录最优值的最优解，返回；否则，判断是否满足约束条件，满足则搜索左子树。因为左子树表示放入该物品，所以令x [t ]=1，表示放入第t 个该物品。cw+=w [t ]，表示当前已被放入物品的重量增加w [t ]。cp+=v [t ]，表示当前已被放入物品的价值增加v [t ]。Backtrack(t +1)表示递推，深度优先搜索第t +1层。回归时即向上回溯时，把增加的值减去，cw−=w [t ]，cp−=v [t ]。判断是否满足限界条件，满足则搜索右子树。因为右子树表示不放入该物品，所以令x [t ]=0，当前已被放入物品的重量、价值均不改变。Backtrack(t +1)表示深度优先搜索第t +1层。

void Backtrack(){ //t 表示当前扩展节点在第 t 层
	if(t > n){ //已经到达叶子
		for(j = 1; j <= n ; j++){
			bestx[j] = x[j];
		}
		bestp = cp; //保存当前最优解
		return ;
	}
	if(cw + w[t] <= w){ //如果满足约束条件，则搜索左子树
		x[t] = 1;
		cw += w[t];
		cp += v[t];
		Backtrack(t + 1);
		cw -= w[t];
		cp -= v[t];
	}
	if(Bound(t + 1) > bestp){ //如果满足限界条件，则搜索右子树
		x[t] = 0;
		Backtrack(t + 1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

⑤ 算法分析

时间复杂度： 回溯法的运行时间取决于它在搜索过程中生成的节点数。而限界函数可以大大减少所生成的节点个数，避免无效搜索，加快搜索速度。

左孩子需要判断约束函数，右孩子需要判断限界函数，那么在最坏情况下有多少个左孩子和右孩子呢？规模为n 的子集树在最坏情况下的状态如下图所示。

总的节点个数为2^0 +2^1 +…+2^n =2^(n +1) -1，减去树根再除以2，就得到了左右孩子的个数，左右孩子的个数为(2^(n +1) -1-1)/2=2^n -1。

约束函数的时间复杂度为O (1)，限界函数的时间复杂度为O (n)。在最坏情况下有O (2^n )个左孩子调用约束函数，有O (2^n )个右孩子调用限界函数，所以采用回溯法解决背包问题的时间复杂度为O(1×2^n +n ×2^n )=O (n ×2^n )。

空间复杂度： 在搜索过程中的任何时刻，仅保留从开始节点到当前扩展节点的路径，从开始节点到叶子最长的路径长度为n 。在程序中使用bestx[]数组记录该最长路径作为最优解，所以该算法的空间复杂度为O (n )。

⑥ 算法优化拓展

在上面的程序中，上界函数是当前价值cp加剩余物品的总价值rp，这个估值过高，因为剩余物品的重量很有可能是超过背包容量的。可以缩小上界，加快剪枝速度，提高搜索效率。

上界函数Bound()：当前价值cp+剩余容量可容纳的剩余物品的最大价值brp。

为了更好地计算和运用上界函数剪枝，先将物品按照其单位重量价值（价值/重量）从大到小排序，然后按照排序后的顺序考察各个物品。

double Bound(int i){ //计算上界【将剩余的物品装满剩余的背包容量获得的最大价值】
	//剩余的物品为第 i ~ n 种物品
	double cleft = W - cw; //剩余的背包容量
	double brp = 0.0;
	while(i <= n && w[i] < cleft){
		cleft -= w[i];
		brp += v[i];
		i ++;
	}
	if(i <= n ){ //采用切割方式装满背包，这里是在求上界，求解时不允许切割
		brp += v[i] / w[i] * cleft;
	}
	return cp + brp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度： 约束函数的时间复杂度为O (1)，限界函数的时间复杂度为O (n )。在最坏情况下有O (2^n )个左孩子需要调用约束函数，有O (2^n )个右孩子需要调用限界函数，回溯算法Backtrack的时间复杂度为O (n 2^n )。排序函数的时间复杂度为O (n logn )。这考虑了最坏情况，实际上，经过上界函数优化后，剪枝速度很快，根本不需要生成所有节点。

空间复杂度： 这里除了记录了最优解数组，还使用了一个结构体
数组用于排序，两个辅助数组传递排序后的结果，这些数组的规模都
是n ，因此空间复杂度仍是O (n )。