欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深度优先搜索(DFS)

程序员文章站 2022-06-11 14:22:56
...

咱们现讲一个有趣的事情,当我们身处在一个巨大的迷宫中,没有任何帮组我们如何走出这迷宫呢?有一种看上去很盲目但实际上很有效的方法。

以当前的位置为起点,沿着一条路向前走,当碰到岔路口的时候,选择一个岔路口前进。如果选择的这个岔路前方是一条死路,就退回到这个岔路口,选择另一条岔路前进。如果岔路中存在新的岔路口,那么仍然按照上面的方法枚举新岔路口的每一条岔路。这样,只要迷宫存在出口,那么这个方法就一定能找到它。

有人也许会问,如果第一个岔路口处选择了一条没有出路的分支,而这个分支比较深,并且路上多次出现新的岔路口,那么在发现这个分支是一个死路后,如何退出到最初的这个岔路口呢?其实方法很简单,只要让右手始终贴着右边的墙壁一路往前走,那么就会自动执行上面这个走法,并且最总一定能走出迷宫,如下图实例。
深度优先搜索(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计算量的方法称为剪枝。

相关标签: C++