当前位置：首页 > news >正文

保研考研机试攻略：第六章——搜索（2）

news 来源：原创 2024/9/19 1:43:11

🍦🍦🍦今天我们继续来学习搜索的后半部分：深度优先搜索（DFS）、搜索剪枝技巧、终极骗分技巧等内容。我们一起加油鸭ヾ(≧▽≦*)o ~ go go go~

🧊🧊🧊6.4 深度优先搜索（DFS）

🥥例题：DreamJudge 1563

🥥例题：DreamJudge 1564

🧊🧊🧊6.5 搜索剪枝技巧

什么是剪枝？

剪枝的原则？

1.可行性剪枝

2.最优性剪枝

3.记忆化搜索

4.搜索顺序剪枝

🧊🧊🧊6.6 终极骗分技巧

1、利用预处理的思想

2、暴力剪枝

3、利用贪心的思想

4、利用概率论的思想

🧊🧊🧊6.4 深度优先搜索（DFS）

深度优先搜索的实现形式就是递归，如果把递归的流程画出来，那么我们可以得到一棵递归树，其实就是一个多叉树。

BFS 和 DFS 有什么区别呢？

对于一棵二叉树，BFS 就是二叉树的层次遍历，一层一层的扩展下去；DFS 就是二叉树的中序遍历，一条路走到底，然后回溯走第二条，直到所有路都走完。

大家需要注意的是，DFS一般情况下效率不如BFS，比如求DFS中的迷宫的最短路径使用DFS就会超时。

🥥例题：DreamJudge 1563

直接用DFS模板，但是数据量大的时候会超时，如下代码：（后边会有剪枝部分的学习）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {1, 0, 0, -1, -1, 0, 0, 1};//右下左上
int ans;
//使用深度优先搜索求解
void dfs(int x, int y, int step) {if (step >= ans) return;//一个小剪枝，当步数超过答案就不用继续if (mpt[x][y] == 'E') {//找到终点ans = min(ans, step);return;}for (int i = 0; i < 4; i++) {//上下左右四个方向int nx = x + dir[i][0];int ny = y + dir[i][1];if ((mpt[nx][ny] == '*' || mpt[nx][ny] == 'E')&&vis[nx][ny] == 0) {vis[nx][ny] = 1;dfs(nx, ny, step+1);vis[nx][ny] = 0;}}
}
int main() {int h, w;while (scanf("%d%d", &h, &w) != EOF) {if (h == 0 && w == 0) break;int sx = 0, sy = 0;memset(mpt, 0, sizeof(mpt));memset(vis, 0, sizeof(vis));for (int i = 1; i <= h; i++) {scanf("%s", mpt[i] + 1);for (int j = 1; j <= w; j++) {if (mpt[i][j] == 'S') {sx = i, sy = j;//记录起点坐标}}}ans = 99999999;dfs(sx, sy, 0);printf("%d\n", ans);}return 0;
}

🥥例题：DreamJudge 1564

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[8][2] = {1,0,0,-1,-1,0,0,1,1,1,1,-1,-1,1,-1,-1};
//使用深度优先搜索求解
int dfs(int x, int y) {vis[x][y] = 1;for (int i = 0; i < 8; i++) {//8 个方向int nx = x + dir[i][0];int ny = y + dir[i][1];if (mpt[nx][ny] == '@' && vis[nx][ny] == 0) {dfs(nx, ny);}}
}
int main() {int h, w;while (scanf("%d%d", &h, &w) != EOF) {if (h == 0 && w == 0) break;int sx = 0, sy = 0;memset(mpt, 0, sizeof(mpt));memset(vis, 0, sizeof(vis));for (int i = 1; i <= h; i++) {scanf("%s", mpt[i] + 1);}int ans = 0;for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {if (vis[i][j] == 0 && mpt[i][j] == '@') {ans++;dfs(i, j);}}}printf("%d\n", ans);}return 0;
}

🧊🧊🧊6.5 搜索剪枝技巧

什么是剪枝？

常用的搜索有 DFS 和 BFS。BFS 的剪枝通常就是判重，因为一般 BFS 寻找的是步数最少，重复的话必定不会在之前的情况产生最优解。深搜，它的进程近似一颗树(通常叫 DFS 树)。

而剪枝就是一种生动的比喻：把不会产生答案的，或不必要的枝条“剪掉”。

剪枝的关键就在于剪枝的判断：什么枝该剪，什么枝不该剪，在什么地方减。

剪枝的原则？

正确性，准确性，高效性。

常用的剪枝有：可行性剪枝、最优性剪枝、记忆化搜索、搜索顺序剪枝。

1.可行性剪枝

如果当前条件不合法就不再继续搜索，直接 return。这是非常好理解的剪枝，搜索初学者都能轻松地掌握，而且也很好想。一般的搜索都会加上。

dfs(int x)
{if(x>n)return;if(!check1(x))return;.... return;
}

2.最优性剪枝

如果当前条件所创造出的答案必定比之前的答案大，那么剩下的搜索就毫无必要，甚至可以剪掉。我们利用某个函数估计出此时条件下答案的‘下界’，将它与已经推出的答案相比，如果不比当前答案小，就可以剪掉。

long long ans=987474477434487ll;
... Dfs(int x,...)
{if(x... && ...){ans=....;return ...;}if(check2(x)>=ans)return ...; //最优性剪枝for(int i=1;...;++i){vis[...]=1;dfs(...);vis[...]=0;}
}
//一般实现：在搜索取和最大值时，如果后面的全部取最大仍然不比当前答案大就可以返回。
//在搜和最小时同理，可以预处理后缀最大/最小和进行快速查询。

3.记忆化搜索

记忆化搜索其实很像动态规划（DP）。

它的关键是：如果对于相同情况下必定答案相同，就可以把这个情况的答案值存储下来，以后再次搜索到这种情况时就可以直接调用。

还有就是不能搜出环来，不能互相依赖。

long long ans=987474477434487ll;
... Dfs(int x,...)
{if(x... && ...){ans=....;return ...;}if(vis[x]!=0) return f[x];vis[x]=1;for(int i=1;...;++i){vis[...]=1;dfs(...);vis[...]=0;f[x]=...;}
}