如果你希望你的启发式算法是可接受的,那么对于每个节点n,都应该满足 h(n) <= h*(n)
,其中h*
是到目标的实际代价。在你的情况下,你需要:
h(A) <= 4
h(C) <= 3
h(G) <= 0
如果您希望您的估算方法具有一致性,那么您应该满足以下条件:h(G) = 0
和 h(n) <= cost(n, c) + h(c)
,其中节点c
是节点n
的子节点。因此在您的情况下:
h(A) <= 1 + h(C)
h(C) <= 3 + h(G) = 3
如果您希望不一致性以及满足可接受条件h(C) <= 3
,那么您应该确保h(A) > 1 + h(C)
。因此,任何满足以下条件的启发式算法:
h(A) > 1 + h(C)
h(C) <= 3
h(G) = 0
是可接受但不一致的。你给了
h(A) = 4
h(C) = 1
h(G) = 0
这是一个有效的候选者。
4 = h(A) <= A到G的实际成本 = 4
,1 = h(C) <= C到G的实际成本 = 3
。 - svef(A) > f(C)
,您的示例启发式不一致。因此,您的启发式h(A)=4, h(C)=1, h(G)=0
是可接受的,但不一致 - 这正是您要寻找的 :) - sve