如何证明在A*搜索算法中使用可接受/一致的启发式函数可以得到最优解？

Question

我们在课堂上证明了如果 A* 在树搜索中是最优的，那么 h(n) 是可采用的（Admissible Heuristics）。如果在图搜索中使用 A* 找到最优解，则 h(n) 是一致的（Consistent）。我们假设 A* 可以找到最优解，证明了可采用和一致的特性。这表明，在图/树搜索中，一致/可采用是最优的必要条件。

然而，我不太确定如何证明它们也是充分条件。我试图弄清楚，但仍然找不到一个好的方法来证明它。例如，我不太确定如何证明可采用能够使用 A* 在树搜索中实现最优性？同样，如何证明一致性可以在使用 A* 进行图搜索时导致最优性呢？谢谢！

这是我第一次在 StackOverflow 上提问，如果我表述不清，请见谅。: ) 提前感谢！

- Leonard

---

为什么图搜索证明不适用于树搜索（因为树是一种特殊的图）？ - Scott Hunter

嗨，感谢您的评论！我已经证明了可接受性和一致性都是树/图搜索的必要条件。然而，我很困惑如何证明它们是导致最优性的充分条件。 - Leonard

我们在课堂上证明了，如果h(n)是可接受的，则在树搜索中使用A*算法是最优的。我不太确定如何证明可接受性可以导致在使用A*算法进行树搜索时达到最优。 - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft 哦，抱歉。我犯了一个粗心的错误。我现在已经修正了问题。谢谢你指出来。：） - Leonard

Answer 1

这表明在图/树搜索中，一致性/可接受是最优的必要条件。

不，它意味着它们是足够的条件。事实上，反过来并不正确 - 可以找到一些情况，在特定图形上给定的非可接受启发式返回最优结果 （一个简单的反例：只有一条路径的树将为任何启发式算法返回最优路径）。因此它们不是必要条件。

顺便说一下，“一致性”意味着“可接受”，而树是一种图形，因此证明“可接受+图形”情况就足够了，并且所有四种情况（可接受/一致性，树/图形）都会立即暗示出来。

- BlueRaja - Danny Pflughoeft

---

谢谢您的回复！根据您上面提到的反例，我认为它们确实不应该是必要条件。但我还是有点好奇，能否请您给我一些提示，如何证明它们是充分条件呢？ - Leonard

嗨，另外，我发现答案中提到的反例可能存在一些小缺陷。我认为算法的最优性意味着在任何图形中，算法总是能够找到最佳解决方案。然而，在上述反例中，它仅指定了一种类型的图形，在单路径树中非最优算法如 BFS 或 DFS 也可以找到上述的最优路径。因此，我认为这可能不是一个非常适合的反例。 - Leonard

@Leonard：是的，我们正在讨论所有图形。然而，要证明一个关于所有图形的陈述不成立，你只需要找到一个反例即可。这里的陈述来自你的问题：“如果在图搜索中使用A*算法找到最优解，则h(n)是一致的”，这是错误的。BFS和DFS找到相同路径的事实是无关紧要的。 - BlueRaja - Danny Pflughoeft