algorithm - 启发式总是低估时 A* 算法最优性的证明

Question

我理解为什么 A* 算法总是给出到达目标状态的最佳路径，而启发式总是低估，但我无法为其创建正式证明。

据我所知，对于每条考虑的路径，随着它越来越深，f(n) 的准确性会增加，直到目标状态，它是 100% 准确的。此外，不会忽略不正确的路径，因为估计值低于实际成本；从而导致最优路径。但是我应该如何为它创建一个证明？

Answer 1

证明的主要思想是，当 A* 找到一条路径时，它找到了一条路径，该路径的估计值低于任何其他可能路径的估计值。由于估计是乐观的，因此可以安全地忽略其他路径。

此外，A* 只有在满足两个条件时才是最优的:

1. 启发式方法是可接受的，因为它永远不会高估成本。

2. 启发式是单调的，也就是说，如果h(n_i) < h(n_{i + 1})，然后实际成本(n_i) <实际成本(n_{i + 1})。

---

您可以通过相反的假设并扩展含义来证明最优性是正确的。

假设 A* 给出的路径不是具有可接受的单调启发式的最优路径，并考虑这在含义方面意味着什么(您很快就会发现自己陷入矛盾)，因此，您最初的假设变得荒谬。

由此您可以得出结论，您最初的假设是错误的，即 A* 在上述条件下是最优的。 Q.E.D.