第2章：状态空间搜索与启发式

树搜索与图搜索

搜索节点保存状态以及到达它的路径信息。同一个状态可以由多条路径到达，因此搜索树不是状态图本身。重复状态检测可避免在环中无限展开，但不能随意丢弃后来找到的更低代价路径。

BFS 按深度展开，在每步代价相同时得到最短路径。统一代价搜索按累计代价 $g(n)$ 展开，在非负边权的有限图上可按 Dijkstra 的规则求最短路。DFS 内存较省，但通常不保证最短，遇到无限深分支还可能不完备。

A* 使用

f(n)=g(n)+h(n),

其中 $h(n)$ 估计剩余最小代价。可采纳要求 $h(n)\le h^*(n)$ ；一致性要求对每条边 $n\to n'$ ，有 $h(n)\le c(n,n')+h(n')$ ，并令目标启发值为零。

一致性意味着路径上的 $f$ 不下降： $g(n')+h(n')\ge g(n)+h(n)$ 。因此在标准有限图、非负代价条件下，节点以最小 $f$ 取出时可以像 Dijkstra 一样固定最优 $g$ 。只有可采纳而不一致时，图搜索通常必须允许重新打开节点。

设最优目标代价为 $C^*$ 。在最优路径尚未被完全展开时，边界上存在该路径的一个节点，其 $f\le C^*$ 。一个次优目标的 $f$ 等于其路径代价，大于 $C^*$ ，因而不会先于所有这些候选被选中。

这依赖按最小 $f$ 取出目标时才停止，以及正确维护更优路径。第一次生成目标就返回，不能据上述论证保证最优。

删除约束得到的松弛问题，最优代价不大于原问题，可用作下界。例如只允许上下左右等代价移动且每步为 1 的网格，忽略障碍后得到曼哈顿距离。

两个可采纳启发式的最大值仍可采纳，并通常更有信息。直接相加可能重复计算同一代价，除非能证明代价分解互不重叠。

例：起点到 A 的代价 2，到 B 为 1；A 到目标为 2，B 到目标为 10。取 $h(A)=2,h(B)=1$ ，A* 可能先展开 B，但之后仍会选择总代价 4 的 A 路径。启发式不要求每一步都猜对方向。