深度优先搜索(DFS)
咱们现讲一个有趣的事情,当我们身处在一个巨大的迷宫中,没有任何帮组我们如何走出这迷宫呢?有一种看上去很盲目但实际上很有效的方法。
以当前的位置为起点,沿着一条路向前走,当碰到岔路口的时候,选择一个岔路口前进。如果选择的这个岔路前方是一条死路,就退回到这个岔路口,选择另一条岔路前进。如果岔路中存在新的岔路口,那么仍然按照上面的方法枚举新岔路口的每一条岔路。这样,只要迷宫存在出口,那么这个方法就一定能找到它。
有人也许会问,如果第一个岔路口处选择了一条没有出路的分支,而这个分支比较深,并且路上多次出现新的岔路口,那么在发现这个分支是一个死路后,如何退出到最初的这个岔路口呢?其实方法很简单,只要让右手始终贴着右边的墙壁一路往前走,那么就会自动执行上面这个走法,并且最总一定能走出迷宫,如下图实例。
这种总是以深度作为前进关键词,不碰到死胡同就不回头,因此把这种搜索的方式称为深度优先搜索(Depth First Search ,DFS)。
而且我们应该注意到,DFS会走遍所有的路径,并且每次都走到死胡同就代表一条完整的路径形成。所以DFS是一种枚举所有完整路径以遍历所有情况的搜索方法。
再讲一个例子,其中包含DFS思想 :有n件物品,每件物品的重量为w[i],价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中,使得在选入背包的物品重量和不超过容量V的前提下,让背包中物品的价值之和最大,求最大价值。n在范围[1,20]
在这个问题中,需要从n件物品中选择若干件物品放入背包,使他们价值之和最大。这样的话,对每件物品都有选择或者不选择,而这就是所谓的岔道口,那么什么是死胡同呢?题目要求选的物品的重量总和不超过V,因此一旦选择的物品重量总和超过V,就会达到死胡同,需要返回最近的岔道口。
显然每次都要对物品进行选择,因此DFS函数的参数中必须记录当前处理的物品编号index。而题目中涉及了物品重量和价值,因此也需要参数来记录在处理物品之前,已选的物品总重量sumW与总价值sumC。于是DFS函数定义如下:
void DFS(int index,int sumW,int sumC)(....)
如果选择不放入index号物品,那么sumW与sumC就将不变,接下来处理index+1号物品,即前往DFS(index+1, sumW, sumC)这条分支,如果选择放入index号物品,那么sumW将增加当前物品的重量w[index],sumC将增加当前物品的价值c[index],接着处理index+1,即前往DFS(index+1,sumW+w[index],sumC+c[index])这条分支。
一旦index增长到了n,则说明已经把n件物品处理完毕(因为物品的下标从0到n-1),此时记录的sumW和sumC就是所选物品总重量和总价值。如果sumW不超过V且sumC大于一个全局记录最大总价值的变量maxValue,就说明当前这种选择方案可以的到更大的价值,于是用sumC更新maxValue。
#include<cstdio.h>
const int maxn = 30;
int n,V,maxValue = 0; //物品件数n,背包容量V,最大价值maxVallue
int w[maxn],c[maxn]; //
void DFS(int index,int sumW,int sumC){
if(index == n){
if(sumW <= V && sumC > maxValue){
maxValue = sumC;
}
return;
}
DFS(index+1,sumW,sumC) //不选index件物品
DFS(index+1,sumW+w[index],sumC+c[index]); //选择index物品
}
int main(){
scanf("%d%d",&n,&V);
for(int i=0;i<n;i++){
scanf("%d",&w[i]);//每件物品的重量
}
for(int i=0;i<n;i++){
scanf("%d\n",&c[i]);//每件物品的价值
}
DFS(0,0,0); //初始时为第0件物品,当前总重量和总价值都为0
printf("%d\n",maxValue);
return 0;
}
但是,因为每件物品都有两种选择,因此上面代码的复杂度为O(2^n),很明显不是很优秀。上面的代码总是把n件物品的选择全部确定以后才会会更新最大值,但是忽略了背包容量不超过V这个特点。也就是说,完全可以把sumW的判断加入“岔道口”中,只有当sumW<=V时才进入岔道,这样效率会高很多。
void DFS(int index, int sumW, int sumC){
if(index == n){
return;
}
DFS(index + 1, sumW, sumC); //不选第index件物品
//只有加入第index件物品后未超过容量V,才能继续
if(sumW + w[index] <= V){
if(sumC + c[index] > ans){
ans = sumC + c[index]; //更新最大价值maxValue
}
DFS(index + 1, sumW + w[index], sumC + c[index]); //选择第index件物品
}
}
可以看到,原来第二条岔路口是直接进入的,但是这里先判断加入第index件物品后能否满足容量不超过V的要求,只用当条件满足时才更新最大价值以及进入这条岔道,这样可以降低计算量,使算法在数据不极端时有很好的表现。这种通过题目条件的限制来节省 DFS计算量的方法称为剪枝。