深度优先搜索

• 三、深度优先搜索
• • 1、普通深度优先搜索
  • • 1.1 迷宫问题描述
    • 1.2 代码实现
  • 2、抽象深度优先搜索问题
  • • 2.1 和为K问题
    • • 2.1.1 问题描述
      • 2.1.2 解题思路
      • 2.1.3 代码实现
    • 2.2 八皇后问题
    • • 2.2.1 问题描述
      • 2.2.2 解题思路
      • 2.2.3 代码实现
  • 3、剪枝深度优先搜索问题
  • • 3.1 基本概念
    • • 3.1.1最优性剪枝
      • 3.1.2 重复性剪枝
      • 3.1.3问题描述及代码实现
      • 3.1.4奇偶性剪枝
  • 4、迷宫问题
  • • 4.1 问题描述
    • 4.2 问题分析
    • 4.3 代码实现
  • 5、炸弹问题
  • • 5.1 问题描述
    • 5.2 解题思路
    • 5.3 代码实现

三、深度优先搜索

1、普通深度优先搜索

1.1 迷宫问题描述

迷宫问题的解法要用到DFS，对上下左右四个方向进行尝试，如果沿某个方向不能走到终点，就原路返回，继续尝试其它方向，知道走出迷宫。
首先找到起点S，走到每个点时，按照左、下、右、上的顺序尝试。每次走到下一个点以后，就把这个点当作起点S，继续按照顺序尝试。如果每个点上下左右四个方向都尝试了，便回到走到这个点之前的点，这一步称为回溯。继续尝试其它方向，直到所有点都尝试过上下左右四个方向。
程序
首先处理好边界条件，什么时候结束搜索？如果搜索到了终点，自然要结束搜索，边界条件是maze[x][y] == ‘T’

1.2 代码实现

#include<Iostream> #include<String> Using namespace std; int n,m; string maze[110]; bool vis[110][110];//定义vis bool in(int x,int y){return 0 <= x && 0 <= y && y < m; } bool dfs(int x,int y){If(maze[x][y] == ‘T’){//边界条件，表示到达终点结束搜索Retrun true;}vis[x][y]=1;//用VIS数组标记当前走过的点maze[x][y]=‘m’;//把走过的点用字符‘m’标记int tx=x-1,ty=y;//向上走if(in(tx,ty)&&maze[tx][ty]!=‘*’&&!vis[tx][ty]){//如果不是‘*’且没有访问，就继续在该位置进行搜索if(dfs(tx,ty)){//如果该位置能搜到解，直接返回trueretrun true;}}tx=x,ty=y-1;if(int(tx,ty)&&maze[tx][ty]!=‘*’&&!vis[tx][ty]){If(dfs(tx,ty)){Retrun true;}}tx=x+1,ty=y;if(int(tx,ty)&&maze[tx][ty]!=‘*’&&!vis[tx][ty]){If(dfs(tx,ty)){Retrun true;}}tx=x,ty=y+1;if(int(tx,ty)&&maze[tx][ty]!=‘*’&&!vis[tx][ty]){If(dfs(tx,ty)){Retrun true;}}//如果四个方向都搜索完也没找到路径，函数结束运行，返回到上一层递归，并且把刚才访问这个位置时做的标记全部撤销。vis[x][y]=0;maze[x][y]=‘.’;return false; } int main(){cin>>n>>m;//输入迷宫地图for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maze[i][j] == ‘s’){x=i,y=j;}}}if（dfs(x,y)）{for(int i=0;i<n;i++){cout<<maze[i]<<endl;}}else{cout<<“NO!<<endl”} }

2、抽象深度优先搜索问题

2.1 和为K问题

2.1.1 问题描述

给定N个整数，要求选出K个数，使得选出的K个数和为SUM

2.1.2 解题思路

对于每一个数，枚举选或者不选两种情况，可以用DFS思想完成这样的枚举过程。在搜索过程中，用S来记录当前选择的数值总和，K记录选择的数的个数，deep表示当前正在枚举第几个数是否选择。
在第一层DFS时，可以枚举是否选第一个数，如果选第一个数则让S加上第一个数且k加一，DFS进入下一层；否则DFS直接进入下一层。
这里还需要借助全局变量、参数或修改数组中的元素的值等方式来标识出当前的层数。
在第二层，对第二个数做同样的处理，DFS的过程中记录已经选取的数的个数，如果已经选取了K个数，判断S的值是否等于SUM。
对于每一层，都有选和不选两个选择。不同的选择，都会使得搜索进入完全不同的分支继续搜索。
可以根据搜索状态构建一张抽象的图，图上的一个顶点就是一个状态，而图上的边就是状态之间的转移关系。

2.1.3 代码实现

#include<iostream> using namespace std; int n,k,sum,ans; int a[40]; //i表示当前正在选择第几个数，cnt表示选取了几个数，s表示选取的数的和 void dfs(int i,int cnt,int s){if(i==n){//边界条件，对所有的数都进行了选择if(cnt==k && s==sum){//判断选出来的数的个数是否等于k,和是否为sumans++;}return 0;}dfs(i+1,cnt,s);//不选取第i个数，cnt和s都不会变化dfs(i+1,cnt+1,s+a[i]);//选取第i个数，cnt+1,s+a[i] } int main(){cin>>n>>k>>sum;for(int i=0;i<n;i++){cin>>a[i];}ans=0;//初始化ans为0dfs(0,0,0);//将所有参数初始化为0cout<<ans<<endl;return 0; }

2.2 八皇后问题

2.2.1 问题描述

在8✖️8的国际象棋上摆上8个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

2.2.2 解题思路

解决这个问题，可以对每一行的八个位置一个一个进行尝试，如果可以放下，就填下一行，直到最后一行，这就是一个可行的方案。

2.2.3 代码实现

#include<iostream> using namespace std; int ans = 0; bool col[10],x1[20],x2[20];//标记列和两条对角线 bool check(int r,int i){//对应的列和两条对角线没有被占用就可以放置return !col[i] && !x1[r+i] && !x2[r-i+8]; } void dfs(int r){if(r==8){//递归出口，如果填完前八行，代表是一种可行方案ans++;return;}for(int i=0;i<8;i++){//对第r行的每一列进行一一尝试if(check(r,i)){//判断是否能放置col[i]=x1[r+i]=x2[r-i+8]=true;//r-i可能为负值，加上偏移量dfs(r+1);col[i]=x1[r+i]=x2[r-i+8]=false;}} } int main(){dfs(0);cout<<ans<<endl;return 0; }

3、剪枝深度优先搜索问题

3.1 基本概念

剪枝就是通过一些判断，砍掉搜索树上不必要的子树。如某个结点对应的子树的状态都不是我们要的结果，就没必要对这个分支进行搜索，砍掉这个子树就是剪枝。

3.1.1最优性剪枝

对于求最优解的一类问题，通常可以用最优性剪枝，比如在求解迷宫问题最短路径时，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝，可以省去大量冗余的计算。此外，在搜索是否有可行解的过程中，一旦找到了一组可行解，后面的搜索都不必再进行了，这算是最优性剪枝的一个特例。

3.1.2 重复性剪枝

对于某一些特定的搜索方式，一个方案可能会被搜索很多次，这样是没有必要的。比如在这个问题中：给定n个整数，要求选出K个数，使得选出的K个数的和为sum。如果搜索方法是每次从剩下的数中选出一个数，一直搜到第k层，那么1，2，3这个选取方法能被搜到6次，这是没必要的，因为我们只关注选出来的数的和，而不会关注选出来的数的顺序，所以这里可以用重复性剪枝。若规定选出的数的位置是递增的，在搜索的时候，用一个参数记录上一次选取的数的位置，那么此次选择，从这个数之后开始选取，这样最后选出来的方案也就不会重复。

3.1.3问题描述及代码实现

从0、1、2、···、29这30个数中选择8个数，使得和值为200.

#include<iostream> using namespace std; int n,k,sum,ans; int a[40]; bool xuan[40]; void dfs(int s,int cnt,int p){if(s>sum || cnt>k){return;}if(s==sum && cnt==k){ans++;}for(int i=pos;i<n;i++){//直接从pos的位置选择数if(!xuan[i]){xuan[i]=1;dfs(s+a[i],cnt+1);xuan[i]=0;}} } int main(){n=30;K=8;sum=200;for(int i=0;i<30;i++){a[i]=i+1;}ans=0;dfs(0,0,0);cout<<ans<<endl;return 0; }

3.1.4奇偶性剪枝

4、迷宫问题

4.1 问题描述

有一个n*m大小的迷宫。其中字符’表示’起点，字符‘D’表示出口，字符’X’表示墙壁。字符’.‘表示空地，从’S’出发走到’D’，每次只能向上下左右相邻的位置移动，并且不能 走出地图，也不能走进墙壁。
每次移动消耗1时间，走过的路都会塌陷，因此不能走回头路或者原地不动。现在已知出口的大门会在T时间打开，从起点能否逃离迷宫。
数据范围n,m<=10,T<=50。

4.2 问题分析

分析：我们需要用dfs搜索每一条路线，并且只需搜到T时间就可以了（这是一个可行性剪枝）

奇偶性剪枝：

如上图所示，将n*m的网格染成黑白两色。我们记录每一个格子的行列数之和为x,如果x为偶数，那么格子就是白色，反之为奇数时就为黑色。容易发现相邻的两个格子颜色肯定不一样，也就是说每走一步颜色都会不一样。更普遍的结论：走偶数步不会改变颜色，走奇数步会改变颜色。
那么如果起点和终点颜色一样，而T是奇数的话，就不可能逃离迷宫。同理，如果起点和终点颜色不一样，而T是偶数的话也不能逃离。遇到这两种情况时，就不用进行DFS了，直接输出“NO”。
这里用一个通用公式：
（x1+y1+x2+y2+T)%2!=0 该公式为真，就不可能逃出迷宫

4.3 代码实现

#include<iostream> using namespace std; int n,m,T; char mat[10][10]; bool vis[10][10]; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; bool ok; void dfs(int x,int y,int t){if(ok)return;if(t==T){if(mat[x][y]=='D'){ok=true;} return;}vis[x][y]=true;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx<0||ty>=n||ty<0||ty>=m||mat[tx][ty]=='X'||vis[tx][ty]){continue;}dfs(tx,ty,t+1);}vis[x][y]=false; } int main(){cin>>n>>m>>T;for(int i=0;i<n;i++){cin>>mat[i];}int sx,sy,ex,ey;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mat[i][j]=='S'){sx=i;sy=j;}if(mat[i][j]=='D'){ex=i;ey=j;}}}if((sx+sy+ex+ey+T)%2!=0){//利用奇偶性剪枝判断是否能够到达迷宫 cout<<"NO"<<endl;}else{ok=false;dfs(sx,sy,0);//搜索 if(ok)cout<<"YES"<<endl;elsecout<<"NO"<<endl;} }

5、炸弹问题

5.1 问题描述

在一个n*m的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把其所在的行和列的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输入两个正数n，m，用空格隔开。
接下来n行，每行输入一个长度为m的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。
数据约定：
对于60%的数据：1<=n,m<=100;
对于100%的数据：1<=n;m<=1000;
输出格式
输出一个证书，表示最少需要手动引爆的炸弹数。
样例输入
5 5
00010
00010
01001
10001
01000
样例输出
2

5.2 解题思路

本题首先不要纠结炸弹的个数，要把可以连锁引爆的炸弹当做一个集合，每个集合分别引爆一个炸弹，便能将所有炸弹引爆。因此本题将手动引爆最少的炸弹个数，转化为求炸弹的集合数。
递归参数：地图坐标x，y
递归边界：当前行列是否被访问过
递归体：遍历所在行，列，如果有炸弹，继续引爆
剪枝：visx[], visy[], mp[x][y] = ‘0’，以保证行列只访问一次

5.3 代码实现

#include<stdio.h> #include<iostream> using namespace std; int n, m; char mat[1005][1005]; bool row[1005], col[1005]; //x,y坐标 void boom(int x, int y) {mat[x][y] = 0;//引爆炸弹，修改防止重复访问 //递归边界 //递归体//访问同一行if(!row[x]){row[x] = true;//标记行被访问 for(int i = 0; i < m; ++i){if(mat[x][i] == '1')//同一行存在炸弹 {boom(x, i);}}}//访问同一列if(!col){col[y] = true;for(int i = 0; i < n; ++i){if(mat[i][y] == '1')//同一列存在炸弹 {boom(i, y);}} } } int main() {scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", mat[i]);}int cnt=0;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(mp[i][j] == '1'){++cnt;boom(i, j);}}}printf("%d\n", cnt);return 0; }

总结

以上是生活随笔为你收集整理的LQ训练营(C++)学习笔记_深度优先搜索的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。