search - 可接纳性并不能保证 A* 的最优性？

Question

我正在为即将到来的考试做准备，并在一张纸上遇到了这个问题：

解释为什么在使用 A* 进行图搜索时，采用启发式方法来保证发现最优路径是不够的。

我一直在思考这个问题并试图解释它，但我无法解决这个问题？我在这里看过其他类似的 Q，但他们谈论的是可接纳性如何保证最优性。

A* 最优性的基本证明依赖于以下事实：
假设我们有两个目标状态 G 和 G2，其中 f(G) = f* 是最优解，G2 是次优解。
n 是 G 的直接祖先，因此必须在 G 之前扩展。
从可接纳性我们知道，无论 f(n) 是什么，它都必须 <= f*。
然而，如果我们选择在 n 之前扩展 G2，这意味着 f(G2) <= f(n)，因此 f(G2) <= f*。
这与前面的说法相矛盾，即 f(G2) 是次优的，因此 f(G2) > f*。

       S
      / \
     n   G2
    /
   G

对我来说，这个证明完全依赖于可接纳性，而一致性确实对其没有影响。虽然证明依赖于 f(G) 大于 f(n)，这是由一致性提供的，但在这种情况下，可接纳性也提供了它？因为除非启发式高估了距离，否则 f(n) 不可能大于 f(G)？

标签： searcha-starconsistency

Answer 1

他们错了。可接纳性是 A* 找到最优路径的必要条件和充分条件。

作者可能很困惑，因为运行时最优性（即快速运行的算法）需要一致的启发式。