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

Question

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

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

score 6 · Accepted Answer

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

此外，仅当满足两个条件时，A* 才是最优的：

启发式是可以接受的，因为它永远不会高估成本。
启发式是单调的，即如果h(n _i ) < h(n _{i + 1} )，则real-cost(n _i ) < real-cost(n _{i + 1} )。

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

假设 A* 给出的路径在可接受的单调启发式中不是最优的，并考虑这意味着什么（你很快就会发现自己遇到矛盾），因此，你的原始假设被简化为荒谬.

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

score 3 · Accepted Answer

考虑最后一步，即完成最佳路径的那一步。

为什么 A* 必须选择那条路径？或者，换一种说法，为什么 A* 必须避免选择达到目标的次优路径？

提示：这就是启发式需要被接受的原因。请注意，可以选择次优路径，只要它没有完成路径（为什么？）。

这应该让您对如何制作证明有所了解。

2 回答 2