搜索算法 • CoderXL's Blog

这部分内容配合【每日一题】第六周 ↗食用更佳。

什么是搜索#

按一定规则和顺序在状态之间转移，并不断检测目标条件是否满足的过程。

形式化地，一个搜索问题包含五个基本要素，可以被定义为如下五元组：

\text{Problem} = \left< S, A, T, s_0, G\right>

其中，

$S$ 是所有可能状态的集合；

$A=A(s)$ 是在给定状态 $s$ 下，所有可以采取的行动的集合；

$T=T(s,a) \in S$ 是在给定的状态 $s$ 和行动 $a$ 下，明确状态将会如何转移的函数；

$s_0$ 是搜索的初始状态；

$G=G(s) \in \{\mathrm{True},\mathrm{False}\}$ 是判断状态 $s$ 是否满足目标条件的函数。

基于这些符号，可以定义：一个搜索问题就是从 $s=s_0$ 出发，每次选取 $A(s)$ 中的动作，并按照 $T$ 转移，不断尝试寻找使得 $G(s) = \mathrm{True}$ 的状态 $s^*$ ，这样的 $s^*$ 称为一个解。

不难看出，状态空间、动作集合、转移函数这三者可以构成一个抽象的图。因此任何搜索问题都可以直观而不失严谨性地理解为一种图上游走。

此外，一些搜索问题的目标可能不只是找到解，而是要找到通向解的路径，甚至是通向解的最短路径等等。

搜索的顺序#

深度优先搜索, Depth-First Search, DFS#

每次到达一个状态时，先选择一条分支，继续进行更深一层的搜索。到达尽头之后逐步回溯，再尝试其它分支。

要实现“回溯”，需要借助一种后进先出（Last-in-First-out, LIFO）的数据结构，称为“栈”。栈中记录了当前的搜索路径，回溯操作只需要从栈顶弹出即可。在递归实现中，栈通常通过递归调用自动实现。

可以把 DFS 的过程想象为一个人在走迷宫。

下面这个动画演示了 DFS 搜索 6 号节点的过程。请注意，DFS 在找到 6 号节点之后，仍然需要依次回溯才能结束搜索。与动画交互以促进直观理解：

flowchart LR
1((1)) ---> 2((2)) ---> 3((3)) ---> 4((4)) ---> 5((5))
3 --->6(((6)))
2 --->7((7))

classDef highlight fill:#ffe08a,stroke:#d97706,stroke-width:1px,color:#111827;

block-beta
columns 10
  n1["1"]:2 n2["2"]:2 n3["3"]:2 n4["4"]:2 n5["5"]:2

Back

优点：空间复杂度低（但使用递归实现时需要考虑栈空间限制）；

缺点：状态空间很深的时候，可能需要很久才能到达答案所在的分支。

时间复杂度 $O(V+E)$ .

广度优先搜索, Breadth-First Search, BFS#

每次到达一个状态时，将该状态的所有可能后继状态都加入到队列末尾，当前状态从队头离开。每次取出队头进行处理。

与栈不同，队列是一种先进先出（First-in-First-out, FIFO）的数据结构。

可以把 BFS 的过程想象为水洒在地上逐渐泛开。

下面这个动画演示了 BFS 搜索 6 号节点的过程。与动画交互以促进直观理解：

flowchart LR
1((1)) ---> 2((2)) ---> 3((3)) ---> 4((4)) ---> 5((5))
3 --->6(((6)))
2 --->7((7))
1 ---> 8((8))
1 ---> 9((9))

classDef highlight fill:#ffe08a,stroke:#d97706,stroke-width:1px,color:#111827;

block-beta
columns 8
  n8["8"]:2 n9["9"]:2 n3["3"]:2 n7["7"]:2

Back

优点：适用于分支较多而答案较浅的搜索；遍历顺序与深度一致，适用于求解最短路；

缺点：在大部分树形状态空间中，空间复杂度高。

时间复杂度 $O(V+E)$ .

优化#

可以看到，两种搜索顺序各有优劣，因此也衍生出了很多将它们进行融合和改进以提升性能的方法。

剪枝（Pruning）#

如果在搜索中，能够确定某个分支一定不可能通向解（或最优解），那么可以提前终止对它的探索。这种提前终止的做法被称为“剪枝”，对应了搜索树中的分支被整体放弃。

剪枝技巧十分多样且庞杂，一般可以分为：搜索顺序优化、重复性剪枝、最优性剪枝、可行性剪枝。

搜索顺序优化#

在大部分搜索问题中，搜索树并不是完全树，这意味着有的分支浅，有的分支深。此时如果可以通过对状态进行排序，先从较浅的分支搜索，通常能更快找到解。

2. 重复性剪枝#

搜索过程中，如果可以判定几条分支是完全等效的，那么只需要对其中一条分支搜索即可。

最优性剪枝#

常见于最优化问题中。在搜索的过程中，我们可以估计一个解的下界/上界，并且不断修正我们的估计。如果某个分支的后续状态都超出了当前估计的下界/上界，说明它不可能通向最优解。

4. 可行性剪枝#

如果发现分支的状态不合法，则应当回溯。例如在数独求解问题中，如果当前某一行/列/九宫格填入了重复的数字，或者某行/列/九宫格待填充的空白格子数多于能填入的合法数字数量，那么这个状态就不可能通向合法解，因此可以提前终止对它的探索。

迭代加深（Iterative Deepening Search, IDS）#

DFS 空间复杂度小，但容易卡在较深的错误分支中；BFS 不会卡在某个错误分支中，因此可以较快地在分支多但答案较浅的状态空间中得到解，但它的空间复杂度通常较高。

迭代加深融合了二者的优点。它首先给定一个深度阈值 $k$ ，然后在深度不超过 $k$ 的范围内进行 DFS，如果没有找到答案则逐步增加 $k$ .

可以发现，对于一个固定的 $k$ ，这种方式的时间复杂度与 BFS 搜索到第 $k$ 层的时间复杂度是相同的，而由于不需要维护队列，空间复杂度接近于 DFS 的水平。

IDS 尤其适用于每一层的状态数量接近于上一层的 $\alpha$ 倍（即指数增长），且每个分支都很深的情况。在这种假设下，每次递增 $k$ 时造成的重复搜索，时间花费可以忽略不计。

下方的动画展示了 IDS 搜索 11 号节点的过程。可以看到深度阈值 $k$ 在每轮之间递增，防止 DFS 卡在某个较深的错误分支中。

flowchart LR
1((1)) ---> 2((2)) ---> 3((3)) ---> 4((4)) ---> 5((5))
4 ---> 6((6))
3 ---> 7((7)) ---> 8((8))
7 ---> 9((9))
2 ---> 10((10)) ---> 11(((11))) ---> 12((12))
11 ---> 13((13))
10 ---> 14((14)) ---> 15((15))
classDef highlight fill:#ffe08a,stroke:#d97706,stroke-width:1px,color:#111827;

block-beta
columns 8
  n1["1"]:2 n2["2"]:2 n3["3"]:2 n4["4"]:2

Back

启发式搜索#

一些情况下，我们虽然不知道答案会在哪些分支里，但是可以凭借经验/常识给出一个估计，让算法优先去探索更有可能存在解的分支。比如在求解八数码问题时，我们可以让算法优先探索那些和最终状态差距较小的状态，我们认为这些状态更有可能更快地到达最终状态。

基于该思想的算法称为 A*，更多可参考这篇 ↗。

折半搜索/双向搜索（Meet in Middle）#

有一类搜索问题的目的并不是找到解，而是要求在给定具体解时，找到通向解的路径。

这类问题往往可以使用折半搜索/双向搜索，即同时从起点和终点出发进行搜索，标记经过的中间状态（通常配合哈希实现）。一旦搜索到对方标记过的状态，就说明路径连通了起点和终点，搜索完成。

假设状态空间每一层状态数是上一层的 $\alpha$ 倍，起点终点的距离是 $d$ ，那么单向搜索的时间复杂度是 $O(\alpha^d)$ ，而折半搜索可以做到 $O(2 \alpha^{d/2}) = O(\sqrt{\alpha^d})$ 的时间复杂度，代价是需要花费更多空间记录中间状态。这也是算法设计中典型的空间换时间技巧。