A 算法

A 算法相比 Dijkstra 算法引入了对距终点距离的估计 $h(n)$，在扩展节点时根据

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

进行扩展，其中 $g(n)$ 为节点距起点的距离。

• 优先扩展 $f(n)$ 小的节点
• 注意到 $h(n)\equiv 0$ 时算法退化为 Dijkstra 算法

算法

• Open 表：已经被扩展但还未扩展其相邻节点的节点
• Close 表：已经被扩展且扩展了相邻节点的点
• 初始时，把初始节点放入 OPEN 表，CLOSED 为空
• 计算 s 的 f 值
• 当 OPEN 不为空时
  • 取出 OPEN 中 f 最小的节点 n
  • 如果 n 是目标节点，返回 n
  • 把 n 从 OPEN 移到 CLOSED
  • 扩展 n，得到所有子节点 $m_i$
  • 计算 $f(n,m_i)=g(n,m_i)+h(m_i)$
  • 如果 $m_i$ 是未访问过的节点（不在 OPEN 表和 CLOSED 表中），则加入 OPEN 表，记录 f 值和父节点
  • 如果 $m_i$ 被访问过（在 OPEN 表或 CLOSED 表中），且当前算出的 f 值更小，则更新 f 值和父节点，如果 $m_i$ 在 CLOSED 表中，还需要将它重新加入 OPEN 表并从 CLOSED 表中移除

然而，当 $h(n)$ 取得“不好”时，A 算法可能无法找到最优解。只有当 $h(n)\le h^{\ast }(n)$（$h^{\ast }(n)$ 为节点实际距终点距离），即估计比实际更乐观时，才能保证找到最优解，此时的 A 算法也称为 $A^{\ast }$ 算法。

• 若存在从初始节点 s 到目标节点 t 的路径，则 $A^{\ast }$ 算法必能找到最佳解
• 若定义了两个 h，且对所有非目标节点有 $h_2(n)>h_1(n)$ ，则 $A_1$ 扩展的节点数 $\ge$ $A_2$ 扩展的节点数

容易发现，已经在 CLOSED 表中的节点可能会被重新放回 OPEN 表中，导致多次重复扩展，导致搜索效率下降。

解决的途径：

• 对 h 加以限制，使得第一次扩展一个节点时就已经找到了从 s 到该节点的最短路径
• 对算法加以改进，避免或减少节点的多次扩展

h 的改进

如果对于任意两个节点 $n_i$ 和 $n_j$，其中 $n_i$ 是 $n_j$ 的父节点，有 $h(n_i)-h(n_j)\le C(n_i,n_j)$，且 $h(t)=0$，则称 $h$ 是单调的。此时可以证明，每次第一次扩展到节点时走的都是最短路径。

$A^{\ast }$ 的充分条件

$h$ 的单调性也是满足 $A^{\ast }$ 条件的充分条件：

要证 $h(u)\le h^{\ast }(u)$，设 $h^{\ast }(u)$ 对应的 $u$ 到 $t$ 的最短路中第一步为 $u\to v$，则 $h^{\ast }(u)=h^{\ast }(v)+C(u,v)$，若 $h(v)\le h^{\ast }(v)$，则

$$h(u)\le h(v)+C(u,v)\le h^{\ast }(v)+C(u,v)=h^{\ast }(u)$$

满足 $A^{\ast }$ 条件.

• 直观上讲，$h^{\ast }$ 显然是满足三角不等式的，因此一个合理的 h 也应该满足三角不等式
• 从另一个角度上讲，因为 h 的估值总是过于乐观的，我们希望越搜索 h 的估值越准，f 越大（仍然小于 $f^{\ast }$），所以走了一段路程之后，h 会减少得没有实际走的路程多
• 此时可以保证每次扩展的点的 f 值是单调不减的

算法的改进

• OPEN 表上任意具有 $f(n)<f^{\ast }(s)$ 的节点一定会被扩展
• 被扩展的节点一定有 $f(n)\le f^{\ast }(s)$
• 可以用目前为止已扩展节点的最大 f 值估计 $f^{\ast }(s)$
• 新定义一个 NEST 集，为 OPEN 表中所有 $f<f_m$ 的节点，当 NEST 集合不为空时，从中选 g 最小的节点，否则选 OPEN 表中 f 值最小的节点，并将 $f_m$ 设为该值
• 从另一个角度看，$f<f_m$ 说明当前点的 f 值估计有问题（理想情况下，即每次搜索都是按最短路径搜索到每个点时，搜索到的 f 值应该是递增的），此时再按 f 值优先级排序是不合理的，应该按实际的 g 值来搜索
• 这种改进不能保证不会重复将点放入 OPEN 表中

应用：拼音输入法

汉字为 $S$，拼音为 $O$，有

$$P(S|O)=P(S)P(O|S)/P(O)$$

$P(O)$ 为常量，$P(O|S)\approx 1$，$P(S)={\prod }_{i=1}^{n}P(w_i|w_1\dots w_{i-1})$，只需使 $P(S)$ 最大即可

二元语法时，等价于求 $\max \left({\prod }_{i=1}^{n}P(w_i|w_{i-1})\right)$ 对应的句子，即 $\min \left(-{\sum }_{i=1}^n\log (P(w_i|w_{i-1}))\right)$ 对应的句子。

等价于一个最短路问题。

解决 $P(w_i|w_{i-1})$ 可能为 0 的问题，可以用一元概率进行平滑。