我们在课堂上证明了如果 A* 在树搜索中是最优的,那么 h(n) 是可采用的(Admissible Heuristics)。如果在图搜索中使用 A* 找到最优解,则 h(n) 是一致的(Consistent)。我们假设 A* 可以找到最优解,证明了可采用和一致的特性。这表明,在图/树搜索中,一致/可采用是最优的必要条件。
然而,我不太确定如何证明它们也是充分条件。我试图弄清楚,但仍然找不到一个好的方法来证明它。例如,我不太确定如何证明可采用能够使用 A* 在树搜索中实现最优性?同样,如何证明一致性可以在使用 A* 进行图搜索时导致最优性呢?谢谢!
这是我第一次在 StackOverflow 上提问,如果我表述不清,请见谅。: ) 提前感谢!
然而,我不太确定如何证明它们也是充分条件。我试图弄清楚,但仍然找不到一个好的方法来证明它。例如,我不太确定如何证明可采用能够使用 A* 在树搜索中实现最优性?同样,如何证明一致性可以在使用 A* 进行图搜索时导致最优性呢?谢谢!
这是我第一次在 StackOverflow 上提问,如果我表述不清,请见谅。: ) 提前感谢!