前言

很多算法问题都可以用搜索解决：将所有可能的方案列出来，一一尝试。虽然笨，但行之有效。比如170多年前的八皇后问题，大数学家高斯也曾回答错误，而今天即使一个入门程序员，都可以利用计算机的强大计算能力，获得正确答案。

互联网行业，程序员技术面试少不了算法题，算法反映的是程序员的内功。原始的搜索即“一一尝试”，可能打败100年前的数学家，但绝对不能通过今天的算法面试。

本文是作者刷完14道搜索相关算法题总结出来的, 希望对大家算法提升有帮助:

首先通过迷宫可视化动画，引入深度优先搜索和广度优先搜索两种策略接着分析何种情况下，采用哪种策略会更好，并指出在遍历时要尽可能提前剪枝然后给到三个具体案例最后给到搜索算法总结和刷题建议如何用搜索策略破解迷宫？

迷宫在游戏领域中很常见，在《最强大脑》中的大型蜂巢迷宫道具也吸引了众多眼球。谈到迷宫，不得不提到搜索策略。

下面两张图，分别是小B和小D两个人探索并走出同一迷宫的过程。其中左上角是迷宫起点，右下角是终点。

迷宫: 广度优先搜索

第一张图中，小B遇到分叉路口后，会在每个路口都尝试走一步，由内向外，像波纹一样层层推进，是一种地毯式搜索，不放过遇到的任意一个路口。最后的绿色方格，表示重建出来的一条可行路径。

迷宫：深度优先搜索

第二张图中，小D遇到分叉路口后，逐个尝试，如果遇到死胡同表示失败，立即返回，返回的途径用红色标出来，表示此路不通。绿色表示当前可行的路径。一直按上述的策略尝试，直到找出一条路径走出迷宫。有点孤军深入的味道，运气好的话，可很快走出迷宫，运气差的话，可能之前走的某条路全部标红，要全部放弃掉，重新尝试其他路径。

小B的全局指挥能力强，有点像《火影忍者》中的鸣人，利用影分身术，遇到分叉洛口，分身就变多，多个分身，按部就班，层层推进，最终只要一个分身走出迷宫，即完成任务。

广度优先搜索: 影分身并行

小D的毅力很强，即使多次失败，仍然不停尝试。只有不怕失败的人，靠毅力和记忆力（失败路径标红）走出迷宫。

深度优先搜索：毅力，不怕失败

人生何尝不是一座迷宫？每个人都在为自己的梦想奔波着。你才取哪种策略呢？像小B一样稳妥的层层推进, 还是像小D一样赌一把?

最短路径问题: 应采用广度优先搜索策略

广度优先搜索：像波纹一样，层层扩展

广度优先搜索(BFS)按照层次顺序遍历，想象一下将一个石子投入水中，波纹一圈一圈往外扩展的样子。搜索过程中遇到的第一个解一定是距离起始位置最近的，所以第一个解，一定就是一个最优解，此时搜索算法可以终止。因此，广度优先搜索可以用来求解最短路径问题，当题目中出现最短，最少的等字眼时，常用BFS来求解。比如：

完成任务所需的最少时间输出最少的变换步数

深度优先搜索搜索到的的解不一定是离起始位置最近的，只有将所有方案全局搜索完毕，即将所有的解决方案都试完，最优进一步比较，才能从所有解中找出最优的解。而BFS不需要搜索完，就能找到最短路径。

故相对于深度优先搜索，广度优先搜索适合解决最短路径问题。

具体实现时，通常用借助队列这种数据结构来实现，广度优先搜索伪代码如下:

BFS伪代码

人生中的广度优先有需要有全局观，眼界开阔，按部就班，升职加薪，水到渠成，似乎指日可待。

连通性问题：应采用深度优先搜索策略

深度优先搜索：快速试错，快速迭代

深度优先搜索(DFS)是一条路走到黑，走不通后，退回一步重试。有点碰运气的味道，快速试错，快速迭代。所以找到的这条路不一定是最短路径，不适合解决最短路径问题。深度优先搜索，适合求解有没有的问题(比如是否连通)或找出一个解的问题。当题目中出现是否、一个解等字眼时，通常用深度优先搜索求解。

一般而言，广度优先搜索层层遍历保存的信息较多，需要保存搜索过程中的状态（通过一个队列来记录）；而深度优先搜索任意时刻，只需维护一条路径的状态，故从空间复杂度上说，深度优先搜索比广度优先搜索有优势。

在不需要找出最优解，只需一个解的时候，深度优先搜索比较合适。

深度优先搜索的核心逻辑:

递归下去：利用递归函数，深入搜索回溯上来：不再满足条件，停止递归调用，返回上一层调用

DFS伪代码

人生中的深度优先，会造就专家，比如谈判专家、算法专家等, 都是在很多次的经验教训练出来的。

需要遍历全部路径的问题：DFS/BFS均可，但注意剪枝

剪枝，加快搜索速度

当需要遍历全部路径时，DFS/BFS均可，个人觉得采用没有明确的界限。但此时，因为需要遍历所有路径，需要一些技巧，来过滤掉没有必要搜索的路径，以提高搜索速度。

常用的技巧有:

记忆化搜索，将重复利用的结果记录下来，下次用时直接取结果，而不是再次搜索试探法: 限将当前节点放入路径后，根据数据规律计算上下限，看结点是否满足，尽可能提前预判路径是否有效

总之，充分利用题目的限定条件，尽可能的提前结束掉路径(即剪枝)。

正所谓: 小树不修不直溜，人不修理哏赳赳。不要等长成大树后再纠正，成本太高，要从小教育。

案例

八皇后问题

八皇后作为经典古老的问题，数学家高斯曾认为有76种方案，与真实答案92 相比漏掉了16种方案。

问题描述:

将八位皇后放在8ｘ8的棋盘上，要求任意两皇后不能处于同一横线、竖线、斜线上。否则，两个皇后会打架。输出方案数及前三种方案（字典序)

分析:

输出方案总数，需要遍历所有可能路径。与最短路径无关，用深度优先搜索

解决方案如下:

八皇后解法

滑雪寻找最长滑坡问题

滑雪问题

问题描述：

给定一个区域（二维数组），数组的值为该点的高度，找到最长滑坡长度。其中一个点可以从上下左右滑向相邻的4个点之一。

分析:

搜索所有可能的滑坡，找到最大值; 跟最短路径无关，采用深度优先搜索利用记忆化搜索，剪枝：即当某个点A作为起始点的最长滑坡已知时，滑坡B-A-End的A-END部分，直接取结果，而不用重复结算。

解决方案：

滑雪问题解法

小结

注意上述两个深度优先搜索案例中, 虽然均为深度优先搜索，但solve()函数中:

八皇后调用一次dfs()即可而滑雪问题在两重for循环中调用多次dfs()

原因如下:

八皇后: 相当于构造了一个哨兵根节点滑雪问题: 无法构造哨兵根节点

参照下面的两张图理解：

八皇后的哨兵根节点

滑雪问题：无法构造哨兵根结点

象棋跳马遍历问题

跳马问题

问题描述:

给定nｘm的棋盘，和马的坐标，计算出马到达棋盘任意一点最少要走多少步

分析:

看到“最少”字言，在进一步分析确定，可通过广度优先搜索解决

解决方案:

跳马问题解法

总结对于最短路径问题，采用广度优先搜索，层层推进对于是否连通或找出一个解的问题，采用深度优先搜索，孤军深入对于遍历全部路径的问题, 深度优先或广度优先搜索都可以，但注意剪枝，降低搜索复杂度，避免不必要的搜索。

最后，大家如果有人在刷题，留心下刷题攻略，建议：

不要走极端：一味的深度优先，虽然某专题上功力深厚，但技术面上会很窄；一味的广度优先，深度上不够广度、深度两者要权衡好： 深度达到一定指标的情况下，广度优先；广度达到一定指标的情况下，深度优先剩下的就是一次又一次的迭代和坚持，加深对算法的理解主要参考资料luogu 14道题目列表: p1032, p1126, p1141, p1162, p1143, p1092, p1019, p1101, p1219, p1605, p1118, P1434, p1433, p1074《算法导论》第22章《算法竞赛入门经典》，第二版，第7章

题目列表

附录: 14道搜索题目