有人能给我一个不一致的可接受启发式的例子吗？

Question

在这个图中:

假设h(C)= 1如果f(A)= g(A)+ h(A)= 0 + 4 = 4,并且f(C)= g(C)+ h(C)= 1 + 1 = 2然后f(C)不大于或等于f(A)因此这个例子是一致的和可接受的,但是有人能给我一个不一致的可接受启发式的例子吗？请

Answer 1

• 可受理

如果你希望你的启发式可以受理,那么你应该有一个h(n) <=h*(n)为每个节点n哪里h*是目标的实际成本.在你的情况下你想要:

h(A) <= 4
h(C) <= 3
h(G) <= 0

• 一致性

如果您希望您的启发式方法保持一致,那么您应该拥有该节点h(G) = 0并且h(n) <= cost(n, c) + h(c)节点c是节点的子节点c.所以在你的情况下

h(A) <= 1 + h(C)
h(C) <= 3 + h(G) = 3

如果你想要不一致,h(C) <= 3那么对于受理条件,你应该有这个h(A) > 1 + h(C).所以任何满足以下条件的heristics:

h(A) > 1 + h(C)
h(C) <= 3
h(G) = 0

是可以接受的,也不一致.你给了

h(A) = 4
h(C) = 1
h(G) = 0

这是一个有效的候选人.