我明白为什么A*算法在启发式函数总是低估的情况下总是能找到通往目标状态的最优路径，但我无法为此创建一个正式的证明。

据我所知，随着路径的深入，f(n)的准确性会不断增加，直到达到目标状态时达到100%的准确性。此外，由于估算是低于实际成本的，因此不会忽略任何错误的路径，从而导致最优路径的产生。但是，我应该如何为此创建一个证明呢？

回答：

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

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

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

2. 启发式函数是单调的，即，如果h(n_i) < h(n_{i + 1})，那么real-cost(n_i) < real-cost(n_{i + 1})。

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

假设A*给出的路径在可接受且单调的启发式函数下不是最优的，并思考这在含义上意味着什么（你很快就会发现自己达到了矛盾），因此，你的原始假设被归结为荒谬。

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