启发式搜索¶
我们规定：
\(g(n)\) 为从初始状态 \(st\) 到达当前状态 \(n\) 的 当前最小代价
注意：这里的 “最小” 只是 “当前最小”，不排除可能 “以后” 会找到更小的，也就是说 \(g(n)\) 是可能会随搜索过程更新的
\(h(x)\) 表示从 \(n\) 到目标状态 \(end\) 的 预估代价
注意：预估代价是由 \(n\)、\(end\) 和计算方法唯一确定的，在搜索过程中不发生改变
\(h^*(n)\) 表示 \(n\) 到 \(end\) 的实际代价
预估代价 \(h(x)\) 可能高于，也可能低于实际代价 \(h^*(x)\)，我们把满足 \(h(x)\leqslant h^*(x)\) 的估价称作 “乐观的估价”
\(g^*(n)\) 表示 \(st\) 到 \(n\) 的 最小代价
这一最小代价是全局的，即 \(g^*(n)\leqslant g(n)\) 恒成立
引理一 对任意状态 \(n\)，\(g^*(n)=\text{Pst}(st,n)\)
引理二 对任意状态 \(n\)，\(h^*(n)=\text{Pst}(n,end)\)
引理三 对任意状态 \(n\)，\(g(n)=g^*(n)\) 时 \(f(n)\) 最小