最佳优先搜索和A*搜索有什么区别？

Question

在我的教科书中，我注意到这两种算法几乎完全相同，我正在尝试理解它们之间的主要区别。

教科书使用A*算法遍历这个示例，就像使用最佳优先搜索算法一样。

任何帮助将不胜感激。

- Computerphile

Answer 1

最佳优先搜索算法基于启发式函数 f(n) = h，访问下一个具有最低启发式值（通常称为贪婪算法）的状态。它不考虑到达该特定状态路径的成本，只关心当前状态中哪个下一个状态的启发式最低。

A*搜索算法基于启发式 f(n) = h + g 访问下一个状态，其中 h 组件与最佳优先搜索中应用的启发式相同，但 g 组件是从初始状态到该特定状态的路径。因此，它选择下一个状态时并不仅考虑最低启发式值，而是考虑其启发式和到达该状态的成本能够得出的最低值。

在上面的例子中，当你从阿拉德（Arad）开始，你可以直接前往锡比乌（Sibiu）（253公里），或者去泽林德（Zerind）（374公里）或蒂米什瓦拉（Timisoara）（329公里）。在这种情况下，两种算法都选择锡比乌，因为它的 f(n) 值最小，为 253。

现在你可以扩展到任意一个状态，返回阿拉德（366公里）、奥拉迪亚（Oradea）（380公里）、法拉加斯（Faragas）（178公里）或林基乌齐亚维尔恰（Rimnicu Vilcea）（193公里）。对于 最佳优先搜索，法拉加斯将具有最小的 f(n) 值，为 178，但对于 A*，林基乌齐亚维尔恰将具有 f(n) = 220 + 193 = 413 的值，其中 220 是从阿拉德到林基乌齐亚维尔恰的费用（140+80），193 是从林基乌齐亚维尔恰到布加勒斯特的费用，但对于法拉加斯来说会更多，因为 f(n) = 239 + 178 = 417。

现在你可以清楚地看到，最佳优先搜索是贪婪算法，因为它会选择启发式较低但总体成本更高的状态，因为它不考虑从初始状态到达该状态的成本。

- MichaelDD

---

有些人也使用“最佳优先算法”一词来指代一类包括A*在内的启发式算法。详情请见：https://en.wikipedia.org/wiki/Best-first_search。 - seaotternerd

我认为你所说的“最佳优先搜索”是指“贪婪算法”。A*算法与贪婪最佳优先搜索算法的区别在于它考虑了已经走过的路径成本/距离g(n)。- 来自维基百科 - KRoy

Answer 2

A*算法通过使用启发式搜索来提高性能。A*结合了最佳优先搜索和均匀代价搜索的优点：使用启发式搜索确保找到优化路径，同时增加算法效率。A*函数的公式为f(n) = g(n) + h(n)，其中h(n)是任意随机顶点n和目标顶点之间的估计距离，g(n)是起点和任意顶点n之间的实际距离。如果g(n)=0，则A*变成最佳优先搜索。如果h(n)=0，则A*变成均匀代价搜索。

- Jianqiang Chen