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

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

如果您希望您的启发式方法是可接受的，那么您应该为每个节点 n 设置 h(n) <=h*(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

这是一个有效的候选人。

Answer 2

如果您分配了一个递减的最优解路径深度的启发式函数（但试图不违反高估可接受性条件），则结果启发式是可接受的但不一致。