📑 本页目录（点开跳转）
附录A · 速查
📖 做题、复习、写代码时翻的那一页。不重讲原理，只给能照做的清单。
📊 一、搜索算法复杂度对照表（最经典的一张）
记号：$b$ = 分支因子，$d$ = 最浅解的深度，$m$ = 树的最大深度，$C^*$ = 最优解代价，$\varepsilon$ = 最小步代价。
| 算法 | 完备 | 最优 | 时间 | 空间 | 一句话 |
|---|---|---|---|---|---|
| BFS | ✅ | ⚠️ 仅当步代价相同 | $O(b^d)$ | $O(b^d)$ | 💀 空间是它的死穴 |
| UCS（一致代价） | ✅ | ✅ | $O(b^{1+\lfloor C^*/\varepsilon\rfloor})$ | 同左 | BFS 的带权版，取 $g$ 最小 |
| DFS | ❌ 无限深度会死循环 | ❌ | $O(b^m)$ | ⭐ $O(bm)$ | 空间极省，但可能走错路一去不回 |
| 深度受限 DLS | ⚠️ 仅当 $d \le L$ | ❌ | $O(b^L)$ | $O(bL)$ | 给 DFS 加个天花板 |
| ⭐ 迭代加深 IDS | ✅ | ⚠️ 同 BFS | $O(b^d)$ | ⭐ $O(bd)$ | ⭐ BFS 的完备性 + DFS 的空间，首选 |
| 双向搜索 | ✅ | ⚠️ 同 BFS | $O(b^{d/2})$ | $O(b^{d/2})$ | 要能反向生成后继 |
| 贪婪最佳优先 | ❌ | ❌ | $O(b^m)$ | $O(b^m)$ | 只看 $h$，容易被骗 |
| ⭐ A* | ✅ | ✅ $h$ 可容许（树）/ 一致（图） | 指数级 | 💀 把所有节点存内存 | $f = g + h$ |
⭐ IDS 为什么不亏：重复展开的代价只是常数倍，因为节点数随深度指数增长，最后一层占绝大多数。 $b=10,\ d=5$：BFS 展开 111,111，IDS 展开 123,456，只多 11.1%。 ⚠️ 但 $b=2$ 时会多 90% —— 分支因子小的时候，IDS 的优势会缩水。
🃏 二、手算套路卡
通用搜索框架（05 章）
流程图
frontier ← {初始节点}；explored ← ∅
循环：
① 若 frontier 空→失败
② 按【策略】从 frontier 取出一个节点 n ← ⭐ 全部差异只在这一行
③ 若 n 是目标→返回路径 ⚠️ 目标测试在【取出时】不是【生成时】
④ 若 n 已在 explored→跳过
⑤ n 加入 explored，展开它的后继放进 frontier
| 策略 | 取哪个 |
|---|---|
| BFS | 最早进来的（队列） |
| DFS | 最晚进来的（栈） |
| UCS | $g$ 最小的 |
| 贪婪 | $h$ 最小的 |
| A* | $g + h$ 最小的 |
A*（07 章）
- 每个节点算 $f(n) = g(n) + h(n)$
- 每次展开 $f$ 最小的
- 目标取出时才算找到（不是生成时）
- ⚠️ 图搜索要求 $h$ 一致；树搜索只要求可容许
启发式设计（08 章）
| 手法 | 做法 |
|---|---|
| 松弛问题 | 去掉约束，用放松后问题的精确解当 $h$ —— 保证可容许 |
| 子问题 / 模式数据库 | 只解一部分，把代价查表 |
| 取 max | 多个可容许的 $h$ 取最大，仍可容许，且支配每一个 |
Minimax（10 章）
- 从叶子往上
- MAX 层取子节点最大值，MIN 层取最小值
- 根的值就是双方最优对弈的结果
α-β 剪枝（11 章）
信息关系
α = MAX 目前能保证的最好值（下界），初始 −∞
β = MIN 目前能保证的最好值（上界），初始 +∞
在任一节点：若 α ≥ β→剪掉剩下的兄弟分支
⭐ 结果和不剪完全一样（根值不变）。最优节点序下 $O(b^m) \to O(b^{m/2})$，同样时间能搜两倍深。
回溯搜索（14 章）
- 选一个未赋值变量
- 逐个试它的值，检查与已赋值变量是否冲突
- 不冲突就递归；全试完都不行 → 回溯
前向检查 vs AC-3（14 章）
| 做什么 | 强度 | |
|---|---|---|
| 前向检查 | 赋值后，删掉邻居值域里冲突的值；某个值域空了就回溯 | 只看一步 |
| ⭐ AC-3 | 队列装所有弧 $(X,Y)$；删 $X$ 中「在 $Y$ 里找不到支持」的值；$X$ 一旦被删就把指向 $X$ 的弧重新入队 | ⭐ 把后果一路传播下去 |
复杂度：AC-3 是 $O(cd^3)$（$c$ 条弧、$d$ 值域大小）。
CSP 启发式（15 章）
| 选什么 | 用什么 | 方向 |
|---|---|---|
| 变量 | ⭐ MRV（剩余值最少）；并列用度启发（未赋值邻居最多） | fail-first |
| 值 | ⭐ LCV（排除邻居选项最少的） | least-constraining |
⚠️⚠️ 两个方向相反：变量挑最容易失败的（早剪枝，优化最坏情况），值挑最容易成功的（早撞上解，优化最好情况）。
最小冲突（15 章）
- 全部变量随机赋值（完整但违反约束）
- 随机挑一个处于冲突中的变量
- 改成让冲突数最少的值
- 重复。⚠️ 不完备：可能卡在局部极小，无法证明无解
贝叶斯网络枚举推理（17 章）
$$P(X \mid e) = \alpha \sum_{y} \prod_i P(x_i \mid \text{Parents}(x_i))$$ 1. 把查询变量、证据变量固定 2. 对所有未观测变量求和 3. 每一项按链式法则乘 CPT 4. 最后归一化（$\alpha$）
📖 三、定义速查
| 术语 | 一行定义 |
|---|---|
| 状态空间 | 所有可达状态的集合。⚠️ ≠ 搜索树 —— 同一状态可对应树上很多节点 |
| 完备性 | 有解就一定能找到 |
| 最优性 | 找到的一定是最优解 |
| ⭐ 可容许（admissible） | $h(n) \le h^*(n)$，从不高估真实剩余代价 |
| ⭐ 一致（consistent） | $h(n) \le c(n,n') + h(n')$，三角不等式。⭐ 一致 ⟹ 可容许，反之不成立 |
| 支配（dominance） | $h_2 \ge h_1$ 且都可容许 ⟹ $h_2$ 展开的节点更少 |
| 有效分支因子 $b^*$ | 展开 $N$ 个节点、解深 $d$ 时，满足 $N \approx (b^*)^d$ 的那个数，越接近 1 越好 |
| PEAS | Performance / Environment / Actuators / Sensors —— 描述任务环境的四件套 |
| 地平线效应 | 搜索深度到底了，坏事被推到视野之外，看起来一切正常 |
| 静默搜索 | 局面不"平静"（还有吃子/将军）时继续往下搜，防地平线效应 |
| CSP | 变量 + 值域 + 约束；找的是一组赋值不是一条路径 |
| 弧相容 | 对弧 $(X,Y)$，$X$ 的每个值在 $Y$ 里都能找到至少一个支持 |
| 条件独立 | $P(X \mid Y,Z) = P(X \mid Z)$ —— ⭐ 它把 $2^n$ 的联合分布压回线性 |
| d-分离 | 读贝叶斯网独立性的图规则（链式/分叉/汇聚三种结构） |
| ⭐ explaining away | 汇聚结构里，观测到一个原因会降低另一个原因的后验概率 |
⚠️ 四、常见陷阱清单
| 陷阱 | 正确的做法 |
|---|---|
| 💀 目标测试放在生成时 | ⭐ 放在取出时。否则 UCS/A* 会返回次优解 |
| 「可容许就够了」 | ⚠️ 图搜索需要一致性。可容许但不一致时，图搜索可能返回次优解 |
| 「$h$ 越大越好」 | ⭐ 只有在仍然可容许的前提下才越大越好。高估了就不保证最优 |
| A* 一定比 UCS 快 | ⚠️ $h \equiv 0$ 时 A* 就是 UCS。启发式没信息量就没加速 |
| IDS 重复展开很浪费 | ⭐ 只多 11%（$b=10$）。⚠️ 但 $b=2$ 时多 90% |
| α-β「剪掉了就可能剪错」 | ⭐ 根值和不剪完全一样。⚠️ 但被剪节点的值会退化成界，不能当真实值用 |
| α-β 的效果和节点序无关 | 💀 关系极大：最优序才有 $O(b^{m/2})$；最差序退回 $O(b^m)$ |
| 评估函数用单调变换「不影响」 | 💀 会影响！期望极小极大里，对效用取 $\sqrt{\cdot}$ 能翻转最优走法 |
| CSP 里变量序和值序用同一个方向 | ⚠️⚠️ 正好相反：变量 fail-first，值 least-constraining |
| 前向检查 ≈ AC-3 | ⚠️ 前向检查只看一步；AC-3 把删值后果一路传播 |
| 最小冲突「总能解出来」 | ⚠️ 不完备。它在解稠密的问题上惊人地好（n 皇后），解稀疏时会卡死 |
| 「阳性就说明大概率有病」 | 💀 基础率谬误。先验很低时，阳性后验仍可能很低 |
| 贝叶斯网「箭头 = 因果」 | ⚠️ 箭头编码的是条件独立结构，因果解读需要额外假设 |
| 观测到一个原因后另一个原因概率不变 | ⚠️ explaining away：汇聚结构里会显著下降 |
🗂 五、哪个概念在哪一章
| 找什么 | 去哪 |
|---|---|
| 图灵测试、符号主义 vs 联结主义 | 02 |
| PEAS、环境的六个维度 | 03 |
| 反应式 / 模型式 / 规划式 Agent、和 LLM Agent 的分界 | 04 |
| 状态空间、通用搜索框架、完备性/最优性 | 05 |
| BFS / DFS / UCS / IDS / 双向、复杂度表 | 06 |
| ⭐ A*、可容许、一致、最优性论证 | 07 |
| 松弛问题、模式数据库、支配性、8-数码 | 08 |
| 占据栅格、势场法、局部极小、Voronoi | 09 |
| 博弈树、Minimax、Negamax | 10 |
| ⭐ α-β 剪枝、节点序 | 11 |
| 评估函数、地平线效应、期望极小极大、棋类简史 | 12 |
| CSP 建模、n 皇后、密码算术 | 13 |
| 回溯、前向检查、AC-3 | 14 |
| ⭐ MRV / 度启发 / LCV、最小冲突、树结构 CSP | 15 |
| 概率基础、贝叶斯定理、基础率谬误、条件独立 | 16 |
| ⭐ 贝叶斯网络、CPT、explaining away | 17 |
| 边缘检测、区域分割、立体视觉 | 18 |
| 形式文法、句法分析树、正则表达式 | 19 |
| 七个动手项目 | 20 |
🔗 六、跨教程速查
| 想找 | 去哪 |
|---|---|
| 决策树、神经网络、反向传播 | ML基础 —— ⭐ 本板块不重写这部分 |
| MDP、Q-learning、策略梯度 | 强化学习基础 —— ⭐ 搜索假设模型已知，RL 假设未知 |
| 极大极小定理（存在性）、纳什均衡、逆向归纳 | 博弈论与集体决策 —— ⭐ 那边是定理，本板块 10–12 章是算法 |
| 最大似然、MAP、KL 散度 | 机器学习的数学原理 |
| CNN、卷积核 | ML基础 12 —— ⭐ 和本板块 18 章的手工边缘算子对照着看 |
| Tokenizer、Transformer | 大模型全景导论 —— ⭐ 和本板块 19 章的文法/句法树对照着看 |
| LLM Agent、工具调用 | 智能体工程教程 —— ⚠️ 和本板块 04 章的 Agent 不是一回事 |