3

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

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

兼容启发式

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

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

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

nh*(n) 是节点到节点的实际距离goal

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

非常感谢。

4

2 回答 2

2

假设h(n)是不可接受的,因此存在一些顶点n使得h(n) > h*(n)

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

现在当n`是顶点G时结合这两个谓词来推导矛盾,从而证明所需的引理归约和荒谬

于 2015-01-01T07:03:08.490 回答
2

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

对于基本情况,当 n = 目标时,最小成本路径为 0。那么 h(goal) = 0 = h*(goal)。

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

于 2015-01-01T08:05:44.953 回答