如何证明A*搜索算法中的兼容启发式函数可以是可接受的启发式函数

Question

兼容启发式函数（h）满足以下条件：

h(n) <= c(n,a,n') + h(n')

****************************************************

可接受启发式函数（h）满足以下条件：

0 <= h(n) <= h*(n)

h*（n）是节点n到goal的实际距离

如果启发式函数是兼容的，那么如何证明它是可接受的？

非常感谢。

- Vahid Najafi

---

你不是忘了一个额外的条件吗？即h(goal)=0？ - Paul Hankin

Answer 1

假设h(n)不是可接受的，那么存在某个顶点n使得h(n) > h*(n)。

但由于h(n)的兼容性，我们知道对于所有的n`，都有h(n) <= c(n,a,n') + h(n')。

现在当n`是顶点G时，将这两个谓词结合起来，推导出一个矛盾，从而证明所需引理归谬法。

- Pieter Geerkens

---

作为图论TA，我不会给这样的答案满分，因为它缺少一些重要的解释，为什么h(n) <= c(n,a,n') + h(n')这个事实是矛盾的？没有限制允许h(n') > h*(n')，而且不等式成立。你需要找到最小的h值，使得h(n)>h*(n)，并对其进行相同的逻辑处理，以避免发生这种情况（请注意，您不能假设无限图的“最小值”）。 - amit

@amit：当然，上面的证明概述是不完整的；我试图引导一匹马去喝水，而不是撬开它的嘴巴，倒下加仑。顺便说一句：你真的读了我上面答案的第三段吗？ - Pieter Geerkens

Answer 2

如果您在h上添加一个附加条件（即h(goal)=0），则可以通过对从n到目标状态的最小代价路径进行归纳来证明它。

对于基本情况，当n = goal时，最小代价路径为0。然后h(goal) = 0 = h*（goal）。

对于一般情况，设n是一个节点，n’是从n到goal的最小路径上的下一个节点。那么h*（n）=c（n，n’）+h*（n’）>= c（n，n’）+h(n') >= h(n)，使用归纳假设得出第一个不等式，使用兼容性定义得出第二个不等式。

- Paul Hankin

---

此外，这个假设（h(goal) = 0）是必须的，否则根据定义，h(goal)>h*(goal)，并且启发式不可采纳。 - amit

然而，这个答案对于无限图是失败的。假设图形中h(v1) = 1，h(v2) = 1/2，h(v3) = 1/4，h(v4) = 1/8，...。虽然在理论上这是一个可接受的启发式方法，但归纳证明对于这样的图形是失败的。 - amit

@amit 在问题中使用的 A* 搜索算法排除了具有无限长度的路径。 - Paul Hankin