Ch3-4 搜索 (Search: Uninformed & Informed)

课件：lec3.pdf (无信息搜索 / Uninformed Search) + lec4.pdf (有信息搜索 / Informed Search)
教材：Artificial Intelligence: A Modern Approach (Russell & Norvig), Ch 3
教师：吉建民，USTC

0. 本章概述

第二章的"目标驱动智能体 (goal-based agent)"需要"搜索与规划 (search and planning)"来找到达成目标的动作序列。本章正是把这一能力具体化：先给出搜索问题 (search problem) 的形式化，再用一系列策略在状态空间中寻找解。按是否利用额外领域知识，分为无信息搜索 (uninformed search) 与有信息搜索 (informed search / heuristic search)。

第一部分：问题求解智能体与搜索问题 (lec3)

1.1 问题求解智能体 (Problem-solving Agents)

⭐ 问题求解智能体是一类目标驱动智能体 (goal-based agent)：它通过评估未来的动作序列来做决策。

• 搜索算法通常假设：
  • 转移模型已知且确定 (known, deterministic transition model)
  • 离散的状态与动作 (discrete states and actions)
  • 完全可观测 (fully observable)
  • 原子表示 (atomic representation)：状态被视为整体，内部结构对算法不可见
• 通常有明确目标 (definite goal)；最优 (optimal) = 以最小代价达成目标。
• 使用更高级的因子化 (factored) 或结构化 (structured) 表示的同类智能体称为规划智能体 (planning agents)。

离线 vs 在线

• 离线问题求解 (offline problem solving)：先求出完整解再执行（“闭着眼睛执行 solution executed eyes-closed”）。
• 在线问题求解 (online problem solving)：在不具备完全知识时边感知边行动（后续章节）。

引例：Romania（罗马尼亚公路旅行）

• 在 Arad 度假，明天从 Bucharest 起飞 → 目标：到达 Bucharest。
• 目标形式化：“be in Bucharest”。
• 问题形式化：states = 城市；actions = 在城市间驾车。
• 解 (solution)：城市序列，如 Arad, Sibiu, Fagaras, Bucharest。

1.2 搜索问题的形式化 ⭐

⭐ 一个（搜索）问题 (search problem) 由以下要素组成：

• 解 (solution)：从初始状态到目标状态的一个动作序列。
• 最优解 (optimal solution)：所有解中代价最小者。

1.3 状态空间的抽象化 (Abstraction) 与"好"状态空间

抽象化

真实世界极其复杂，必须抽象化 (abstracted) 后才能求解：

• (抽象) 状态 = 一组真实状态的集合。
• (抽象) 动作 = 一组复杂真实动作的组合（如 Go(Zerind) 代表无数种可能路线、绕路、停靠）。
• 为保证可实现性 (realizability)：任何处于抽象状态 $\text{In(Arad)}$ 的真实状态，执行该动作后必须落入某个 $\text{In(Zerind)}$ 的真实状态。
• 每个抽象动作应比原问题"更容易"。

构建"好的"状态空间 ⭐

• 让状态尽可能可达、可行、合法；状态数越少越好（规避大量不可达状态）；方便设计后继函数与搜索算法。

例：n 皇后问题的三种状态空间设计（状态数差异巨大）

→ 同一个问题，状态空间设计的优劣直接决定搜索可行性。

其他典型搜索问题

⚠️ n-puzzle 的最优解是 NP-hard；8-puzzle 的状态数为 $O((n+1)!)$，是 NP 完全问题。

1.4 状态空间图 (State Space Graph) vs 搜索树 (Search Tree) ⭐

状态空间图

• 节点 (nodes) = 抽象的世界配置；弧 (arcs) = 后继关系（动作结果）；目标测试对应一组目标节点。
• ⭐ 在状态空间图中，每个状态只出现一次。
• 通常太大，无法完整在内存中构造，但是有用的概念。

搜索树

• 通过扩展 (expanding) 已探索状态的后续状态，按需动态构造。
• 搜索树的每个节点 (node) 对应状态空间图中一条完整路径（不是单个状态）。
• 尽量只构造必要的部分。

节点 (Node) 的数据结构

节点是搜索树中的数据结构，包含：

• state（状态）
• parent node（父节点）
• action（从父到本节点的动作）
• path cost $g(n)$（路径代价）
• depth（深度）

重复状态问题 ⭐

“Those who don’t know history are doomed to repeat it!”（不吸取历史教训者注定重蹈覆辙）

• 不检测重复状态，可能把一个线性规模的问题变成指数规模。
• 例：含重复状态、深度 $d$ 的搜索树有 $4^d$ 个叶节点；而距起点 $d$ 步以内的不同状态仅有约 $2d^2$ 个。

1.5 树搜索 vs 图搜索 (Tree-Search vs Graph-Search) ⭐

通用树搜索 (General Tree Search)

• 基本思想：离线、模拟地探索状态空间——不断生成已探索状态的后继（即"扩展状态"）。
• 主要变化维度：
  1. 下一步扩展哪个叶节点（决定策略）
  2. 是否检测重复状态
  3. frontier 与已扩展节点的数据结构

图搜索 (Graph Search) 与 Frontier

• Frontier（边界 / fringe）：分隔"已扩展区域"与"未探索区域"。
• 扩展一个 frontier 节点：把它从 frontier 移入已扩展集，并把新发现的未探索节点加入 frontier（维持 frontier 性质）。
• 例：$\{1,2\}$ 已扩展，frontier $=\{3,4,5\}$；扩展 3 后 frontier $=\{4,5,6,7\}$。

对比

1.6 搜索算法性能评估 ⭐

搜索策略 (search strategy) = 选择节点扩展的顺序。

四个评估维度：

复杂度参数 ⭐

1.7 无信息搜索 (Uninformed Search) 策略 ⭐

⭐ 定义：无信息搜索 (uninformed / blind search) 指除问题定义提供的状态信息外，没有任何附加信息。与之对应的是有信息搜索（启发式搜索），后者知道某非目标状态是否比其他状态更接近目标。

本课介绍 6 种无信息策略：广度优先、一致代价、深度优先、深度受限、迭代加深、双向。

1.7.1 广度优先搜索 (Breadth-First Search, BFS) ⭐

• Frontier 数据结构：FIFO 队列（first-in, first-out）。
• 完备性：完备（若 $d$ 有限）。
• 最优性：当每条边代价一致（cost = 1/step）时返回最优解；否则不一定。
• 时间复杂度：

$$1+b+b^2+\cdots+b^d = O(b^d)$$

若目标测试在节点被扩展时做（而非生成时），则整层 $d$ 都被扩展，时间复杂度为 $O(b^{d+1})$。

• 空间复杂度：$O(b^d)$（或 $O(b^{d+1})$），所有节点都要存——BFS 的最大瓶颈是空间。

1.7.2 一致代价搜索 (Uniform-Cost Search, UCS) ⭐

• 思想：扩展当前路径代价最小的未扩展节点。
• Frontier：按路径代价 $g(n)$ 排序的优先级队列。
• 若所有边代价一致，UCS 退化为 BFS。
• 完备性：完备，前提是单步代价有下界 $\epsilon>0$（即 step cost $\ge\epsilon$）。
• 最优性：最优（节点按 $g(n)$ 递增顺序扩展）。
• 时间/空间复杂度：代价不超过 $C^*$ 的节点数

$$O\!\left(b^{1+\lfloor C^*/\epsilon\rfloor}\right)$$

其中 $C^*$ 为最优解代价。

1.7.3 深度优先搜索 (Depth-First Search, DFS)

• Frontier：LIFO 栈（last-in, first-out）。
• 完备性：不完备——在无限深空间或含环空间会失败；若改为避免路径上的重复状态，则在有限空间完备。
• 最优性：不保证。
• 时间复杂度：

$$1+b+b^2+\cdots+b^m = O(b^m)$$

当 $m\gg d$ 时很糟；但若解密集，可能比 BFS 快得多。

• 空间复杂度：$O(bm)$，即线性空间——只需存一条根到叶的路径及路径上节点的未扩展兄弟。

1.7.4 深度受限搜索 (Depth-Limited Search, DLS)

• 思想：DFS + 深度界限 $l$，深度 $>l$ 的节点不再扩展。目的：避免 DFS “一条路走到黑”。
• 返回结果三种：有解 / 无解 / 在 $l$ 范围内无解。
• 完备性：不完备。
• 最优性：不保证。
• 时间复杂度：$O(b^l)$；空间复杂度：$O(bl)$。
• 若 $l<d$ 可能不完备；若 $l>d$ 不最优。

1.7.5 迭代加深的深度优先搜索 (Iterative Deepening Search, IDS) ⭐⭐⭐

⭐ 由 DLS 演化：以 $k=0,1,2,\dots$ 为深度界限反复执行 DLS，每轮加一。

• 结合了 BFS（完备/最优/浅层优先）与 DFS（线性空间）的优点。
• 完备性：完备。
• 最优性：当每条边代价一致（step cost = 1）时返回最优解；否则不一定。
• 时间复杂度：

$$db+(d-1)b^2+(d-2)b^3+\cdots+b^d = O(b^d)$$

（上层被重复生成，但额外开销不大）

• 空间复杂度：$O(bd)$（深度界限达到 $d$）。

IDS vs BFS 数值对比（$b=10,d=5$，解在最右叶）

• $N(\text{IDS})=50+400+3000+20000+100000=123450$
• $N(\text{BFS})=10+100+1000+10000+100000=111100$

重复生成上层的额外成本很小，但换来了线性空间。

⭐ 结论：当搜索空间大、解深度未知时，IDS 是无信息搜索的首选方法 (preferred uninformed search method)。

1.7.6 双向搜索 (Bidirectional Search)

• 思想：同时从初态和终态进行 BFS，在中间相遇。
• 难点：终态可能不好描述（如 n 皇后）；从终态出发的前驱函数可能不好定义。
• 完备性：完备。
• 最优性：当每条边代价一致时返回最优解；否则不一定。
• 时间/空间复杂度：$O(b^{d/2})$（两个 $d/2$ 深度的搜索）。

1.8 无信息搜索策略速查表 ⭐⭐⭐

$b$=分支因子，$d$=最优解深度，$m$=最大深度，$C^*$=最优解代价，$\epsilon$=单步代价下界。

第二部分：有信息搜索 (Informed Search) (lec4)

2.1 有信息 vs 无信息

2.2 最佳优先搜索 (Best-First Search) ⭐

⭐ 核心思想：为每个节点定义评价函数 (evaluation function) $f(n)$——对"合意性 (desirability)"的估计；每次扩展 $f$ 最优的未扩展节点。

• 启发函数 (heuristic function) $h(n)$：估计状态 $n$ 距目标的接近程度；针对特定搜索问题设计。
• 实现：frontier 为按 $f$ 降序排列的优先级队列 (priority queue)。
• 是通用 TREE-SEARCH / GRAPH-SEARCH 的实例。
• 三个评价函数的特例：

其中：

• $g(n)$ = 从初始节点到 $n$ 的实际路径代价 (path cost so far)（向后代价 backward cost）。
• $h(n)$ = 从 $n$ 到目标的估计代价 (estimated cost to goal)（向前代价 forward cost）。

2.3 贪心最佳优先搜索 (Greedy Best-First Search) ⭐

• 评价函数 $f(n)=h(n)$ = 从 $n$ 到最近目标的代价估计。
  • Romania 例：$h_{\text{SLD}}(n)$ = $n$ 到 Bucharest 的直线距离 (Straight-Line Distance)。
• 策略：扩展看起来离目标最近的节点。
• 性质：

2.4 A* 搜索 ⭐⭐⭐

评价函数

$$\boxed{\,f(n)=g(n)+h(n)\,}$$

• $g(n)$ = 到达 $n$ 的耗散（cost so far）
• $h(n)$ = 从 $n$ 到目标的最低耗散路径的估计（启发函数）
• $f(n)$ = 经过 $n$ 到达目标的总代价估计

可采纳性 (Admissibility) ⭐

⭐ $h(n)$ 是可采纳的 (admissible) 当且仅当对每个节点 $n$：

$$h(n)\le h^*(n)$$

其中 $h^*(n)$ 是从 $n$ 到目标的真实最小代价。并要求 $h(n)\ge 0$，且对任何目标 $G$ 有 $h(G)=0$。

• 直觉：可采纳启发式从不过高估计到达目标的代价，即它是乐观的 (optimistic)。
• 例：$h_{\text{SLD}}$ 从不高估真实公路距离。

一致性 (Consistency) ⭐

⭐ $h(n)$ 是一致的 (consistent / monotone) 当且仅当对每个节点 $n$、每个由动作 $a$ 生成的后继 $n'$：

$$h(n)\le c(n,a,n')+h(n')$$

• ⭐ 一致性蕴含可采纳性 (consistency implies admissibility)。
• 若 $h$ 一致，则沿任何路径 $f$ 值单调不减：

$$f(n')=g(n')+h(n')=g(n)+c(n,a,n')+h(n')\ge g(n)+h(n)=f(n)$$

A* 的最优性定理 ⭐⭐⭐

定理 1（TREE-SEARCH）：若 $h(n)$ 可采纳，则 A* 的 TREE-SEARCH 版本最优。

定理 2（GRAPH-SEARCH）：若 $h(n)$ 一致，则 A* 的 GRAPH-SEARCH 版本最优。

最优性证明（TREE-SEARCH，可采纳情形）⭐

设次优目标 $G_2$ 已在 fringe 中，$n$ 是 fringe 中、位于通向最优目标 $G$ 的最短路径上的未扩展节点。

1. $f(G_2)=g(G_2)$（因为 $h(G_2)=0$）。
2. $g(G_2)>g(G)$（$G_2$ 次优）。
3. $f(G)=g(G)$（因为 $h(G)=0$）。
4. 故 $f(G_2)>f(G)$。
5. 由可采纳性 $h(n)\le h^*(n)$，且 $n$ 在到 $G$ 的最短路上：

$$f(n)=g(n)+h(n)\le g(n)+h^*(n)\le g(G)=f(G)$$

6. 因此 $f(G_2)>f(n)$，A* 永远不会选择 $G_2$ 扩展。$\square$

A* 的三个版本

• Tree-search 版本：不检测重复。
• Graph-search 版本：检测重复。
• Practical 版本：当发现到达旧节点 $n$ 的新路径时，若 $g(n)$ 变得更小，则更新 $n$ 并让它重新成为待扩展节点（即重新打开 closed 节点 / 路径更新）。这是实际工程中最常用的形式。

f-等值线 (f-contours)

A* 按递增的 $f$ 值扩展节点，逐步形成"等值线 (contours)"——contour $i$ 包含所有 $f=f_i$ 的节点，$f_i<f_{i+1}$。

A* 扩展哪些节点 ⭐

设 $C^*$ 为最优解代价：

• A* 扩展所有 $f(n)<C^*$ 的节点；
• A* 扩展部分 $f(n)=C^*$ 的节点；
• A* 不扩展任何 $f(n)>C^*$ 的节点。

A* 性质总结

2.5 启发式设计 (Heuristic Design) ⭐⭐⭐

8-puzzle 的两个经典启发式

设 $h^*(n)$ 为真实最少步数：

• $h_1(n)$ = 错位棋子数 (number of misplaced tiles)。
• $h_2(n)$ = 曼哈顿距离之和 (total Manhattan distance) = 所有棋子到其目标位置的水平竖直距离和。

对同一初始状态 $S$：$h_1(S)=8$，$h_2(S)=3+1+2+2+2+3+3+2=18$。

8-puzzle 平均解步数约 22，分支因子约 3；穷举到深度 22 需 $3^{22}\approx 3.1\times10^{10}$。

支配性 (Dominance) ⭐

⭐ 若对所有 $n$ 都有 $h_2(n)\ge h_1(n)$（且两者都可采纳），则称 $h_2$ 支配 (dominate) $h_1$，$h_2$ 更有利于搜索。

典型搜索开销（平均扩展节点数）对比：

→ 支配性更强的启发式扩展节点数远少于被支配者。

组合多个启发式 ⭐

⭐ 给定任意一组可采纳启发式 $\{h_1,\dots,h_m\}$，

$$h(n)=\max(h_1(n),\dots,h_m(n))$$

仍可采纳，且支配其中每个成员启发式。

松弛问题 (Relaxed Problems) ⭐⭐⭐

⭐ 松弛问题 (relaxed problem)：对动作施加更少限制的问题。

• ⭐ 核心定理：松弛问题最优解的代价，是原问题的一个可采纳启发式（因为去掉限制只会让代价不增）。
• 关键点：松弛问题的最优解代价 $\le$ 原问题的最优解代价。

8-puzzle 的三种松弛（原规则：棋子可从 A 移到 B，当 A、B 水平/垂直相邻且 B 为空）：

设计启发式的一般方法：从原问题去掉某些约束得到松弛问题，求其精确最优解作为 $h$。

Pattern Database（模式数据库）*

课件正文未直接展开，属 AIMA 标准方法（对照原课件/教材查看）：预先存储一组"模式 (patterns)"到目标的最短代价，作为可采纳启发式，常用于 15-puzzle 等大状态空间。

有效分支因子 (Effective Branching Factor)*

AIMA 标准评估指标（对照原课件/教材查看）：若 A* 扩展 $N$ 个节点、解深 $d$，定义 $b^*$ 使 $N+1=1+b^*+\cdots+(b^*)^d$；$b^*$ 越接近 1 说明启发式越好，且对同一问题 $b^*$ 在不同 $d$ 下大致恒定。

2.6 Hybrid A*（应用扩展）*

车辆自主泊车的路径规划算法：以较少换挡次数规划出可行驶轨迹。

• 搜索状态 $(x,y,\theta,r)$，$r$ 表示前进/后退。
• 动作离散化：max-left / no-turn / max-right。
• 启发式：
  • non-holonomic without obstacles：忽略障碍但满足可行驶约束（车头朝向连续变化）；
  • holonomic with obstacles：考虑障碍但忽略可行驶约束。
• 最后再做轨迹平滑与优化。

2.7 内存受限与迭代加深的 A*（AIMA 扩展）*

课件正文未直接出现，属 AIMA 标准考点（建议对照教材 Ch3 补充）：

• IDA* (Iterative Deepening A*)：把迭代加深思想用到 $f$ 值上。每轮设 $f$ 阈值，只扩展 $f\le$ 阈值的节点；下一轮阈值 = 上一轮被剪枝节点的最小 $f$。内存 $O(bd)$，可采纳 $h$ 下完备且最优。
• RBFS (Recursive Best-First Search)：递归式最佳优先，用线性内存模拟最佳优先；每个节点记录"可达的最佳 $f$ 替代值"，递归回溯。
• SMA* (Simplified Memory-bounded A*)：A* 的内存受限版——当内存满时丢弃 $f$ 最差节点，但将其信息回填到父节点，以便日后必要时重新生成。

2.8 局部搜索算法 (Local Search Algorithms) ⭐

适用场景：很多优化问题中，到目标的路径无关紧要，目标状态本身就是解。

• 状态空间 = “完整配置 (complete configurations)” 的集合（如 n 皇后的一种摆法）。
• 不断保持单个"当前状态"并尝试改进；常数空间，适合在线与离线搜索。

2.8.1 爬山搜索 (Hill-Climbing Search)

• 比喻：“像在浓雾中、患健忘症 (amnesia) 攀登珠峰”——只能看到局部、忘记来路。
• 问题：依赖初始状态，可能陷入局部极大值 (local maxima)、山肩 (shoulders)、平坦区。
• 改进：
  • 随机重启爬山 (Random-restart hill climbing)：克服局部极大，平凡地完备。
  • 横向随机移动 (random sideways moves)：逃出山肩。

8-queens 中的爬山

• 评价 $h$ = 互相攻击的皇后对数；某状态 $h=17$；可能陷入 $h=1$ 的局部最小。

2.8.2 模拟退火 (Simulated Annealing Search) ⭐

• 思想：允许少量"坏"移动以逃离局部极大，但逐渐降低其频率（温度 $T$ 缓慢下降）。
• ⭐ 理论保证：若 $T$ 下降足够慢，模拟退火将以趋于 1 的概率找到全局最优。
• 广泛用于 VLSI 布局、航班调度等。

标准 AIMA 中的接受准则（对照教材）：若 $\Delta E>0$ 直接接受；否则以概率 $\exp(\Delta E/T)$ 接受（$\Delta E$ 为新状态的值增量）。

2.8.3 局部剪枝搜索 (Local Beam Search)

1. 同时跟踪 $k$ 个状态（而非一个）。
2. 从 $k$ 个随机生成的状态开始。
3. 每轮生成所有 $k$ 个状态的全部后继。
4. 若任一为目标则停止；否则从完整后继列表中选最好的 $k$ 个，重复。

• ⚠️ 不是 $k$ 个独立搜索并行运行——发现好状态的搜索会"招募"其他搜索加入。
• 缺点：$k$ 个状态常聚集到同一座局部山丘 → 改进：随机选 $k$ 个后继、偏向好状态（随机束搜索 stochastic beam search）。

2.8.4 遗传算法 (Genetic Algorithms, GA) ⭐

• 后继由两个父代状态组合产生。
• 从 $k$ 个随机生成的状态（种群 population）开始。
• 状态表示为有限字母表上的串（常为 0/1 串）。
• 评价函数 = 适应度函数 (fitness function)：状态越好值越大。
• 通过三大操作产生下一代：选择 (selection)、杂交 (crossover)、变异 (mutation)。

8-queens 中的 GA

• 适应度 = 不互相攻击的皇后对数（min = 0，max = $\binom{8}{2}=28$）。
• 选择概率正比于适应度，如 $24/(24+23+20+11)=31\%$。

2.9 搜索方法小结

有信息搜索

• 启发函数估计到目标的最短路径代价；好的启发可极大降低搜索代价。
• 贪心最佳优先：扩展最小 $h$；不完备、不最优。
• A*：扩展最小 $g+h$；完备、最优，且（对前向搜索、除并列外）效率最优 (optimally efficient)。
• 可采纳启发式可由松弛问题的精确解导出。

局部搜索

• 路径无关紧要；保持单个"当前状态"并改进。
  • 爬山：可能陷入局部极大。
  • 模拟退火：允许坏移动并逐渐降温，可收敛到全局最优。
  • 局部剪枝：同时保留 $k$ 个状态。
  • 遗传算法：基于种群的选择/杂交/变异。

无信息 vs 有信息（课程结语）

• 好的启发式搜索能大幅提高搜索性能。
• 但启发式需要抽取问题相关特征信息，而特征抽取有时困难 → 盲目搜索仍是有用的策略。

好的搜索策略应满足

• 引起运动——避免原地踏步；
• 系统——避免兜圈；
• 运用启发函数——缓解组合爆炸。

算法 / 复杂度 / 公式 速查表

关键公式

• 评价函数：$f(n)=g(n)+h(n)$
• 可采纳：$h(n)\le h^*(n)$
• 一致：$h(n)\le c(n,a,n')+h(n')$；一致 ⇒ 可采纳
• 一致下 $f$ 单调不减：$f(n')\ge f(n)$
• A* 扩展范围：$\{n:f(n)<C^*\}$ 必扩展，$\{n:f(n)>C^*\}$ 不扩展
• 组合启发式：$h(n)=\max_i h_i(n)$ 仍可采纳且占优
• IDS 时间：$db+(d-1)b^2+\cdots+b^d=O(b^d)$
• BFS 求和：$1+b+\cdots+b^d=O(b^d)$

本章关键概念清单

• [ ] 写出搜索问题的六要素（初始状态 / 动作 / 转移模型 / 状态空间 / 目标测试 / 路径代价），并举 Romania 例
• [ ] 区分状态 (state) 与节点 (node)，说出节点数据结构的五个字段
• [ ] 解释为什么必须抽象化状态空间，以及"好状态空间"的三条标准
• [ ] 用 n 皇后的三种状态空间设计说明状态数差异
• [ ] 区分状态空间图与搜索树，说明重复状态为何会把线性问题变指数
• [ ] 复述性能评估四维度（完备/时间/空间/最优）与 $b,d,m,C^*,\epsilon$ 的含义
• [ ] 默写六种无信息策略的 frontier 数据结构与复杂度
• [ ] 说明 IDS 为何是无信息搜索的首选（线性空间 + 接近 BFS 的时间）
• [ ] 推导 IDS 的时间复杂度 $O(b^d)$ 并对比 BFS
• [ ] 写出 best-first search 框架与 $f=g$（UCS）、$f=h$（Greedy）、$f=g+h$（A*）三特例
• [ ] 给出贪心搜索的完备性/时间/空间/最优性结论
• [ ] 写出 A* 的评价函数 $f(n)=g(n)+h(n)$
• [ ] 陈述并证明 A* TREE-SEARCH 在 $h$ 可采纳时最优
• [ ] 定义可采纳性 ($h\le h^*$) 与一致性 ($h(n)\le c(n,a,n')+h(n')$)，说明一致⇒可采纳
• [ ] 证明一致启发式下 $f$ 沿路径单调不减
• [ ] 陈述 A* GRAPH-SEARCH 在 $h$ 一致时最优
• [ ] 说出 A* 扩展节点的范围（$f<C^*$ 全扩、$f=C^*$ 部分扩、$f>C^*$ 不扩）
• [ ] 解释 A* 的 practical 版本为何要"重新打开"已关闭节点
• [ ] 给出 8-puzzle 的 $h_1$（错位数）、$h_2$（曼哈顿距离）并会计算
• [ ] 定义支配性 (dominance) 并解释 $h_2$ 为何优于 $h_1$
• [ ] 证明 $h=\max(h_a,h_b)$ 仍可采纳且占优
• [ ] 用松弛问题构造可采纳启发式（8-puzzle 三种松弛）
• [ ] 说出局部搜索的适用条件（路径无关、目标即解、常数空间）
• [ ] 列出爬山、模拟退火、局部剪枝、遗传算法各自的思想与改进机制
• [ ] 说明模拟退火的理论保证（$T$ 降得够慢⇒概率 1 找到全局最优）
• [ ] 描述遗传算法的三大操作（选择/杂交/变异）与适应度函数