深度优先搜索算法(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)

无减枝版本

#include<bits/stdc++.h>
using namespace std;
char Map[15][15];
int n,m,t,qx,qy,zx,zy;
int flag;
int dir[4][2]={-1,0,0,-1,1,0,0,1};//上下左右四个方向 
void dfs(int x,int y,int cnt){      //搜索
	if(x==zx&&y==zy&&cnt==t){   //如果位置和出口一样并且时间一样则为成功
		flag=1;
	}
	if(flag){               //只要有一次成功则直接return
		return;
	}   
	if(cnt>t){              //如果时间超出限制
		return;
	}
	for(int i=0;i<4;i++){       //四个方向寻求可以走的地方
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(xx<0||yy<0||xx>n-1||yy>m-1){     //如果超出地图
			continue;
		}
		else if(Map[xx][yy]!='X'){      //如果可以走
			Map[xx][yy]='X';            //标记为下次不能走
			dfs(xx,yy,cnt+1);       //进入搜索
			Map[xx][yy]='.';        //取消标记
		}
	}
}
int main(){
	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&(n||m||t)){
		for(int i=0;i<n;i++){
			scanf("%s",Map[i]);
			for(int j=0;j<m;j++){
				if(Map[i][j]=='S'){
					qx=i;
					qy=j;
				}
				if(Map[i][j]=='D'){
					zx=i;
					zy=j;
				}
			}
		}
		flag=0;
		Map[qx][qy]='X';    //将起点标记为不能走
		dfs(qx,qy,0);       /进入搜索
		if(flag){
			printf("YES\n");
		}
		else{
			printf("NO\n"); 
		}
	}
	return 0;
}

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

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

所以，在这里再次强调“剪枝”！

减枝

可以把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 但是要求时间是偶数的 都可以直接判断不可达！

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

伪代码

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

完整代码

#include<bits/stdc++.h>
using namespace std;
char Map[15][15];
int n,m,t,qx,qy,zx,zy;
int flag;
int dir[4][2]={-1,0,0,-1,1,0,0,1};//上下左右四个方向 
void dfs(int x,int y,int cnt){
	if(x==zx&&y==zy&&cnt==t){
		flag=1;
	}
	if(flag){
		return;
	}
	if(cnt>t){
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(xx<0||yy<0||xx>n-1||yy>m-1){
			continue;
		}
		else if(Map[xx][yy]!='X'){
			Map[xx][yy]='X';
			dfs(xx,yy,cnt+1);
			Map[xx][yy]='.';
		}
	}
}
int main(){
	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&(n||m||t)){
		for(int i=0;i<n;i++){
			scanf("%s",Map[i]);
			for(int j=0;j<m;j++){
				if(Map[i][j]=='S'){
					qx=i;
					qy=j;
				}
				if(Map[i][j]=='D'){
					zx=i;
					zy=j;
				}
			}
		}
		flag=0;
		Map[qx][qy]='X';
		int sum=t-abs(zx-qx)-abs(zy-qy);
		if(sum>=0&&sum%2==0){
			dfs(qx,qy,0);
		}
		if(flag){
			printf("YES\n");
		}
		else{
			printf("NO\n"); 
		}
	}
	return 0;
}