我了解为什么A*算法在启发式函数始终低估时总是给出最优路径,但是我无法为其创建正式证明。
据我所知,对于每条被考虑的路径,随着其深入,f(n)
的准确性会增加,直到目标状态达到,此时它的准确率为100%。同时,由于估计值小于实际代价,没有错误的路径被忽略,从而导致寻找最优路径。但是我应该如何为此创建一个证明呢?
我了解为什么A*算法在启发式函数始终低估时总是给出最优路径,但是我无法为其创建正式证明。
据我所知,对于每条被考虑的路径,随着其深入,f(n)
的准确性会增加,直到目标状态达到,此时它的准确率为100%。同时,由于估计值小于实际代价,没有错误的路径被忽略,从而导致寻找最优路径。但是我应该如何为此创建一个证明呢?
启发式函数是可接受的,因为它永远不会高估成本。
启发式函数是单调的,即如果 h(ni) < h(ni + 1),那么 real-cost(ni) < real-cost(ni + 1)。