搜索算法

练习题目：

搜索：“暴力法”算法思想的具体实现。

搜索：“通用”的方法。一个问题，如果比较难，那么先尝试一下搜索，或许能启发出更好的算法。

技巧：竞赛时遇到不会的难题，用搜索提交一下，说不定部分判题数据很弱，得分了！

暴力法（Brute force，又译为蛮力法）。

搜索的基本思路：

1. 【BFS】Breadth-First Search，宽度优先搜索，或称为广度优先搜索。

2. 【DFS】Depth-First Search，深度优先搜索。

BFS：一群老鼠走迷宫

1. 老鼠无限多；

2. 在每个路口，都派出部分老鼠探索所有没走过的路；

3. 走某条路的老鼠，如果碰壁无法前行，就停下；

4. 如果到达的路口已经有别的老鼠探索过了，也停下；

5. 所有的道路都会走到，而且不会重复。

全面扩散、逐层递进

DFS：一只老鼠走迷宫

1. 只有一只老鼠；

2. 在每个路口，都选择先走右边（当然，选择先走左边也可以），能走多远就走多远；

3. 碰壁无法再继续往前走，回退一步，这一次走左边，然后继续往下走；

4. 能走遍所有的路，而且不会重复（回退不算重复）。

一路到底、逐层回退

DFS

• N皇后问题 ：N 皇后问题 - 蓝桥云课 (lanqiao.cn)

• 路径之谜 ：路径之谜 - 蓝桥云课 (lanqiao.cn)

DFS基础

• 形式上，递归函数是“自己调用自己”，是一个不断“重复”的过程。

• 递归的思想，是把大问题逐步缩小，直到变成最小的同类问题的过程，而最后的小问题的解是已知的，一般是给定的初始条件。

• 到达最小问题后，再“回溯”，把小问题的解逐个带回给更大的问题，最终最大问题也得到了解决。

• 递归有两个过程：递归前进、递归返回（回溯）。

• 在递归的过程中，由于大问题和小问题的解决方法完全一样，那么大问题的代码和小问题的代码可以写成一样。

• 一个递归函数，直接调用自己，实现了程序的复用。

模版伪码：

int check(参数){
    f(满足条件)
        return 1;
    return 0;
}
bool pd(参数){
    相应操作
}
void dfs(int step){
    判断边界pd()
    {
        不在边界内，即回溯
    }
    尝试每一种可能
    {
        满足check条件
        标记
        继续下一步dfs(step+1)
        恢复初始状态（回溯的时候要用到）
    }
}

DFS剪枝

剪枝：把不会产生答案的，或不必要的枝条“剪掉”。

剪枝的关键：剪什么枝、在哪里减。

剪枝是搜索常用的优化手段，常常能把指数级的复杂度，优化到近似多项式的复杂度。

• **可行性剪枝：**对当前状态进行检查，如果当前条件不合法就不再继续，直接返回。

• **搜索顺序剪枝：**搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态。

• **最优性剪枝：**在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索已经没有继续进行下去的意义，停止对当前分支的搜索。

• **排除等效冗余：**搜索的不同分支，最后的结果是一样的，那么只搜一个分支就够了。

• **记忆化搜索：**在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。将已经计算出来的结果保存起来，以后需要用到的时候直接取出结果，避免重复运算，从而提高了算法的效率。

BFS（求最短路径）

• 长草：长草 - 蓝桥云课 (lanqiao.cn)

BFS基础

BFS搜索的原理：“逐层扩散”。从起点出发，按层次从近到远，逐层先后搜索。

编码：用队列实现。

应用：BFS一般用于求最短路径问题，BFS的特点是逐层搜索，先搜到的层离起点更近。

最短路径：BFS法

BFS的特点：逐层扩散。

• 往BFS的队列中加入邻居结点时，按距离起点远近的顺序加入：先加入距离起点为1的邻居结点，加完之后，再加入距离为2的邻居结点，等等

• 搜完一层，才会继续搜下一层。

最短路径：从起点开始，沿着每一层逐步往外走，每多一层，路径长度就增加1。

所有长度相同的最短路径都是从相同的层次扩散出去的。

搜到第一个到达终点的路径，就是最短路径。

模版伪码：

int check(参数){
    if(满足条件)
    	return 1;
    return 0;
}
bool pd(参数){
	相应操作
}
void bfs(){
    1.把根节点放入队列尾端;
    2.每次从队列中取出一个节点;
    3.Check判断是不是答案，如果是结束算法return;
    4.把当前取出的节点扩展，如果扩展后的节点经Pd()后符合要求，就放入队列，不符合就不放;
    5.转到步骤2，循环执行。
}
如果所有节点被扩展完了，没有找到答案就无解。

BFS判重

set判重

map判重

搜索相关习题

蓝桥云课习题集：

青蛙跳杯子102，发现环108，合根植物110，填字母游戏113，机器人塔118，

四平方和122，取球博弈123，卡片换位125、生命之树131，穿越雷区141、

长草149、小朋友崇拜圈182，剪格子211，版本分支223，迷宫与陷阱229，

调手表230，分考场237，最长子序列244，九宫重排261，网络寻路263，

危险系数264，约数倍数选卡片265，字母阵列621，魔方状态643，算式649，

凑平方数653，方格填数664，完美正方形685，五星填数687，生成回文数691，

走迷宫1216，N皇后问题1508，最少操作数1509。