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

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

• Admissibility

如果你想让你的启发式方法被接受，那么你应该拥有 h(n) <=h*(n)对于每个节点 n其中 h*是实现目标的实际成本。在你的情况下你想要:

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

• Consistency

如果您希望您的启发式算法保持一致，那么您应该拥有 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) .所以任何满足的遗传学:

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

可接受且不一致。你给了

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

这是一个有效的候选人。