Life has its own fate, and meeting may not be accidental.

0%

深度优先搜索算法(DFS)

在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举)。

对于问题的第一个状态,叫初始状态,要求的状态叫目标状态。
搜索就是把规则应用于实始状态,在其产生的状态中,直到得到一个目标状态为止。

感谢杭电刘老师的ppt

什么是深度优先搜索

所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构和产生系统。正如前面所说的,搜索算法简而言之就是穷举所有可能情况并找到合适的答案,所以最基本的问题就是罗列出所有可能的情况,这其实就是一种产生式系统。

从根开始计算,到找到位于某个节点的解,回溯法(深度优先搜索)作为最基本的搜索算法,其采用了一种“一只向下走,走不通就掉头”的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。

借用刘老师的话

基本思想:从初始状态S开始,利用规则生成搜索树下一层任一个结点,检查是否出现目标状态G,若未出现,以此状态利用规则生成再下一层任一个结点,再检查是否为目标节点G,若未出现,继续以上操作过程,一直进行到叶节点(即不能再生成新状态节点),当它仍不是目标状态G时,回溯到上一层结果,取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态,就按该分支一直扩展到叶节点,若仍不是目标,采用相同的回溯办法回退到上层节点,扩展可能的分支生成新状态,…,一直进行下去,直到找到目标状态G为止。

DFS算法

  • 把起始节点S线放到OPEN表中。
  • 如果OPEN是空表,则失败退出,否则继续。
  • 从OPEN表中取最前面的节点node移到CLOSED 表中。
  • 若node节点是叶结点(若没有后继节点),则转向(2)。
  • 扩展node的后继节点,产生全部后继节点,并把他们放在OPEN表的前面。各后继结点指针指向node节点。
  • 若后继节点中某一个是目标节点,则找到一个解,成功退出。否则转向(2)循环。

DFS最重要的就是回溯,它的本质是递归!

我认为实质就是暴力枚举多种可能。

减枝

对于深度优先搜索来说减枝也是极为重要的。如果遍历了一些无关紧要的节点的话就会很浪费时间,如果数据小的话还看不出。一旦数据大,减枝所带来的优化将变得极为重要。

HDU-1010-Tempter of the Bone为例

题目

小狗在一个古老的迷宫中发现了一根骨头,这使他非常着迷。但是,当他捡起它时,迷宫开始摇晃,小狗可以感觉到地面下沉。他意识到骨头是一个陷阱,他拼命试图摆脱这个迷宫。

迷宫是一个矩形,大小为N×M。迷宫中有一扇门。刚开始时,门是关闭的,它将在第T秒打开一小段时间(少于1秒)。因此,小狗必须在第T秒精确到达门。每秒钟,他可以将一个块移动到上,下,左和右相邻的块之一。一旦他进入一个街区,该街区的地面将开始下沉并在下一秒消失。他不能在一个街区停留超过一秒钟,也不能搬到一个拜访的街区。可怜的小狗可以生存吗?请帮助他。

输入

输入包含多个测试用例。每个测试用例的第一行包含三个整数N,M和T(1<N,M<7;0<T<50),分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局,每行包含M个字符。角色是以下字符之一:

‘X’:小狗无法进入的墙块;
‘S’:小狗的起点;
‘D’:门;或
“.”:空白块。

输入以三个0终止。该测试用例将不被处理。

输出

对于每个测试用例,如果小狗可以存活,则在一行中打印“YES”,否则打印“NO”。

样例输入

4 4 5
S.X.
..X.
..XD
….
3 4 5
S.X.
..X.
…D
0 0 0

样例输出

NO
YES

典型的迷宫式搜索,每一步都只能走一次,并且只有时间刚刚好时,才能成功!

深搜代码(DFS)

无减枝版本

1
#include<bits/stdc++.h>
2
using namespace std;
3
char Map[15][15];
4
int n,m,t,qx,qy,zx,zy;
5
int flag;
6
int dir[4][2]={-1,0,0,-1,1,0,0,1};//上下左右四个方向 
7
void dfs(int x,int y,int cnt){      //搜索
8
	if(x==zx&&y==zy&&cnt==t){   //如果位置和出口一样并且时间一样则为成功
9
		flag=1;
10
	}
11
	if(flag){               //只要有一次成功则直接return
12
		return;
13
	}   
14
	if(cnt>t){              //如果时间超出限制
15
		return;
16
	}
17
	for(int i=0;i<4;i++){       //四个方向寻求可以走的地方
18
		int xx=x+dir[i][0];
19
		int yy=y+dir[i][1];
20
		if(xx<0||yy<0||xx>n-1||yy>m-1){     //如果超出地图
21
			continue;
22
		}
23
		else if(Map[xx][yy]!='X'){      //如果可以走
24
			Map[xx][yy]='X';            //标记为下次不能走
25
			dfs(xx,yy,cnt+1);       //进入搜索
26
			Map[xx][yy]='.';        //取消标记
27
		}
28
	}
29
}
30
int main(){
31
	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&(n||m||t)){
32
		for(int i=0;i<n;i++){
33
			scanf("%s",Map[i]);
34
			for(int j=0;j<m;j++){
35
				if(Map[i][j]=='S'){
36
					qx=i;
37
					qy=j;
38
				}
39
				if(Map[i][j]=='D'){
40
					zx=i;
41
					zy=j;
42
				}
43
			}
44
		}
45
		flag=0;
46
		Map[qx][qy]='X';    //将起点标记为不能走
47
		dfs(qx,qy,0);       /进入搜索
48
		if(flag){
49
			printf("YES\n");
50
		}
51
		else{
52
			printf("NO\n"); 
53
		}
54
	}
55
	return 0;
56
}

如果没有减枝也能搜索出来,但是会超时,因为浪费了很多不必要的时间

广度和深度优先搜索有一个很大的缺陷,就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。

所以,在这里再次强调“剪枝”!

减枝

可以把map看成这样:

  • 0 1 0 1 0 1
  • 1 0 1 0 1 0
  • 0 1 0 1 0 1
  • 1 0 1 0 1 0
  • 0 1 0 1 0 1

从为 0 的格子走一步,必然走向为 1 的格子
从为 1 的格子走一步,必然走向为 0 的格子
即:

0->1或1->0 必然是奇数步
0->0 走1->1 必然是偶数步

所以当遇到从 0 走向 0 但是要求时间是奇数的,或者, 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达!

则我们可以,判断他终点和起点是否一致。来进行减枝,减去一些不必要浪费的时间

伪代码

1
int sum=t-abs(zx-qx)-abs(zy-qy);
2
if(sum>=0&&sum%2==0){
3
	dfs(qx,qy,0);
4
}

完整代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
char Map[15][15];
4
int n,m,t,qx,qy,zx,zy;
5
int flag;
6
int dir[4][2]={-1,0,0,-1,1,0,0,1};//上下左右四个方向 
7
void dfs(int x,int y,int cnt){
8
	if(x==zx&&y==zy&&cnt==t){
9
		flag=1;
10
	}
11
	if(flag){
12
		return;
13
	}
14
	if(cnt>t){
15
		return;
16
	}
17
	for(int i=0;i<4;i++){
18
		int xx=x+dir[i][0];
19
		int yy=y+dir[i][1];
20
		if(xx<0||yy<0||xx>n-1||yy>m-1){
21
			continue;
22
		}
23
		else if(Map[xx][yy]!='X'){
24
			Map[xx][yy]='X';
25
			dfs(xx,yy,cnt+1);
26
			Map[xx][yy]='.';
27
		}
28
	}
29
}
30
int main(){
31
	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&(n||m||t)){
32
		for(int i=0;i<n;i++){
33
			scanf("%s",Map[i]);
34
			for(int j=0;j<m;j++){
35
				if(Map[i][j]=='S'){
36
					qx=i;
37
					qy=j;
38
				}
39
				if(Map[i][j]=='D'){
40
					zx=i;
41
					zy=j;
42
				}
43
			}
44
		}
45
		flag=0;
46
		Map[qx][qy]='X';
47
		int sum=t-abs(zx-qx)-abs(zy-qy);
48
		if(sum>=0&&sum%2==0){
49
			dfs(qx,qy,0);
50
		}
51
		if(flag){
52
			printf("YES\n");
53
		}
54
		else{
55
			printf("NO\n"); 
56
		}
57
	}
58
	return 0;
59
}