如何证明相容启发式算法在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(目标值)= 0)，则可以通过从n到目标状态的最小代价路径的归纳法来证明它。

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

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