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

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), 因此这个例子是一致和可接受的，但是有没有人能给出一个不一致但可接受的启发式算法的例子？

- user3880907

---

可能是一致和可接受的启发式的重复问题。 - Don Reba

你的例子启发式函数是否可接受？它从不高估实际成本。4 = h(A) <= A到G的实际成本 = 4，1 = h(C) <= C到G的实际成本 = 3。 - sve

@svs 是的，你是对的，我犯了个错误。 - user3880907

但是，由于 f(A) > f(C)，您的示例启发式不一致。因此，您的启发式 h(A)=4, h(C)=1, h(G)=0 是可接受的，但不一致 - 这正是您要寻找的 :) - sve

Answer 1

• 可接受性

如果你希望你的启发式算法是可接受的，那么对于每个节点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

这是一个有效的候选者。

- sve

---

非常感谢！我真的很感激，现在对我来说已经很清楚了！ :) - user3880907

@user3880907 没问题，我很乐意帮忙 :) - sve

很抱歉这么晚才提出来，但在满足启发式可接受且不一致的条件列表中，h(A)<=4也应该包括吧？ - Hani

Answer 2

如果你分配一个随着最优解路径深度递减的启发式函数（但尝试不违反允许性的高估条件），则结果启发式是允许的，但不是一致的。

- saeed foroutan