搜索算法

前置知识#

建议先阅读以下内容再进入本文：

• 算法分析基础与学习路线
• 查找算法
• 递归与回溯

知识点地图#

本篇属于「搜索算法」知识类别的通用篇，覆盖静态查找与无信息图搜索。

解决什么问题：在一大堆数据里找一个元素（查找），或在一个巨大的状态 空间里找一条从起点到终点的路径（图搜索）——分别该用什么算法、代价 各是多少、什么时候会出错。

什么时候用到：写查找逻辑前选型；刷题前建立 BFS/DFS 与二分的标准 写法；面试前复习复杂度与陷阱。

有信息搜索（双向 BFS、IDDFS、A*、IDA*）与博弈搜索（Minimax、 Alpha-Beta）已拆分至 055-InformedAndGameSearch，本篇不再展开。

1. 概述与学习目标#

1.1 什么是搜索算法#

搜索（Search）是计算机科学中最基础的操作之一——在状态空间（State Space）中寻找满足特定条件的状态序列。Stuart Russell 与 Peter Norvig 在《Artificial Intelligence: A Modern Approach》第 3 章将搜索算法形式化为在状态空间图 $G = (V, E)$ 上寻找从初始状态 $s_0$ 到目标状态 $g \in G$ 的路径问题。按信息量与策略可分为四大类：

1. 静态查找（Knuth TAOCP Vol.3 §6）：在固定数据集合中定位元素，包括线性查找 $O(n)$、二分查找 $O(\log n)$、哈希查找 $O(1)$；
2. 无信息搜索（Uninformed/Blind Search, Russell-Norvig §3.4）：无启发式信息，包括 BFS、DFS、UCS（Dijkstra）、IDDFS；
3. 有信息搜索（Informed/Heuristic Search, Russell-Norvig §3.5）：利用启发式函数 $h(n)$ 引导，包括贪婪最佳优先、A*、IDA*——本篇不展开，见 055 篇；
4. 对抗搜索（Adversarial Search, Russell-Norvig §5）：多智能体博弈，包括 Minimax、Alpha-Beta 剪枝、Monte Carlo Tree Search（MCTS）——本篇不展开，见 055 篇。

flowchart TD
    S["搜索"]
    S --> ST["静态查找 数组/链表<br/>线性 O(n)/二分 O(log n)/哈希 O(1)"]
    S --> U["无信息搜索 状态空间图<br/>BFS O(V+E)/DFS O(V+E)/UCS O(E log V)/IDDFS O(b^d)"]
    S --> I["有信息搜索 状态空间图+启发式<br/>A* O(b^d)/IDA* O(b^d)/贪婪 GBFS/WIDA*"]
    S --> G["对抗搜索 博弈树<br/>Minimax O(b^d)/MCTS/Alpha-Beta O(b^(d/2))"]

搜索算法的四大评估指标：

1. 完备性（Completeness）：若解存在，算法是否必能找到？
2. 最优性（Optimality）：算法找到的解是否为最优解？
3. 时间复杂度：状态扩展次数（用分支因子 $b$、解深度 $d$、最大深度 $m$ 衡量）；
4. 空间复杂度：内存占用。

一句话定义：搜索 = 在状态空间图中寻找从初始状态到目标状态的路径；静态查找 $O(\log n)$（二分）制霸有序数据，$O(1)$（哈希）制霸精确匹配；BFS/DFS 无信息搜索 $O(V+E)$ 服务通用图；A 启发式搜索用 $f(n) = g(n) + h(n)$ 引导方向，可达 $O(b^{\epsilon d})$；IDA 内存 $O(d)$ 服务内存受限场景；Alpha-Beta 剪枝 $O(b^{d/2})$ 主宰博弈树。**

1.2 学习目标#

完成本文档学习后，你将能够：

1. 记忆线性搜索 $O(n)$、二分搜索 $O(\log n)$、哈希查找 $O(1)$ 平均、BFS/DFS $O(V+E)$、UCS/Dijkstra $O(E \log V)$、IDDFS $O(b^d)$ 时间/$O(d)$ 空间、A* $O(b^d)$ 最坏/$O(b^{\epsilon d})$ 最优启发、IDA* $O(b^d)$ 时间/$O(d)$ 空间、Alpha-Beta 剪枝 $O(b^{d/2})$ 的形式化复杂度，复述各算法的完备性与最优性；
2. 理解 Shannon 1950 国际象棋程序（Philosophical Magazine 41:256-275）、Dijkstra 1959 最短路径（Numerische Mathematik 1:269-271）、Moore 1959 BFS（《The shortest path through a maze》）、Hart-Nilsson-Raphael 1968 A*（IEEE Trans. SSC-4(2):100-107）、Knuth-Moore 1975 Alpha-Beta 剪枝分析（Artificial Intelligence 6(4):293-326）、Korf 1985 IDA*（Artificial Intelligence 27(1):97-109）的历史脉络，说明各搜索算法的设计动机；
3. 应用线性搜索（含哨兵）、二分搜索（含 lower_bound/upper_bound/二分答案/浮点二分）、BFS（含分层、最短路径、双向 BFS）、DFS（含环检测、拓扑排序、回溯）、IDDFS、A*（含曼哈顿/欧氏/切比雪夫启发式）、IDA*、Minimax + Alpha-Beta 剪枝编写可运行的 Python/C++/Java 代码，解决 LeetCode 33、127、200、207、773、1091、64 等高频问题；
4. 分析状态空间图模型、启发式函数的可采纳性（$h(n) \leq h^*(n)$）与一致性（$h(n) \leq c(n, n') + h(n')$）、A* 最优性证明、IDA* 完备性证明、Alpha-Beta 剪枝正确性证明，掌握”图搜索、势能分析、对偶论证”三大核心论证方法；
5. 评估各搜索算法在”静态查找 vs 动态查找”、“精确匹配 vs 范围查询”、“无权最短路 vs 加权最短路”、“完备性 vs 时间复杂度”、“内存受限 vs 时间最优”维度上的优劣，识别 Google Maps A* 路径规划、Stockfish 国际象棋引擎、PostgreSQL B+ 树索引、Redis 字典、社交网络最短路径的选型动机；
6. 对比线性、二分、哈希、BST、BFS、DFS、双向 BFS、IDDFS、A*、IDA*、Minimax、Alpha-Beta 在时间复杂度、空间复杂度、完备性、最优性、启发式依赖、应用场景维度的差异；
7. 创造性设计基于搜索算法的开源项目解决方案，如 Google Maps A* 路径规划、Stockfish 国际象棋引擎、PostgreSQL B+ 树索引、Sokoban 求解器、八数码问题、迷宫生成与求解、社交网络 K 度好友推荐。

1.3 术语表#

1.4 全景对比表#

1.5 适用场景速查#

2. 历史动机与演进#

2.1 早期：图搜索与博弈论的奠基（1950-1959）#

Shannon 1950 国际象棋程序：Claude Shannon 在 1950 年《Philosophical Magazine》41:256-275 发表《Programming a Computer for Playing Chess》，首次提出用 Minimax + 启发式评估函数实现计算机下棋。Shannon 区分了”A 型”（暴力搜索固定深度）与”B 型”（选择性搜索关键分支）策略，奠定了 50 年国际象棋引擎的基础。1997 年 IBM 深蓝击败 Kasparov 用的就是 Shannon A 型 + Alpha-Beta 剪枝。

Dijkstra 1959 最短路径：Edsger Dijkstra 1959 在《Numerische Mathematik》1:269-271 发表《A note on two problems in connexion with graphs》，提出单源最短路径算法（即 Dijkstra 算法）与最小生成树算法。Dijkstra 在 Amsterdam 数学中心构思此算法时仅用 20 分钟，初衷是为演示 ARMAC 计算机的能力。论文仅 2.5 页，但开启了图论算法时代。

Moore 1959 BFS：Edward F. Moore 1959 在《Proceedings of the International Symposium on the Theory of Switching》285-292 发表《The shortest path through a maze》，独立提出 BFS 算法用于迷宫求解。C.Y. Lee 1961 在电路布线中独立再发现 BFS，故电路领域称”Lee 算法”。

2.2 启发式搜索的诞生（1968-1972）#

Hart-Nilsson-Raphael 1968 A*：Peter Hart、Nils Nilsson、Bertram Raphael 1968 在 SRI International 为 Shakey 机器人（首个移动智能机器人）设计路径规划时，提出 A* 算法。论文《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》发表于《IEEE Transactions on Systems Science and Cybernetics》SSC-4(2):100-107。

A* 的核心创新：将 Dijkstra 的 $g(n)$（已走代价）与启发式 $h(n)$（预估剩余代价）结合为评估函数 $f(n) = g(n) + h(n)$。论文证明：当 $h$ 可采纳（$h(n) \leq h^*(n)$）时，A* 找到最优解；当 $h$ 一致时，A* 无需重开闭表。1972 年作者在《SIGART Newsletter》37:28-29 发表更正。

Pohl 1971 双向搜索：Ira Pohl 1971 在《Machine Intelligence》6:127-140 发表《Bi-directional Search》，提出从起点与终点同时搜索，在中间相遇。理论上将复杂度从 $O(b^d)$ 降至 $O(b^{d/2})$，但实践中常因”相遇判定”开销而效果打折。

2.3 博弈树搜索分析（1975）#

Knuth-Moore 1975 Alpha-Beta 分析：Donald Knuth 与 Ronald Moore 1975 在《Artificial Intelligence》6(4):293-326 发表《An analysis of alpha-beta pruning》，首次严格分析 Alpha-Beta 剪枝的复杂度。证明：最优节点排序下 Alpha-Beta 仅需评估 $O(b^{d/2})$ 个叶节点（vs Minimax 的 $O(b^d)$），即”减半有效深度”。这篇论文还引入了”negamax”形式（负极大值），简化 Minimax 实现。

2.4 内存受限搜索（1985）#

Korf 1985 IDA*：Richard Korf 1985 在《Artificial Intelligence》27(1):97-109 发表《Depth-first iterative-deepening: An optimal admissible tree search》，提出 IDA*（Iterative Deepening A*）。IDA* 结合 IDDFS（迭代深化 DFS）的 $O(d)$ 空间与 A* 的启发式引导：每轮用 $f(n) = g(n) + h(n)$ 阈值限制 DFS 深度，下一轮阈值取上一轮越界节点的最小 $f$。

IDA* 在 15 数码问题（状态空间 $10^{13}$）上首次实现毫秒级求解，成为 AI 标准基准。Korf 后续还提出 WIDA*（加权 IDA*）、DFBnB（深度优先分支定界）、LRTA*（实时学习 A*）。

2.5 现代发展（1990-至今）#

Korf 1997 规约搜索：Korf 与 Zhang 1997 提出 Divide-and-Conquer Beam Search，将 IDA* 扩展至大规模问题。

Kishimoto 2002 并行 IDA*：用 Transposition Table（转置表）+ 并行化加速 IDA*。

Coulom 2006 MCTS：Rémi Coulom 2006 提出 Monte Carlo Tree Search（MCTS），用随机模拟替代启发式评估。AlphaGo（Silver et al. 2016）用 MCTS + 深度学习击败李世石。

时间线总结：

timeline
    title 搜索算法演进史
    1950 : Shannon 国际象棋程序 Minimax
    1959 : Dijkstra 单源最短路径
        : Moore BFS 迷宫求解
    1968 : Hart-Nilsson-Raphael A* (SRI Shakey)
    1971 : Pohl 双向搜索
    1972 : Hart-Nilsson-Raphael A* 更正
    1975 : Knuth-Moore Alpha-Beta 严格分析
    1985 : Korf IDA* 内存受限搜索
    1997 : Korf-Zhang 规约搜索
    2006 : Coulom MCTS 蒙特卡洛树搜索
    2016 : AlphaGo (Silver) MCTS + 深度学习击败李世石
    2018 : AlphaZero 自学习超越所有国际象棋引擎

2.6 关键设计决策#

1. A 为何用 $f = g + h$ 而非 $f = h$**：纯启发式（贪婪最佳优先）不完备，可能陷局部最优；$g$ 分量保证已走代价被计入，使 A 完备且最优；
2. IDA 为何用 DFS 而非 BFS*：BFS 需 $O(b^d)$ 内存，15 数码需 TB 级；DFS 仅 $O(d)$ 内存，可处理状态空间 $10^{13}$；
3. Alpha-Beta 为何”减半深度”：MAX 节点评估一个子节点后获得 $\alpha$，MIN 节点评估该子节点时若某叶节点 $\leq \alpha$ 即剪枝。最优排序下每两层仅评估约 $\sqrt{b}$ 个节点，总复杂度 $O(b^{d/2})$；
4. IDDFS 为何”重复搜索也高效”：每层搜索工作量 $b^i$，总工作量 $\sum_{i=0}^d b^i = O(b^d)$，最后一层占大头，重复开销仅 $O(b^{d-1})$ = $O(b^d)/b$ 比例。

3. 形式化定义#

3.1 状态空间图模型#

定义 3.1（状态空间）：搜索问题的状态空间为 5 元组 $\langle S, s_0, A, G, \text{succ} \rangle$：

• $S$：状态集合（可有限可无限）；
• $s_0 \in S$：初始状态；
• $A: S \to 2^A$：对每个状态 $s$，给出可执行动作集合；
• $G \subseteq S$：目标状态集合（或目标判定函数 $\text{goal}(s)$）；
• $\text{succ}: S \times A \to S$：后继函数，给定状态与动作返回新状态。

定义 3.2（搜索图）：状态空间对应有向图 $G = (V, E)$，其中 $V = S$，$(u, v) \in E$ 当且仅当 $\exists a \in A(u), \text{succ}(u, a) = v$。若动作有代价 $c(u, a, v)$，则图为加权图。

定义 3.3（解）：解是状态序列 $s_0, s_1, \ldots, s_k$ 满足 $s_k \in G$ 且 $\forall i, \exists a \in A(s_{i-1}), \text{succ}(s_{i-1}, a) = s_i$。最优解为代价 $\sum_{i=1}^k c(s_{i-1}, a_i, s_i)$ 最小者。

3.2 启发式函数的可采纳性与一致性#

定义 3.4（启发式函数）：$h: S \to \mathbb{R}_{\geq 0}$，$h(n)$ 估算从 $n$ 到目标的最低代价。约定 $h(g) = 0, \forall g \in G$。

定义 3.5（可采纳性 Admissibility）：$h$ 可采纳当且仅当 $\forall n \in S, \quad h(n) \leq h^*(n)$ 其中 $h^*(n)$ 为从 $n$ 到最近目标的真实最优代价。

定义 3.6（一致性 Consistency / Monotonicity）：$h$ 一致当且仅当对任意边 $(n, n')$， $h(n) \leq c(n, a, n') + h(n')$ 即满足三角不等式。

定理 3.1：一致性蕴含可采纳性。

证明：对最优路径 $n = n_0 \to n_1 \to \ldots \to n_k = g$ 反复应用一致性： $h(n_0) \leq c(n_0, n_1) + h(n_1) \leq c(n_0, n_1) + c(n_1, n_2) + h(n_2) \leq \ldots \leq \sum_{i=0}^{k-1} c(n_i, n_{i+1}) + h(g) = h^*(n_0) + 0 = h^*(n_0)$ $\square$

启发式构造方法：

1. 松弛法（Relaxation）：放宽问题约束得到易解问题，其最优解即原问题的可采纳启发式。例如 8 数码问题：
   • 原问题：每步移动一个数字，求最少步数；
   • 松弛问题 1：数字可瞬移到任意位置 → 曼哈顿距离之和；
   • 松弛问题 2：忽略空格位置，每数字独立 → 错位数字数（弱于曼哈顿）；
2. 模式数据库（Pattern Database, Korf 1997）：预计算部分子问题的最优解，作为启发式下界。15 数码用 7-7 划分模式数据库可降至毫秒级；
3. 绝对最大值：$h(n) = \max(h_1(n), h_2(n))$，若 $h_1, h_2$ 可采纳则 $h$ 可采纳。

3.3 A* 最优性证明#

定理 3.2（A 最优性）**：若 $h$ 可采纳，A 在树搜索中返回最优解；若 $h$ 一致，A* 在图搜索中返回最优解且无需重开闭表。

证明（树搜索 + 可采纳）：设 $G$ 为最优目标，代价 $C^* = h^*(s_0)$。反设 A* 返回次优解 $G'$，代价 $C' > C^*$。则在 $G'$ 被选中扩展时，最优路径上必存在某节点 $n$ 在 open 表中（因最优路径尚未完成）。由 A* 选择规则： $f(G') = g(G') + h(G') = C' + 0 = C' \leq f(n) = g(n) + h(n) \leq g(n) + h^*(n) \leq C^*$ （最后一步：$g(n) + h^*(n)$ 是经过 $n$ 的最优路径代价，$\geq$ 全局最优 $C^*$）故 $C' \leq C^*$，与 $C' > C^*$ 矛盾。$\square$

证明（图搜索 + 一致）：一致性保证首次扩展某节点时 $g(n) = g^*(n)$（最优代价），无需后续更新。证明略。

3.4 IDA* 完备性与最优性#

定理 3.3（IDA 完备性）**：若 $h$ 可采纳且状态空间有限、分支因子有限，IDA 必能找到解。

证明：阈值序列 $f_1 < f_2 < \ldots$ 严格递增（因可采纳 $h \leq h^*$，故阈值 $\leq C^*$）。最终阈值达到 $C^*$ 时，最优路径所有节点 $f \leq C^*$ 都被扩展，目标必被发现。$\square$

定理 3.4（IDA 最优性）**：若 $h$ 可采纳，IDA 返回最优解。

证明：IDA* 最终轮阈值为 $C^*$（最优代价）。在阈值 $\leq C^*$ 的 DFS 中，最优路径全部节点满足 $f(n) = g(n) + h(n) \leq g(n) + h^*(n) = C^*$（沿最优路径），均被访问。返回的第一个目标必为最优目标（次优目标 $f = C' > C^*$ 不被访问）。$\square$

3.5 Alpha-Beta 剪枝正确性#

定理 3.5（Alpha-Beta 正确性）：Alpha-Beta 剪枝返回与 Minimax 完全相同的最优值。

证明（不变式）：维护 $\alpha$（MAX 节点下界）与 $\beta$（MIN 节点上界）。剪枝条件 $\alpha \geq \beta$ 表明：当前节点的值已不影响根节点决策，故剪去剩余子树不影响结果。详细归纳证明见 Knuth-Moore 1975。$\square$

复杂度：

• 最坏（无剪枝）：$O(b^d)$，与 Minimax 相同；
• 最优排序：$O(b^{d/2})$，相当于”减半深度”；
• 平均：$O((b/\log b)^d)$（Knuth-Moore 1975）。

4. 线性搜索#

4.1 基本实现#

线性搜索是最朴素的策略：从头到尾逐个比较。虽 $O(n)$ 但在小数据（$n < 20$）下常数因子最小，且对无序链表无可替代。

def linear_search(arr: list[int], target: int) -> int:
    """线性搜索：返回 target 下标，不存在返回 -1"""
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def linear_search_sentinel(arr: list[int], target: int) -> int:
    """哨兵优化：省去每次循环的越界检查"""
    arr.append(target)  # 末尾放哨兵
    i = 0
    while arr[i] != target:
        i += 1
    arr.pop()
    return i if i < len(arr) else -1

def linear_search_ordered(arr: list[int], target: int) -> int:
    """有序数组的线性搜索：可提前终止"""
    for i, val in enumerate(arr):
        if val == target:
            return i
        if val > target:  # 有序性保证后续必更大
            return -1
    return -1

// C++ 实现
int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// 哨兵优化（C 风格数组）
int linearSearchSentinel(int* arr, int n, int target) {
    int last = arr[n - 1];
    arr[n - 1] = target;  // 末尾放哨兵
    int i = 0;
    while (arr[i] != target) i++;
    arr[n - 1] = last;  // 恢复
    if (i < n - 1) return i;
    return (last == target) ? n - 1 : -1;
}

4.2 复杂度分析#

4.3 工程价值#

• 小数据 n < 20：插入排序的小数据回退、C++ std::find 默认实现；
• 链表场景：链表无随机访问，二分不可用，线性搜索是唯一选择；
• 流式数据：未知长度的流只能线性扫描；
• 早终止优化：有序数据中 val > target 即可终止。

5. 二分搜索#

5.1 标准二分搜索#

二分搜索要求有序数组与随机访问，时间 $O(\log n)$，是静态查找的标准方案。

def binary_search(arr: list[int], target: int) -> int:
    """标准二分搜索"""
    low, high = 0, len(arr) - 1
    while low <= high:
        # 防整数溢出（Python 无此问题，C++/Java 必备）
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

5.2 二分变体：lower_bound 与 upper_bound#

C++ STL 提供两个核心变体：

def lower_bound(arr: list[int], target: int) -> int:
    """返回第一个 >= target 的位置（左闭右开区间）"""
    low, high = 0, len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

def upper_bound(arr: list[int], target: int) -> int:
    """返回第一个 > target 的位置"""
    low, high = 0, len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return low

# 应用：查找元素出现的范围 [left, right)
def search_range(arr, target):
    left = lower_bound(arr, target)
    right = upper_bound(arr, target)
    return [left, right - 1] if left < right else [-1, -1]

5.3 二分答案（参数搜索）#

当问题的判定比求解更容易时，可对答案进行二分：

def binary_search_answer(lo: int, hi: int, check: callable) -> int:
    """二分答案：在 [lo, hi] 内找最小可行值"""
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid  # 可行，尝试更小
        else:
            lo = mid + 1  # 不可行，增大
    return lo

# 示例：LeetCode 410 分割数组的最大值
def splitArray(nums: list[int], k: int) -> int:
    def check(max_sum: int) -> bool:
        cnt, cur = 1, 0
        for x in nums:
            if cur + x > max_sum:
                cnt += 1; cur = x
                if cnt > k: return False
            else:
                cur += x
        return True
    return binary_search_answer(max(nums), sum(nums), check)

5.4 浮点二分#

用于连续优化问题，如 LeetCode 69 求 $\sqrt{x}$：

def my_sqrt(x: int) -> int:
    """浮点二分求平方根"""
    if x <= 1: return x
    lo, hi = 1.0, float(x)
    eps = 1e-6
    while hi - lo > eps:
        mid = (lo + hi) / 2
        if mid * mid < x:
            lo = mid
        else:
            hi = mid
    return int(hi)

5.5 经典变体：旋转数组、峰值#

# LeetCode 33 旋转排序数组查找
def search_rotated(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        # 左半有序
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # 右半有序
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

# LeetCode 162 寻找峰值（任意一个）
def find_peak_element(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # 右侧有峰
        else:
            hi = mid  # 左侧含 mid 有峰
    return lo

5.6 复杂度与陷阱#

整数溢出陷阱（Bloch 2006）：mid = (low + high) / 2 在 low + high 超过 INT_MAX 时溢出。Java Arrays.binarySearch 1997 至 2006 年存在此 bug，约 9 年。修复为 mid = low + (high - low) / 2。

6. 哈希查找#

6.1 直接寻址与哈希#

哈希查找的核心是”直接寻址”的推广：

• 直接寻址表：键 $k$ 存于数组位置 $k$，要求键域 $U$ 与数组大小 $|U|$ 相当，空间 $O(|U|)$；
• 哈希表：用哈希函数 $h: U \to \{0, 1, \ldots, m-1\}$ 将键映射到 $m$ 个槽位，空间 $O(m)$。

冲突不可避免（鸽巢原理：$|U| > m$ 时必冲突），冲突处理策略：

1. 链地址法（Chaining）：每个槽位存链表，冲突元素追加。Python dict、Java HashMap（Java 8+ 链表长度 $\geq 8$ 转红黑树）；
2. 开放寻址（Open Addressing）：冲突时探查下一个槽位。探查序列：
   • 线性探针：$h(k, i) = (h'(k) + i) \mod m$
   • 二次探针：$h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m$
   • 双重哈希：$h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$
   • Robin Hood、Hopscotch、Cuckoo 等高级方案

6.2 完整实现#

class HashTable:
    """链地址法哈希表，自动扩容"""
    def __init__(self, capacity: int = 16, load_factor: float = 0.75):
        self.capacity = capacity
        self.size = 0
        self.load_factor = load_factor
        self.buckets: list[list[tuple]] = [[] for _ in range(capacity)]
    
    def _hash(self, key) -> int:
        return hash(key) % self.capacity
    
    def _resize(self):
        old = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)
    
    def put(self, key, value):
        if self.size >= self.capacity * self.load_factor:
            self._resize()
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        self.buckets[idx].append((key, value))
        self.size += 1
    
    def get(self, key, default=None):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return default
    
    def remove(self, key) -> bool:
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.buckets[idx]):
            if k == key:
                del self.buckets[idx][i]
                self.size -= 1
                return True
        return False

6.3 复杂度分析#

负载因子 $\alpha = n/m$。链地址法期望查找时间 $O(1 + \alpha)$，简单均匀哈希假设下 $\alpha = O(1)$ 即 $O(1)$。开放寻址要求 $\alpha < 1$，通常 $\alpha \leq 0.75$。

6.4 工业实现#

• Python dict：开放寻址 + 伪随机探查，$\alpha \leq 2/3$，扩容 2 倍或 4 倍；
• Java HashMap：链地址法，链表长度 $\geq 8$ 且 $\alpha \geq 0.75$ 时转红黑树；
• C++ std::unordered_map：链地址法，实现依赖厂商（libstdc++ / libc++ / MSVC）；
• Redis dict：链地址法，渐进式 rehash 避免阻塞；
• Google Abseil flat_hash_map：开放寻址 + Robin Hood，内存紧凑。

7. 广度优先搜索（BFS）#

7.1 算法思想#

BFS 从起始节点出发，按层次逐步扩展：先访问距离 1 的所有节点，再访问距离 2 的节点，依此类推。核心数据结构是 FIFO 队列。

图: 0 -- 1 -- 3
     |    |
     2 -- 4 -- 5

BFS 从 0 出发:
  第 0 层: {0}
  第 1 层: {1, 2}
  第 2 层: {3, 4}
  第 3 层: {5}
  访问顺序: 0, 1, 2, 3, 4, 5

BFS 关键性质：在无权图中，BFS 首次到达某节点时的路径就是最短路径。这使 BFS 成为无权图最短路径的标准算法。

7.2 Python 实现#

from collections import deque, defaultdict

def bfs(graph: dict, start) -> list:
    """BFS 遍历，返回访问顺序"""
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

def bfs_shortest_path(graph: dict, start, end) -> list | None:
    """BFS 求无权图最短路径"""
    if start == end: return [start]
    visited = {start}
    queue = deque([(start, [start])])
    while queue:
        node, path = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

def bfs_distance(graph: dict, start) -> dict:
    """BFS 计算从 start 到所有节点的最短距离"""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

def bfs_layered(graph: dict, start) -> list[list]:
    """分层 BFS，返回每层节点列表"""
    if not graph: return []
    layers = [[start]]
    visited = {start}
    while layers[-1]:
        next_layer = []
        for node in layers[-1]:
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    next_layer.append(neighbor)
        if next_layer:
            layers.append(next_layer)
    return layers

7.3 C++ 实现#

#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

vector<int> bfs(const vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> order;
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return order;
}

// 无权图最短路径
vector<int> bfsShortestPath(const vector<vector<int>>& graph, int start, int end) {
    int n = graph.size();
    vector<int> parent(n, -1);
    vector<bool> visited(n, false);
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        if (node == end) break;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                parent[neighbor] = node;
                q.push(neighbor);
            }
        }
    }
    // 回溯路径
    vector<int> path;
    for (int cur = end; cur != -1; cur = parent[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());
    return (path.back() == start) ? path : vector<int>{};
}

7.4 复杂度分析#

• 时间：$O(V + E)$，每个顶点入队出队各一次，每条边检查一次（无向图两次）；
• 空间：$O(V)$，队列与 visited 数组；
• 完备性：是（有限分支图）；
• 最优性：无权图是，加权图否（需 Dijkstra/UCS）。

7.5 工程应用#

1. 社交网络 K 度好友：LinkedIn、Facebook 用 BFS 找 K 度连接；
2. 无权迷宫最短路：LeetCode 1091 二进制矩阵最短路径；
3. 单词接龙（LeetCode 127）：从 beginWord 到 endWord 的最短变换序列；
4. 网络爬虫：BFS 抓取网页层级；
5. 消息广播：P2P 网络 Gossip 协议。

8. 深度优先搜索（DFS）#

8.1 算法思想#

深度优先搜索（Depth-First Search, DFS）沿一条分支尽可能深入，遇到死路则回溯探索其他分支。Tarjan 在 1972 年《Depth-First Search and Linear Graph Algorithms》（SIAM J. Comput. 1(2):146-160）系统化 DFS 的算法理论，证明其线性时间复杂度可解决诸多图问题（连通分量、拓扑排序、割点、桥、强连通分量）。

DFS 的核心特征：

1. LIFO 栈：后进先出，与 BFS 的 FIFO 队列相对；
2. 递归本质：自然对应递归调用栈；
3. 不完备：在无限分支图上可能陷入无限循环，需配合访问标记；
4. 不最优：找到的路径不一定最短。

8.2 Python 实现（递归与栈两种形式）#

from collections import defaultdict

class DFS:
    """深度优先搜索：递归与栈两种实现"""

    def __init__(self, graph: dict):
        self.graph = graph

    def dfs_recursive(self, start) -> list:
        """递归 DFS：返回访问顺序"""
        visited = set()
        order = []

        def _dfs(node):
            visited.add(node)
            order.append(node)
            for neighbor in self.graph.get(node, []):
                if neighbor not in visited:
                    _dfs(neighbor)

        _dfs(start)
        return order

    def dfs_stack(self, start) -> list:
        """显式栈 DFS：避免 Python 递归深度限制"""
        visited = set()
        order = []
        stack = [start]
        while stack:
            node = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            order.append(node)
            # 逆序入栈以保证与递归版访问顺序一致
            for neighbor in reversed(self.graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)
        return order

8.3 环检测（三色标记法）#

CLRS 第 22.3 节介绍三色标记：白色（未访问）、灰色（在递归栈中）、黑色（已完成）。若 DFS 过程中遇到灰色边，则存在环。

def has_cycle(graph: dict) -> bool:
    """有向图环检测：三色标记法。WHITE=0, GRAY=1, BLACK=2"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def _dfs(node) -> bool:
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                return True  # 回边，存在环
            if color[neighbor] == WHITE and _dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(color[n] == WHITE and _dfs(n) for n in graph)

8.4 拓扑排序（后序逆序）#

拓扑排序仅适用于 DAG（有向无环图）。DFS 后序的逆序即为一种合法拓扑序。Kahn 算法（BFS 入度法）是另一种实现。

def topological_sort(graph: dict, num_nodes: int) -> list:
    """DFS 后序逆序实现拓扑排序。要求图为 DAG。"""
    visited = [False] * num_nodes
    postorder = []

    def _dfs(node):
        visited[node] = True
        for neighbor in graph.get(node, []):
            if not visited[neighbor]:
                _dfs(neighbor)
        postorder.append(node)

    for n in range(num_nodes):
        if not visited[n]:
            _dfs(n)
    return postorder[::-1]  # 后序的逆序

8.5 连通分量#

无向图的连通分量可用 DFS 一次扫描求出。Tarjan 1972 提出基于 DFS 的线性时间算法。

def connected_components(graph: dict, num_nodes: int) -> list:
    """无向图连通分量"""
    visited = [False] * num_nodes
    components = []

    def _dfs(start, comp):
        visited[start] = True
        comp.append(start)
        for neighbor in graph.get(start, []):
            if not visited[neighbor]:
                _dfs(neighbor, comp)

    for n in range(num_nodes):
        if not visited[n]:
            comp = []
            _dfs(n, comp)
            components.append(comp)
    return components

8.6 割点与桥（Tarjan 算法）#

割点（Articulation Point）：删除该点后图不再连通。桥（Bridge）：删除该边后图不再连通。Tarjan 1974《A note on finding the bridges of a graph》（IPL 2(6):160-161）给出 $O(V+E)$ 算法，基于 disc（发现时间）与 low（回边可达的最小 disc）。

def find_bridges(graph: dict, n: int) -> list:
    """Tarjan 桥算法：low[v] > disc[u] 则 (u,v) 是桥"""
    disc = [-1] * n
    low = [-1] * n
    bridges = []
    timer = [0]

    def _dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph.get(u, []):
            if disc[v] == -1:
                _dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            _dfs(i, -1)
    return bridges

8.7 C++ 实现#

#include <vector>
#include <functional>
using namespace std;

vector<int> dfs_recursive(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    vector<int> order;
    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        order.push_back(u);
        for (int v : graph[u]) {
            if (!visited[v]) dfs(v);
        }
    };
    dfs(start);
    return order;
}

8.8 复杂度分析#

• 时间：$O(V + E)$，每条边访问一次；
• 空间：$O(V)$ 递归栈最坏 $O(V)$（链状图）；
• 完备性：有限图完备，无限分支不完备；
• 最优性：否（可能找到非最短路径）。

8.9 工程应用#

1. 拓扑排序：编译器依赖分析（Make、Bazel）、任务调度（Airflow DAG）；
2. 环检测：死锁检测、依赖循环检测；
3. 连通分量：社交网络社区发现、好友推荐；
4. 割点/桥：网络关键节点识别、可靠性分析；
5. 回溯算法：N 皇后、数独、组合搜索的底层框架。

拆分说明：本篇原第 9-13 节（双向 BFS、IDDFS、A*、IDA*、Minimax 与 Alpha-Beta）已拆分为独立篇 055-InformedAndGameSearch（启发式搜索与博弈树），相关工程案例（Google Maps、Stockfish、Sokoban）与陷阱条目一并移入。本篇保留无信息搜索与静态查找主线。

9. 经典应用案例#

9.1 LeetCode 33 旋转排序数组查找#

def search(nums: list, target: int) -> int:
    """旋转排序数组查找：二分变体"""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # 左半有序
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # 右半有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

9.2 LeetCode 200 岛屿数量（DFS/BFS）#

def numIslands(grid: list[list[str]]) -> int:
    """DFS 求岛屿数量"""
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # 标记已访问
        dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

9.3 LeetCode 207 课程表（拓扑排序）#

from collections import deque

def canFinish(numCourses: int, prerequisites: list) -> bool:
    """Kahn 算法判断 DAG"""
    graph = {i: [] for i in range(numCourses)}
    indegree = [0] * numCourses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    taken = 0
    while queue:
        course = queue.popleft()
        taken += 1
        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                queue.append(next_course)
    return taken == numCourses

9.4 LeetCode 1091 二进制矩阵最短路径（BFS）#

from collections import deque

def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    """八连通 BFS 最短路径"""
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1
    queue = deque([(0, 0, 1)])  # (r, c, dist)
    visited = {(0, 0)}
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    while queue:
        r, c, dist = queue.popleft()
        if r == n - 1 and c == n - 1:
            return dist
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not grid[nr][nc] and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return -1

9.5 LeetCode 64 最小路径和（DAG 上的搜索 + DP）#

def minPathSum(grid: list[list[int]]) -> int:
    """DP 求解最小路径和（本质是 DAG 上的 Dijkstra）"""
    m, n = len(grid), len(grid[0])
    dp = [[float('inf')] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(m):
        for j in range(n):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + grid[i][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + grid[i][j])
    return dp[m-1][n-1]

10. 工程实践#

10.1 PostgreSQL B+ 树索引#

PostgreSQL 默认索引结构为 B+ 树（Bayer-McCreight 1972 的推广），查找过程本质是搜索算法：

1. 根节点到叶节点：每层二分查找定位子树，$O(\log_B n)$ I/O；
2. 叶节点链表：支持范围查询与反向扫描；
3. Page Cache：缓冲池避免磁盘 I/O，热数据查找 $O(\log n)$ 内存操作。

10.2 Redis 字典#

Redis 字典采用链地址法哈希表，查找 $O(1)$ 平均：

1. MurmurHash3：高性能非加密哈希；
2. 渐进式 rehash：扩容时新旧两表并存，每次操作迁移一个桶，避免一次性 rehash 阻塞；
3. SipHash（4.0+）：防止哈希碰撞攻击。

10.3 工业级优化技巧#

1. 优先队列优化：A* 用 Fibonacci 堆替代二叉堆，理论 $O(1)$ decrease-key；
2. 状态压缩：用整数编码状态（如 15 数码状态用 64 bit 整数）；
3. 置换表（Transposition Table）：缓存已扩展节点的最优值，避免重复计算；
4. 位并行 BFS：用位运算批量处理多个状态；
5. 分层搜索：将状态按层次划分，分层搜索降低内存；
6. 延迟扩展：仅当节点被弹出时才生成子节点（lazy generation）；
7. A + IDA 混合**：内存充足时用 A*，内存紧张时切换 IDA*；
8. 并行 Alpha-Beta：多线程并行搜索不同子树（Stockfish 11+ 默认 256 线程）。

11. 常见陷阱#

11.1 二分查找整数溢出#

mid = (lo + hi) / 2 在 $lo + hi > 2^{31} - 1$ 时溢出。Bloch 2006 在 Google Research Blog 公开 Java 标准库的此 bug（追溯至 Bentley 1986 Programming Pearls）。正确写法：

mid = lo + (hi - lo) // 2   # Python 无溢出但保留习惯
# C++: mid = lo + ((hi - lo) >> 1);
# Java: mid = (lo + hi) >>> 1;  // 无符号右移

11.2 DFS 递归深度栈溢出#

Python 默认递归深度 1000，处理大图需改用显式栈或 sys.setrecursionlimit。C++ 同样需注意栈大小。

11.3 BFS 队列膨胀#

BFS 在分支因子大的图上内存爆炸。改用 IDDFS 或双向 BFS。

11.4 哈希查找未处理碰撞#

链地址法与开放寻址法各有取舍。Python dict 用开放寻址（伪随机探测），Java HashMap 用链地址法（链表 + 红黑树）。

11.5 拓扑排序对非 DAG 应用#

若图有环，DFS 后序逆序不构成拓扑序。需先做环检测（三色标记）。

11.6 Tarjan 算法 parent 误判#

elif v != parent 防止树边被当作回边。但若图有重边，需用边编号而非节点编号判断。

12. 自测习题#

填空题知识点讲解#

1. Tarjan 桥算法中，边 $(u, v)$ 是桥的充要条件是 ____。

解析讲解：$\text{low}[v] > \text{disc}[u]$

2. Bloch 2006 在 Google Research Blog 公开的二分查找整数溢出 bug 是 ____，正确写法应为 ____。

解析讲解：mid = (low + high) / 2；mid = low + (high - low) / 2 或 mid = (low + high) >>> 1

13. 参考资源#

13.1 经典教材#

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. ISBN 978-0262046305. Chapter 11 (Hash Tables), Chapter 22 (Elementary Graph Algorithms - BFS/DFS), Chapter 24 (Single-Source Shortest Paths - Dijkstra).
2. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. ISBN 978-0134610993. Chapter 3 (Solving Problems by Searching), Chapter 5 (Adversarial Search).
3. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. ISBN 978-0201896855. Section 6.1-6.4.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. ISBN 978-0321573513. Section 3.1-3.4, 4.1-4.3.
5. Kleinberg, J., & Tardos, É. (2006). Algorithm Design. Pearson. ISBN 978-0321295354. Chapter 3 (Graphs), Chapter 4 (Greedy), Chapter 6 (Dynamic Programming).

13.2 历史性论文#

6. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, 41(314), 256-275. DOI:10.1080/14786445008521796. 首次将 Minimax 应用于国际象棋。
7. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. DOI:10.1007/BF01386390. 单源最短路径算法。
8. Moore, E. F. (1959). The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching, 285-292. BFS 独立提出。
9. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. DOI:10.1109/TSSC.1968.300136. A* 算法原论文。
10. Hart, P. E., Nilsson, N. J., & Raphael, B. (1972). Correction to A Formal Basis for the Heuristic Determination of Minimum Cost Paths. SIGART Newsletter, 37, 28-29. A* 算法更正。
11. Pohl, I. (1971). Bi-directional Search. Machine Intelligence, 6, 127-140. 双向搜索。
12. Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293-326. DOI:10.1016/0004-3702(75)90019-3. Alpha-Beta 严格分析。
13. Tarjan, R. E. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2), 146-160. DOI:10.1137/0201010. DFS 系统化。
14. Tarjan, R. E. (1974). A note on finding the bridges of a graph. Information Processing Letters, 2(6), 160-161. 桥算法。
15. Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109. DOI:10.1016/0004-3702(85)90084-0. IDA* 原论文。

13.3 工业实现与进阶#

16. Geisberger, V., Sanders, P., Schultes, D., & Delling, D. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. WEA 2008. Google Maps 路径规划基础。
17. Coulom, R. (2006). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. CG 2006. MCTS 奠基。
18. Bentley, J. (2000). Programming Pearls (2nd ed.). Addison-Wesley. Column 4 (Writing Correct Programs). 90% 程序员无法正确实现二分查找。
19. Bloch, J. (2006). Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog. Java 标准库二分查找整数溢出 bug。
20. Korf, R. E. (1997). Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. AAAI 1997. 模式数据库技术。
21. Stockfish Engine. https://stockfishchess.org/. 开源国际象棋引擎标杆。
22. PostgreSQL Documentation. https://www.postgresql.org/docs/current/indexes-types.html. B+ 树索引实现。
23. Redis Documentation. https://redis.io/docs/reference/. 字典与渐进式 rehash。
24. CPython dictobject.c. https://github.com/python/cpython/blob/main/Objects/dictobject.c. Python 字典实现。
25. Java HashMap. https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java. Java 哈希表实现。

14. 延伸学习#

14.1 理论深入#

• Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. 启发式搜索的奠基性专著。
• Russell, S. (1992). Efficient Memory-Bounded Search Methods. ECAI 1992. SMA*（简化内存受限 A*）。
• Edelkamp, S., & Schrödl, S. (2012). Heuristic Search: Theory and Applications. Morgan Kaufmann. 启发式搜索全景。

14.2 应用拓展#

• 路径规划：Contraction Hierarchies、Hub Labels、Transit Node Routing；
• 博弈 AI：AlphaGo、AlphaZero、MuZero（深度强化学习 + MCTS）；
• 机器人路径规划：RRT、RRT*、PRM（采样式规划）；
• 数据库索引：B+ 树、LSM 树、跳表索引；
• 生物信息学：BLAST 序列搜索、A* 在基因组比对中的应用。

14.3 教学视频#

• MIT 6.006 Introduction to Algorithms：BFS、DFS、Dijkstra 章节；
• Berkeley CS188 Artificial Intelligence：搜索算法章节（Russell 主讲）；
• Stanford CS221 AI Principles：A*、博弈搜索；
• Reducible YouTube Channel：BFS/DFS 可视化讲解。

14.4 在线交互工具#

• VisuAlgo：BFS/DFS/Dijkstra/A* 实时可视化；
• Pathfinding.js（GitHub）：多种路径算法对比；
• Chess Programming Wiki：国际象棋引擎开发资源；
• LeetCode Play：在线运行搜索算法代码。

14.5 进阶主题#

• Monte Carlo Tree Search (MCTS)：Coulom 2006，AlphaGo 的核心；
• Pattern Database (PDB)：Korf 1997，状态空间压缩技术；
• Bidirectional A*：Pohl 1971 的双向启发式搜索；
• Focal Search / WA*：加权 A*，牺牲最优性换取速度；
• Real-Time Search：LRTA*，实时游戏 AI；
• Anytime A*：随时可中断返回当前最优解。

15. 总结#

15.1 知识图谱#

flowchart TD
    S["搜索算法"]
    S --> ST["静态查找 数组/链表<br/>线性 O(n)/二分 O(log n)/哈希 O(1)"]
    S --> U["无信息搜索 状态空间图<br/>BFS O(V+E)/DFS O(V+E)/双向BFS O(b^(d/2))/IDDFS O(b^d) O(d)"]
    S --> I["有信息搜索 状态空间图+启发式<br/>A* O(b^d)/IDA* O(b^d)/贪婪 GBFS/WIDA*"]
    S --> G["对抗搜索 博弈树<br/>Minimax O(b^d)/MCTS/Alpha-Beta O(b^(d/2))"]

15.2 三大核心论证方法#

1. 图搜索论证：以状态空间图模型为基础，证明算法遍历性质（如 BFS 完备性、DFS 连通性）；
2. 势能分析：用于分析带优先队列的算法（如 Dijkstra 的 dist 单调递减、A* 的 f 单调递增）；
3. 对偶论证：反证法证明最优性（如 A* 最优性、IDA* 最优性）。

15.3 工业级选型决策树#

下图中「有信息搜索」与「博弈搜索」两分支的展开讲解见 055-InformedAndGameSearch。