搜索
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| search tree | 搜索树 | sōu suǒ shù |
| heuristic/hjuːˈrɪstɪk/ | 启发函数 | qǐ fā hán shù |
树与估计
- 搜索树 search tree：节点是状态、边是动作。无信息 uninformed 搜索盲展——广度优先 breadth-first（步长一致时最短）、深度优先 depth-first（省内存）。有信息 informed 搜索用启发函数 heuristic $h(n)$：A* 搜索 A* search 选 $f = g + h$ 最小的节点。
{exercise:uni-cs1301-astar}
练习
A* 选——最小的节点。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
已付代价加可采纳的剩余估计。
课程路线精确版
- 课程图：D→A (4)、D→B (2)、A→C (3)、B→C (1)、C→G (5)、B→G (9)；$h = \{A{:}8, B{:}6, C{:}5, G{:}0\}$。A* 弹出 D(0)、B(8)、C(8)、G(8)：最优代价 8、路径 D→B→C→G、四次扩展——BFS 要访遍全图。
- 可采纳性即契约：$h(n) \le h^*(n)$ 保证首次弹出目标即最优，因为该时刻的 $f$ 是任何开放节点都打不过的下界。
{exercise:uni-cs1301-trace}
练习
课程图上 A* 在目标前扩展——个节点。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
弹 D、B、C，再以代价 8 弹 G——四次。
启发函数说谎时
- 把 $h(C)$ 高估为 12：C 的 $f = 3 + 12 = 15$，而经 B 的目标 $f = 11$——A* 以代价 11 弹出目标即停：非最优（$11 > 8$）。
- 完备（找得到解）不等于最优（找到最好）；BFS 的前沿要 $O(b^d)$ 内存。
{exercise:uni-cs1301-lies}
练习
把 h(C) 高估为 12 让 A* 返回代价——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
C 的 f=15 对目标的 11：提前弹目标——信了谎。