dfs与bfs搜索以及剪枝优化

DFS

dfs是什么？

深度优先搜索算法（Depth First Search，简称DFS），一句话总结：DFS 是一种“一条路走到黑，撞墙再回头”的算法，像极了玩迷宫游戏时的策略。

• 核心目标：遍历或搜索树、图中的所有可能路径。
• 通俗比喻：假设你被困在一个迷宫里，入口是起点（S），出口是终点（T），路（.）可以走，墙（*）不能走。DFS 的策略是：
  1. 遇到岔路时，随便选一条路（比如先右转）。
  2. 走到死胡同时，原路返回到上一个岔路口，换另一条路继续走。
  3. 最终找到出口（如果存在的话），但可能绕远路。

核心

深度优先

• 思想：优先往深处探索，直到无路可走。
• 举例：假设迷宫中有三条分叉路：A→B→C（死胡同）、A→D→E→T（出口）。DFS 会先走 A→B→C，发现是死胡同后回退到 A，再走 A→D→E→T。

回溯

• 思想：走到尽头后，回退到上一个岔路口，换另一条路继续探索。
• 关键操作：递归返回时恢复状态（比如取消标记）。
• 举例：在迷宫 A→B→C 中，回退到 B 时，需要将 C 标记为未访问，否则后续路径无法重新探索 C。

标记已访问节点

• 思想：记录走过的节点，避免重复访问和死循环。
• 关键操作：用一个数组visited（vis）记录是否访问过某个位置。
• 举例：在迷宫中，如果从 A→B→A（环路），未标记会导致无限循环。标记后，第二次访问 A 时会直接跳过。

练习题

表示上下左右的方向数组：

intdir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};或intdx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

迷宫（一）

#include<bits/stdc++.h>usingnamespacestd;constintN=11;intn,m,vis[N][N];chara[N][N];constintdir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};boolf;voiddfs(intx,inty){if(a[x][y]=='T'){f=1;return;}for(intk=0;k<4;k++){intxx=x+dir[k][0];intyy=y+dir[k][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]!='*'&&!vis[xx][yy]){vis[xx][yy]=1;dfs(xx,yy);}}}voidsolve(){cin>>n>>m;intx=-1,y=-1;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='S'){x=i,y=j;}}}dfs(x,y);if(f){cout<<"yes"<<'\n';}else{cout<<"no"<<'\n';}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT=1;// cin>>T;while(T--)solve();return0;}

BFS

引入

广度优先搜索算法（Breadth First Search，简称BFS）通常指利用队列结构逐层扩展状态的搜索方式，适合求解最短路径或最少步骤类问题。

解释

• 核心思想：按层扩展，从起点开始逐层扫描可到达的位置。首次遇到终点时的路径长度即为最短路径。这种方式保证了搜索的层次性与最优性。

• 基本流程：在实际执行中，BFS 会从起点出发，先访问起点的所有直接可到达结点，这些可到达结点构成了搜索的第一层；接着，再以这些可到达结点为新的起点，依次访问它们的邻居，形成第二层；以此类推，不断向外扩展，直至找到目标结点或遍历完所有可达结点。这个过程中，算法会借助队列和访问数组vis，将每一层新发现的结点（访问数组中还没有记录过的）依次入队，确保同一层的结点按照访问顺序依次被处理，从而严格遵循「按层扩展」的逻辑。复杂度O(n)
  

练习题

迷宫（二）

#include<bits/stdc++.h>usingnamespacestd;constintN=15;typedefpair<int,int>PII;intn,m,vis[N][N],dist[N][N];charg[N][N];constintdir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};voidsolve(){cin>>n>>m;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){dist[i][j]=1e9;}}intx=-1,y=-1;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>g[i][j];if(g[i][j]=='S'){x=i,y=j;}}}queue<PII>q;q.push({x,y});vis[x][y]=1;dist[x][y]=0;while(!q.empty()){auto[x,y]=q.front();q.pop();for(intk=0;k<4;k++){intxx=x+dir[k][0];intyy=y+dir[k][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]!='*'&&!vis[xx][yy]){vis[xx][yy]=1;dist[xx][yy]=dist[x][y]+1;q.push({xx,yy});}}}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(g[i][j]=='T'){cout<<(dist[i][j]==1e9?-1:dist[i][j])<<'\n';return;}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT=1;// cin>>T;while(T--)solve();return0;}

优化

引入

DFS（深度优先搜索）是一种常见的算法，大部分的题目都可以用 DFS 解决，但是大部分情况下，由于DFS复杂度比较高，可以考虑使用一些实用的优化算法降低复杂度（俗称剪枝）。

常见的深搜模板，之后的模板将在此基础上进行修改。

intans=最坏情况,now;// now 为当前答案voiddfs(传入数值){if(到达目的地)ans=从当前解与已有解中选最优;for(遍历所有可能性)if(可行){进行操作;dfs(缩小规模);撤回操作;}}

其中的 ans 可以是解的记录，那么从当前解与已有解中选最优就变成了输出解。

剪枝方法

最常用的剪枝有三种，记忆化搜索、最优性剪枝、可行性剪枝。

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。

在搜索中，相同的传入值往往会带来相同的解，那我们就可以用数组来记忆。

模板

intg[MAXN];// 定义记忆化数组intans=最坏情况,now;voiddfs(传入数值){if(g[规模]!=无效数值)return;// 或记录解，视情况而定if(到达目的地)ans=从当前解与已有解中选最优;// 输出解，视情况而定for(遍历所有可能性)if(可行){进行操作;dfs(缩小规模);撤回操作;}}intmain(){memset(g,无效数值,sizeof(g));// 初始化记忆化数组}

最优性剪枝

在搜索中导致运行慢的原因还有一种，就是在当前解已经比已有解差时仍然在搜索，那么我们只需要判断一下当前解是否已经差于已有解。

模板

intans=最坏情况,now;voiddfs(传入数值){if(now比ans的答案还要差)return;if(到达目的地)ans=从当前解与已有解中选最优;for(遍历所有可能性)if(可行){进行操作;dfs(缩小规模);撤回操作;}}

可行性剪枝

在搜索过程中当前解已经不可用了还继续搜索下去也是运行慢的原因。

intans=最坏情况,now;voiddfs(传入数值){if(当前解已不可用)return;if(到达目的地)ans=从当前解与已有解中选最优;for(遍历所有可能性)if(可行){进行操作;dfs(缩小规模);撤回操作;}}

练习题

Missile Defence System
考虑可行性剪枝

考虑可行性剪枝，可以用贪心的思想。

如果对于一个导弹，我们有两个递增装置都能够拦截它，那么基于贪心，我们一定会选择目前高度最高的一个去拦截它（因为低的那一个“更有潜力”）

如现在有两个递增装置，第一个依次拦截了高度为 2 5 8 的三枚导弹，第二个拦截了 6 7 的两枚导弹，那么如果又来了一发高度为 9 的导弹，那么用第一个拦截一定会比第二个更优。

递减装置同理。

考虑最优性剪枝

当目前答案已经大于已知最优答案时，直接回溯即可。

#include<bits/stdc++.h>usingnamespacestd;constintN=55;intn,ans,a[N];vector<int>up,down;voiddfs(intnow){intx=up.size(),y=down.size();if(x+y>=ans)return;if(now>n){ans=min(ans,x+y);return;}for(inti=0;i<x;i++){if(a[now]>up[i]){inttemp=up[i];up[i]=a[now];dfs(now+1);up[i]=temp;break;}}if(!x||up[x-1]>=a[now]){up.push_back(a[now]);dfs(now+1);up.pop_back();}for(inti=0;i<y;i++){if(a[now]<down[i]){inttemp=down[i];down[i]=a[now];dfs(now+1);down[i]=temp;break;}}if(!y||down[y-1]<=a[now]){down.push_back(a[now]);dfs(now+1);down.pop_back();}}voidsolve(){while(cin>>n&&n){ans=1e9;up.clear(),down.clear();for(inti=1;i<=n;i++)cin>>a[i];dfs(1);cout<<ans<<'\n';}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT=1;// cin>>T;while(T--)solve();return0;}