可接纳性并不能保证 A* 的最优性？
Admissibility does not guarantee optimality for A*?
我正在为即将到来的考试做准备，在 sheet 上遇到了这个问题：
Explain why it is not enough for a heuristic to be admissible to
guarantee the discovery of the optimal path, when conducting a graph
search using A*.
我一直在思考这个问题并尝试解释它，但我无法解决这个问题？我在这里查看了其他类似的问题，但他们谈论的是可接纳性 如何 保证最优性。
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)？
他们错了。可采性对于A*找到最优路径既是必要的也是充分的。
作者可能感到困惑，因为运行时最优性（即快速运行的算法）需要一致的启发式。
我正在为即将到来的考试做准备，在 sheet 上遇到了这个问题：
Explain why it is not enough for a heuristic to be admissible to guarantee the discovery of the optimal path, when conducting a graph search using A*.
我一直在思考这个问题并尝试解释它，但我无法解决这个问题？我在这里查看了其他类似的问题，但他们谈论的是可接纳性 如何 保证最优性。
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)？
他们错了。可采性对于A*找到最优路径既是必要的也是充分的。
作者可能感到困惑，因为运行时最优性（即快速运行的算法）需要一致的启发式。