📑 本页目录（点开跳转）
20 · 实战与挑战项目
⏱ 按项目算，从 2 小时到 3 天 ｜ 🔨 菜单式：挑一个做透，比七个都翻一遍强
🎯 一句话
这个板块的算法全部能用纯 Python 几十行写出来 —— 不需要 GPU、不需要数据集、不需要装任何库，而且每一个都有「标准答案」可以对账。
⭐ 这是它相对站里其他板块的最大优势。训练模型你没法确认「跑对了没有」， 但 A* 找到的最短路是不是真的最短、α-β 剪枝后的根值有没有变、CSP 的解满不满足所有约束 —— 全都能当场验证。
⭐⭐ 所以每个项目都给了「验收标准」。 做完对不上，就是写错了，回去查。 这种即时反馈在别的板块很难有。
🗺️ 怎么挑
| 你的情况 | 从这个开始 |
|---|---|
| 想尽快看到东西动起来 | ① 走迷宫可视化（2–4 小时） |
| 想做个能玩的 | ③ 四子棋 AI（1 天） |
| 手上有真实的排班/排课问题 | ④ 数独求解器（1 天）→ 挑战 A |
| 想把第 1 章那个洞穴写成代码 | ⑤ Wumpus Agent（1–2 天） |
| 想挑战自己 | 挑战 A / B（2–3 天） |
⚠️ 别按顺序全做。 挑一个做到「能给别人演示」的程度，比七个半成品有价值得多。
① 走迷宫可视化 ⏱ 2–4 小时
🔗 依赖：05 状态空间与搜索框架、06 无信息搜索、07 启发式与 A*
目标：在同一张网格地图上跑 BFS / DFS / UCS / A，把每种算法展开过的格子标出来*。
步骤
1. 用一个字符串画地图（# 是墙，. 是空地，S 起点，G 终点）
2. 复用第 5 章那个通用搜索框架 —— ⭐ 换一个 pick 就是换一种算法
3. 每跑完一种，把 explored 里的格子打成 *，和地图叠着打印出来
验收标准 - ✅ BFS 和 UCS（代价全为 1 时）找到的路长度相同 - ✅ DFS 找到的路通常更长 - ⭐⭐ A* 展开的格子明显少于 BFS，而且两者路径长度一样 —— 这是本项目最该看到的一幕：启发式省的是搜索量，不是解的质量 - ✅ 把启发式换成 $h \equiv 0$，A* 的展开数应该退化成和 UCS 一样
💡 加分：在地图上放几堵「绕远的墙」，看贪婪最佳优先怎么被骗进死胡同 —— 对照第 7 章。
② 8-数码与启发式对比 ⏱ 3–6 小时
🔗 依赖：07、08 启发式怎么设计
目标：实现 $h_1$（错位数）和 $h_2$（曼哈顿距离），比较展开节点数。
步骤
1. 状态用长度 9 的元组表示，0 代表空格
2. 生成合法移动（空格上下左右换）
3. 用 A* 分别配 $h_1$、$h_2$、以及 $h \equiv 0$（退化成 UCS）跑同一批随机初始局面
验收标准 - ✅ 三者找到的解长度完全相同（都最优） - ⭐⭐ 展开节点数 $h\equiv0 \gg h_1 > h_2$ —— 这就是第 8 章说的支配性 - ✅ 随机生成的初始局面有一半是无解的（逆序数奇偶性），要能正确报「无解」
⚠️ 常见错误：忘了判断可解性，程序在无解局面上把整个状态空间搜完（181440 个状态）才停。
③ 四子棋 AI ⏱ 1 天
🔗 依赖：10 博弈树与 Minimax、11 α-β 剪枝、12 评估函数与棋类 AI
目标：写一个能和你对下的四子棋（Connect Four），先用 Minimax，再加 α-β。
步骤 1. 7×6 棋盘，落子只能从底部堆叠 2. 胜负判定：横/竖/两条斜线上四连 3. 限定搜索深度（比如 6 层），到底了调用评估函数 4. 评估函数：数每种「三连且第四格为空」的数量，己方加分、对方减分
验收标准 - ⭐⭐ 加 α-β 前后，选出的落子完全一样（根值不变）—— 这是剪枝正确性的判据。 ⚠️ 如果结果变了，一定是剪枝写错了 - ⭐ 打印两者访问的叶子数：α-β 应该少一大截。第 11 章那棵教学树是 9 个叶子看 7 个； 你这里深度一深，差距会拉到几倍甚至几十倍 - ✅ 加上移动排序（先试中间列）后，α-β 的叶子数还能再降 —— 对照第 11 章「节点序影响巨大」 - ✅ 它能挡住你的三连
💡 加分：把搜索深度做成参数，画一条「深度 vs 思考时间」的曲线，看看指数增长有多陡。
④ 数独求解器：一层层加技巧 ⏱ 1 天
🔗 依赖：13 CSP 是什么、14 回溯与约束传播、15 CSP 的启发式
目标：⭐ 同一个数独，四个版本，每次只加一层技巧，打印回溯次数。
| 版本 | 加了什么 |
|---|---|
| V1 | 纯回溯（按格子顺序填） |
| V2 | + 前向检查 |
| V3 | + AC-3 |
| V4 | + MRV（先填候选最少的格） |
验收标准 - ✅ 四个版本解完全相同（数独解唯一） - ⭐⭐ 回溯次数逐版本大幅下降。简单题上 V4 常常是零回溯 —— 这正是第 15 章说的「从第 ③ 步起每步只有一个合法值，根本没得选也就无从选错」 - ✅ 拿一道「困难」难度的题，V1 可能要跑很久，V4 秒解
⭐ 这个项目是全板块性价比最高的一个：数独人人都懂，而四个版本的差距用肉眼就能看见。
⑤ Wumpus World Agent ⏱ 1–2 天
🔗 依赖：01 第一天、03 任务环境、13、16 不确定性下的推理
目标：把第 1 章你用脑子做的推理，写成代码。
步骤 1. 生成随机洞穴（4×4，随机放坑/Wumpus/金子） 2. Agent 只能看到当前格的感知（微风/臭味/闪光） 3. 维护一个知识库：每格三种状态（确定安全 / 确定危险 / 未知） 4. 每次只走到「确定安全且没去过」的格子；用 A* 规划怎么走过去
验收标准 - ⭐⭐ 在第 1 章那个局面上，它必须推出「坑在 (3,1)、Wumpus 在 (1,3)、(2,2) 安全」 —— 和你手推的结果一模一样 - ✅ 跑 100 个随机洞穴，统计存活率 - ⚠️ 一定会遇到「没有确定安全的格子可走」的局面 —— ⭐ 这就是第 1 章那堵墙三。此时要么冒险，要么退出。记录这种局面出现的频率
💡 加分：给每个未知格算一个「有坑的概率」，只赌概率最低的那格 —— 用上第 16 章。
🏆 挑战 A：把排课表变成 CSP ⏱ 2–3 天
🔗 依赖：13–15 章全部
目标：解一个真实规模的排课/排班问题。
建模（这一步比写算法难，也更值钱） - 变量：每门课的（时间段, 教室） - 值域：所有可用的时间段 × 教室 - 约束：同一教师不能同时上两门课、同一教室不能同时排两门、教室容量够、 某些课必须在上午、某些课不能相邻……
验收标准 - ✅ 解满足全部约束（写一个独立的检查函数，别用求解器自己验） - ⭐ 规模拉到 50 门课以上时，MRV + AC-3 和纯回溯的差距应该是数量级的 - ⭐⭐ 加一条互相矛盾的约束，程序应该能报「无解」而不是死循环 —— ⚠️ 这一点很多人第一次会写错
💡 加分：加软约束（老师偏好上午），变成优化问题：先求可行解，再局部搜索改进。 ⭐ 这就是第 15 章的最小冲突的用武之地 —— 从旧解开始修，比从头搜快得多。
🏆 挑战 B：贝叶斯网络推理器 ⏱ 2–3 天
目标：写一个能对任意小型贝叶斯网做精确推理的程序。
步骤 1. 网络用「节点 → (父节点列表, CPT)」的字典表示 2. 实现枚举推理：给定证据，对所有未观测变量求和 3. 实现变量消元：按某个顺序消掉变量，对比它比枚举快多少
验收标准 - ⭐⭐ 用第 17 章的警报网络验证：$P(b \mid j, m)$ 必须算出 0.284 （精确值 0.2841718353643929）—— 对不上就是写错了 - ✅ 联合概率 $P(j, m, a, \neg b, \neg e)$ 应该是 0.000628 - ⭐ 验证 explaining away：观测到地震后，入室行窃的后验概率应该大幅下降 - ✅ 变量消元在节点数增加时明显快于枚举
💡 加分：实现似然加权采样，和精确解对比，看采样多少次才能收敛到小数点后三位。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 附录A · 速查 | ⭐ 动手时最该开着的那一页：每个算法的步骤清单、复杂度对照表、常见陷阱 |
| 05 · 状态空间与搜索框架 | 项目 ①②⑤ 全都建在那个通用框架上 —— 写一次，换 pick 就够 |
| 11 · α-β 剪枝 | 项目 ③ 的验收标准（结果不变、叶子数下降）就是那一章的正确性判据 |
| ../机器学习与深度学习基础/17-实战项目.html | ⭐ 对照着做很有意思：那边的项目要下数据、调参、等训练；这边的项目秒跑、可验证、无随机性。两种工程体验完全不同 |
✅ 检查点
⭐ 这一章的检查点不考知识，考你能不能判断自己写对了 —— 这才是动手时真正需要的能力。
- 为什么说这个板块的项目「能当场验证」？和训练模型的工程体验有什么不同？
- 项目 ① 里，A* 和 BFS 的路径长度应该一样还是不一样？展开的格子数呢？为什么？
- 项目 ① 里把启发式换成 $h \equiv 0$，A* 会变成什么？
- 项目 ② 里三种启发式的展开节点数应该是什么关系？这个关系叫什么？
- 项目 ③ 加 α-β 之后，如果 AI 选的落子变了，说明什么？
- 项目 ④ 的四个版本，解应该相同还是不同？该拿什么指标看出差距？
- 项目 ⑤ 一定会遇到什么局面？它对应第 1 章的哪堵墙？
- 挑战 A 里，为什么验收要「独立写一个检查函数」而不是信求解器？
- 挑战 B 用什么数字验收？对不上说明什么？
👀 答案
- 因为每个算法都有标准答案可以对账：最短路是不是真最短、剪枝后根值有没有变、CSP 的解满不满足约束 —— 全能当场验证。⭐ 而训练模型你没法确认「跑对了没有」，只能看指标好不好看。这种即时反馈在别的板块很难有。
- ⭐⭐ 路径长度一样，展开格子数 A* 明显更少。 因为 $h_{SLD}$ 可容许，A* 保证最优（所以解一样好），而启发式的作用是少展开无关节点 —— 启发式省的是搜索量，不是解的质量。
- ⭐ 退化成 UCS。$f = g + 0 = g$，就是按已花代价取最小 —— 这也是验证你 A* 写对了的好办法。
- 展开数 $h\equiv0 \gg h_1 > h_2$，而解长度三者完全相同。这个关系叫 ⭐ 支配性（dominance）：$h_2 \ge h_1$ 且都可容许 ⟹ $h_2$ 展开的节点更少（第 8 章）。
- 💀 说明剪枝写错了。 ⭐ α-β 的正确性判据就是根值和不剪完全一样 —— 它只跳过「不可能影响根值」的分支。结果变了就一定是 α/β 的更新或剪枝条件写错了。（⚠️ 注意：被剪节点的值会退化成界，不能当真实值用，但根值不受影响。）
- ✅ 解完全相同（数独解唯一）。⭐ 差距要看回溯次数（不是看解）—— V1 纯回溯 → V2 前向检查 → V3 AC-3 → V4 MRV，回溯次数应该逐版本大幅下降，简单题上 V4 常常零回溯。
- ⚠️ 一定会遇到「没有任何确定安全的格子可走」的局面。⭐ 这对应第 1 章的墙三：逻辑推不出唯一答案，但你还是得走一步 —— 逻辑只有真和假，没有「多半」。此时要么冒险要么退出，加分做法是给每格算概率、只赌最低的（第 16 章）。
- 因为求解器自己验等于自己判自己的卷。⭐ 如果你的约束建模写漏了一条，求解器会「合法地」给出一个违反那条约束的解，而它自己检查时用的是同一份（漏掉那条的）约束，永远发现不了。独立的检查函数是另一双眼睛。
- ⭐⭐ 第 17 章警报网络的 $P(b \mid j,m) = \mathbf{0.284}$（精确值 0.2841718353643929），联合概率 $P(j,m,a,\neg b,\neg e) = \mathbf{0.000628}$。对不上就是写错了 —— 最常见的错是求和时漏了某个未观测变量的取值，或者忘了最后归一化。
🛑 可以停在这里
⚡ 走神救援
⭐⭐ 这个板块的算法全部能用纯 Python 几十行写出来 —— 不需要 GPU、数据集、任何库，而且每个都有标准答案可对账。 这是它相对全站其他板块的最大优势：训练模型你没法确认「跑对了没」，但最短路是不是真最短、剪枝后根值有没有变、CSP 的解满不满足约束，全都能当场验证 —— 所以每个项目都给了验收标准，对不上就是写错了。七个项目：① 走迷宫可视化（2–4 小时），同一张地图跑 BFS/DFS/UCS/A* 并把展开过的格子标出来 —— ⭐⭐ 该看到的一幕是 A* 展开的格子明显更少、但路径长度和 BFS 一样（启发式省的是搜索量不是解的质量），另外把 $h$ 换成恒 0 应该退化成 UCS。② 8-数码（3–6 小时），$h_1$ 错位数 vs $h_2$ 曼哈顿距离，⭐ 验收是解长度完全相同但展开数 $h\equiv0 \gg h_1 > h_2$（第 8 章的支配性）；⚠️ 别忘了一半随机局面是无解的。③ 四子棋 AI（1 天），Minimax 加 α-β，⭐⭐ 验收核心是加剪枝前后选出的落子完全一样（结果变了就是写错了），同时打印叶子数看差距，再加移动排序还能再降。④ 数独求解器（1 天，性价比最高），同一道题四个版本 V1 纯回溯 → V2 前向检查 → V3 AC-3 → V4 MRV，每次只加一层、打印回溯次数，⭐⭐ 简单题上 V4 常常零回溯，差距肉眼可见。⑤ Wumpus Agent（1–2 天），把第 1 章脑子里那套推理写成代码，⭐⭐ 验收是必须推出「坑在 (3,1)、Wumpus 在 (1,3)、(2,2) 安全」；⚠️ 一定会遇到「没有确定安全的格子可走」——那就是第 1 章的墙三，加分项是给每格算概率、只赌最低的那个。🏆 挑战 A：排课 CSP（2–3 天），⭐ 建模比写算法难也更值钱，验收要独立写检查函数（别用求解器自己验），规模到 50 门课以上时 MRV+AC-3 和纯回溯差数量级；⚠️ 加一条矛盾约束要能报无解而不是死循环。🏆 挑战 B：贝叶斯推理器（2–3 天），⭐⭐ 用第 17 章警报网络验收：$P(b\mid j,m)$ 必须是 0.284、联合概率 0.000628，还要能复现 explaining away。⚠️ 最后一条建议：别按顺序全做 —— 挑一个做到能给别人演示的程度，比七个半成品有价值得多。