算法总结--搜索

声明(叠甲)：鄙人水平有限，本文为作者的学习总结，仅供参考。

---

1. 搜索介绍

搜索算法包括深度优先搜索（DFS）和广度优先搜索（BFS）这两种，从起点开始，逐渐扩大寻找范围，直到找到需要的答案为止。从时间复杂度来说这与一般的暴力枚举来说没来太大的区别，这样的话我们为什么要使用搜索算法，而不直接使用暴力法呢？首先，搜索算法是暴力法一种优雅的写法，即优雅的暴力，可以为我们的代码减少冗长的嵌套 for 循环。其次搜索通过剪枝操作可以跳过一些无效状态，降低问题规模，从而使效率比直接的枚举所有答案要高。

---

2. DFS 与 BFS 的区别

类别	DFS	BFS
搜索类型	试探搜索	地毯搜索
所用的数据结构	栈（vector也是可以的）	队列
适用的题目	求方案总数	求最短路径
实现方法	一般结合回溯算法一同实现	将可行行方案放入队列，然后一一遍历

---

3. 举些栗子

3.1 BFS--马的遍历

题目描述

有一个 $n\ast m$ 的棋盘，在某个点 $(x,y)(x,y)$上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

这是一道经典 BFS 题,可说使模板题了，在解题前先介绍一下 BFS 的实现思路如下：

【1】 构建对应结构体与队列
【2】 初始化数据和初始点
【3】 根据初始点与遍历关系遍历其它符合要求的点
【4】 查询答案

根据 BFS 的实现思路可以容易的得到该题的代码如下

#include 
#define N_MAX 400
using namespace std;
int mp[N_MAX][N_MAX]; // mp[i][j] 表示马到（i，j）点所需的最少次数
int n,m,x,y;
// 定义 dx dy 便于运算
int dx[] = {-1,1,2,2,1,-1,-2,-2};
int dy[] = {-2,-2,-1,1,2,2,1,-1};
// [1] 定义数据结构体与duilie
struct point{
    int x,y; // 点的坐标
    int t;   // 马到该点的最少次数
};
queue que;

int main()
{
    // [2] 初始化数据
    memset(mp,-1,sizeof(mp));
    cin >> n >> m >> x >> y;
    mp[x][y] = 0; // 初始点为 0

    // [3] 搜索
    que.push((point){x,y,mp[x][y]}); // 先向队列中压入初始点
    while(!que.empty())
    {
        // 从队列中一个一个的遍历
        point p = que.front();
        que.pop(); // 记得弹出
        // 寻找满足条件的点,并压入队列中
        for(int i = 0;i < 8;i++)
        {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            // 判断是否合法
			if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == -1)
			{
				mp[nx][ny] = p.t + 1;
            	que.push((point){nx,ny,mp[nx][ny]});
			} 	
        }
    }
    // 输出结果
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {    
            cout << mp[i][j] << " ";
        }
        cout << endl;
    }
        
    return 0;
}

3.2 BFS--奇怪的电梯

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（$1\le i\le N$）上有一个数字 $K_i$（$0\le K_i\le N$）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3,3,1,2,5$ 代表了 $K_i$（$K_1=3$，$K_2=3$，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

这题也是一道 BFS 的模板题了，算是用于巩固了，具体 AC 代码如下

#include 
using namespace std;
#define N_MAX 201
struct point{
	int f;  // 所在层数
	int ki; // 拥有的数字
	int t;  // 需要按的次数 
};
queue que;
int ans[N_MAX];
int n,a,b;
int k[N_MAX];

int main()
{
	memset(ans,-1,sizeof(ans));
	cin >> n >> a >> b;
	for(int i = 1;i <= n;i++)
	{
		cin >> k[i];
	}
	ans[a] = 0;
	// bfs
	que.push((point){a,k[a],ans[a]});
	while(!que.empty())
	{
		point p = que.front();
		que.pop();
		int nf = p.f + p.ki; // 上 
		if(nf <= n && ans[nf] == -1)
		{
			ans[nf] = p.t+1;
			que.push((point){nf,k[nf],ans[nf]});	
		}
		nf = p.f - p.ki;    // 下  
		if(nf >= 1 && ans[nf] == -1)
		{
			ans[nf] = p.t+1;
			que.push((point){nf,k[nf],ans[nf]});	
		}		
	}  
	cout << ans[b] << endl;
	return 0;
}

3.4 DFS--数的组合

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

这是一到典型的 DFS 题，DFS 组要就是利用回溯算法进行解决，回溯的具体思路如下，其难点在于确定递归参数的确定

【1】 写递归出口（收果子）
【2】 循环遍历搜索，并进行剪枝优化
【3】 处理节点
【4】 递归
【5】 回溯，即取消处理节点时的朝左
该题代码如下：

class Solution {
public:
    vectorint>> ret; // 用于存储最后的结果
    vector<int> path;       // 用于存储中间的结果
    
    void bnf(int st,int n,int k)
    {
        // 收果子 （中止条件）
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        // 循环，并进行剪枝优化
        for(int i = st;i <= n - k + path.size() + 1;++i)
        {
            // 处理节点
            path.push_back(i);
            // 递归
            bnf(i+1,n,k);
            // 回溯
            path.pop_back();
        }
    }
    vectorint>> combine(int n, int k) {
        bnf(1,n,k);
        return ret;
    }
};

4.参考

代码随想录
洛谷搜索算法推荐题库
马的遍历的洛谷题解
本文到此结束，希望对您有所帮助。

• 1. 搜索介绍
• 2. DFS 与 BFS 的区别
• 3. 举些栗子
•     3.1 BFS--马的遍历
•         题目描述
•     3.2 BFS--奇怪的电梯
• 题目描述
•     3.4 DFS--数的组合
•         题目描述
• 4.参考

__EOF__