当启发式总是低估时,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*在上述条件下是最优的.QED