我们在类里面已经证明，如果 Tree-Search 中的 A* 是最优的，那么 h(n) 是可采纳的(Admissible Heuristics)。如果在 Graph-Search 中使用 A* 找到最优解，则 h(n) 是一致的。如果我们假设 A* 可以找到最优解，我们证明了 admissible 和 consistent 的性质。这表明一致/可接受是图/树搜索最优的必要条件。
但是，我不太确定如何证明它们也是充分条件。我试图弄清楚，但我仍然找不到很好的方法来证明它。例如，我不太确定如何证明可接受的可以导致使用 A* 进行树搜索的最优性？同样，如何证明一致性可以导致使用 A* 进行图搜索的最优性？提前致谢!
这是我第一次在 StackOverflow 上提问，如果我没有很好地表达我的问题，请见谅。 :)提前谢谢你!
最佳答案
This indicates that consistent /admissible are necessary conditions for optimality in Graph/Tree Searching.
不，这意味着它们是充分条件。事实上，反过来是不正确的 - 可以找到给定的非可接受启发式返回特定图的最佳结果的情况(简单的反例:只有一条路径的树将返回最佳路径对于任何启发式)。因此它们不是必要条件。
作为旁注，'consistent'意味着'admissible'，树是一种图，因此足以证明“admissible + graph”的情况，以及所有四种情况(admissible/consistent，tree/graph ) 立即暗示。
关于graph-algorithm - 如何证明 A* 搜索方法中的可接受/一致启发式会导致最优解？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63633540/