526互联

关于DFS

发布时间 2023-06-17 22:42:42作者: haozexu

概述

所谓深度优先搜索（以下称为dfs，depth first search），这个高尚的名字，它是什么呢？

我认为，他是一种借助计算机计算能力的枚举。

是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故称之为“剪枝”。
from csdn

但是他又和普通枚举有什么区别呢？

dfs是基于递归实现的，从名字来看，这很能体现dfs的深度特点。

所以，dfs会从初态一直选择下面的其中一个状态扩展（体现为搜索树上的一个儿子），一直扩展到叶子节点（终态）。dfs的这种深度使他可以更快地接近目标

而普通枚举通常而言由于枚举方向的不确定性（或不易确定）而不方便进行枚举

是不是很不好理解？
来看一道题

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * nn∗n的格点组成，每个格点只有2种状态，..和 # ，前者表示可以通行，后者表示不能通行。
同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点AA走到点BB，问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#)，则看成无法办到。

这是经典的走地图问题，为什么不好用普通枚举做呢？

如果用普通枚举，那么最好的方法就是设f[i][j]表示可以从i到j，最后枚举两两点，再从中间寻找一个中介点进行扩展（dp思想）

但是这样浪费也太多了，有些点完全八竿子打不着，但是我们还是要枚举。

如果用dfs，它每次只会尝试一条路径，每一步之间当然是很好确定的，降低了浪费和实现难度。

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int t,n;
bool vis[N][N];
int sx,sy,ex,ey;
const int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
bool check(int x,int y){
	if(x<1||x>n||y<1||y>n||vis[x][y]) return false;
	else return true;
}
void readin(){
	cin>>n;
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char ch;
			cin>>ch;
			if(ch=='#') vis[i][j]=1;
		}
	}
	cin>>sx>>sy>>ex>>ey;
	sx++,sy++,ex++,ey++;
}
bool dfs(int x,int y){
	if(x==ex&&y==ey){
		return true;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(check(nx,ny)){
			vis[nx][ny]=1;
			bool ret=dfs(nx,ny);
			if(ret) return true;
			vis[nx][ny]=0;
		}
	}
	return false;
}
int main(){
	cin>>t;
	while(t--){
		readin();
		bool ret=dfs(sx,sy);
		cout<<(ret?"YES\n":"NO\n");
	}
}

众所周知，dfs还有一个兄弟叫bfs，我简单罗列了他们的区别

X 实现 适用场景 思想区别
dfs 递归 一步步确定的问题，有前后依赖性 执着往下走，这使得有时dfs可能会有很大损耗（例如：网络流FF）
bfs 队列 广泛用于图上，或者可以转换为图的问题 一层层考虑，在一般没有分层这个概念时不适用（例如：枚举全排列）
具体的说明等到bfs总结在做

结构

一般的dfs结构

void dfs(参数){
	if(边界){
		操作
		return;
	}
	for(下一个状态){
		if(判断状态合法){
			标记
			dfs(下一个)
			取消标记
		}
	}
	return;
}

请注意边界条件，如果不正确很有可能引起递归爆栈MLE

经典应用

1.杂项

普通枚举可以解决的大部分问题dfs也可以解决。通常效率相差不大但dfs思想更为清晰（不过递归会带来常数上的损耗）。

2.图上求联通块

Link

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 \(N\times M(1\leq N\leq 100, 1\leq M\leq 100)\) 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

只需枚举每一个点，以此扩展即可。

#include<bits/stdc++.h>
using namespace std;
char mp[101][101];
bool vit[101][101];
int dx[8]={0,0,-1,-1,-1,1,1,1};
int dy[8]={1,-1,-1,0,1,-1,0,1};
int n,m;
bool check(int x,int y)
{
	if(x<1||x>n||y<1||y>m||mp[x][y]=='.'||vit[x][y])
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
void dfs(int x,int y)
{
	vit[x][y]=1;
	for(int i=0;i<8;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(check(nx,ny)==1)
		{
			dfs(nx,ny);
		}
	}
}
int main()
{
	int ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
				cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]=='W'&&!vit[i][j])
			{
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;
}

优化

通常有5种方式：

  1. 最优化剪枝
  2. 可行性剪枝
  3. 排除等效冗余
  4. 记忆化
  5. 优化搜索顺序

其中1、2、4是较为常用的。

典例：

小木棍：

#include<bits/stdc++.h>
using namespace std;
int n,num[70],goal,cnt,sum,ans=0x3f3f3f3f;
bool vis[70];
inline bool dfs(int k,int len,int last)//last:最后失败 
{
	if(len==goal)
	{
		if(dfs(k+1,0,n))
		{
			return true;
		}
	}
	if(k>=cnt) return true;
	int cant=0;
	for(register int i=last;i>=1;i--)//last前面都已经失败 
	{
		if(!vis[i]&&len+num[i]<=goal&&cant!=num[i])
		{
			vis[i]=true;
			if(dfs(k,len+num[i],i-1))	return true;//考虑不搜索i-1之前的区间(i-1是因为排序) 
			//因为循环能执行到i，是因为之前的木棍都已经失败或被用过，虽然不能保证last之后的都没有访问过，但也不用再考虑
			 
			vis[i]=false;
			cant=num[i];//这个木棍失败
			if(len==0||len+num[i]==goal) return false;
			//len==0且失败时，说明当前方案不可能再拼接剩下的空木棍，不可能是答案
			//len+num[i]==goal且失败时，说明当前用一根能拼好目标失败，那用别的方法不仅会占用更多的短木棍，也不能得到成功 
		}
	}
	return false;
}
int main()
{
	cin>>n;
	int l=0;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
		if(num[i]>50) 
		{
		n--;
		continue;	
		}
		l=max(l,num[i]);
		sum+=num[i];
	}
	sort(num+1,num+1+n);//先拼大的，占空间 
	for(register int i=l;i<=sum;i++)
	{
		if(sum%i==0)
		{
			goal=i;
			cnt=sum/i;
			memset(vis,false,sizeof vis);
			if(dfs(0,0,n))
			{
				cout<<i;
				return 0;
			}
		}
	}
	cout<<sum;
	return 0;
}

这道题需要同时使用剪枝123

关于“优化搜索顺序”：
这个比较少见。

[USACO07OCT]Obstacle Course S

#include<bits/stdc++.h>
using namespace std;
char mp[105][105];
int sx,sy,cnt,ans=0x3f3f3f,n;
int gox[4]={0,0,-1,1},goy[4]={-1,1,0,0};
int vis[105][105];
bool check(int x,int y)
{
	if(x<1||x>n||y<1||y>n||cnt>=vis[x][y]||mp[x][y]=='x') return false;
	else return true;
}
void dfs(int x,int y,int fx,bool fi)
{
	if(mp[x][y]=='B')
	{
		ans=min(ans,cnt);
		return;
	}
	if(cnt>=ans) return;
	for(int i=0;i<4;i++)
	{
		int nx=x+gox[i],ny=y+goy[i];
		if(check(nx,ny))
		{
			
			if(i!=fx&&!fi) cnt++;
			vis[nx][ny]=cnt;
			dfs(nx,ny,i,false);
			if(i!=fx&&!fi) cnt--;
		}
	}
	return;
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("p1-4.out","w",stdout);
	cin>>n;
	memset(vis,0x3f,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]=='A')
			{
				sx=i;
				sy=j;
				vis[i][j]=0;
			}
		}
	}
	dfs(sx,sy,0,true);
	if(ans==0x3f3f3f) cout<<-1;
	else cout<<ans;
}

如果修改dxdy数组顺序就不能AC（其实这个是有点巧的事情）

关于记忆化搜索：

是dp的一种实现方式。此处可见dfs与枚举其实有很大关系。
有一个简单例子：
求斐波那契数列的第k项

int fib(int n){
	if(Ans[n]) return Ans[n];
	if(n==1||n==2) return n;
	Ans[n]=fib(n-1)+fib(n-2;
	return Ans[n];
}

将算过的先存起来，避免重复计算

EOF

感谢观看。\(\huge QwQ\)