📑 本页目录（点开跳转）
附录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 不是一回事 |
打卡记录保存在你的浏览器里，首页能看到总进度