如何证明兼容启发式可以是 A* 搜索算法中的可接受启发式

Question

兼容启发式 (h) 是具有以下条件的启发式：

h(n) <= c(n,a,n') + h(n')

****************************************************

可接受的启发式 (h) 是具有以下条件的启发式：

0 <= h(n) <= h*(n)

h*(n) 是节点 n 到 goal

的真实距离

如果启发式兼容，如何证明它是可接受的？

非常感谢。

Answer 1

假设h(n)是不允许的，所以存在一些顶点n使得h( n) > h*(n)。

但是由于 h(n) 的兼容性，我们知道对于所有 n` 它认为 h(n) <= c(n,a,n') + h(n')。

现在将n`为顶点G的这两个谓词组合起来，推导出一个矛盾，从而证明所需的引理减少广告荒谬。

Answer 2

如果在 h 上添加一个附加条件（即 h(goal) = 0），则可以通过对从 n 到目标状态的最小成本路径进行归纳来证明。

对于基本情况，当 n = 目标时，最小成本路径为 0。然后 h(目标) = 0 = h*(目标).

对于一般情况，设 n 为节点，n' 为从 n 到目标的最小路径上的下一个节点。然后 h*(n) = c(n, n') + h*(n') >= c(n, n') + h(n') >= h(n) 使用归纳假设得到第一个不等式和相容性的定义。