A*（A星）算法解释

Question

我被要求调查改进Dijkstra算法。我一直在研究A星算法，但我发现许多解释使用了不熟悉的单词和数学符号。

我理解A星算法只考虑通往目标节点的边。例如，如果将A星算法应用于英国的道路网络，并且目的地是邓迪，我从伦敦开始，则仅检查通向北方的边。

这样理解至少有点正确吗？

- user3343975

---

只有指向北方的边缘会被检查，但是那些被估计为最快通向目标的边缘将首先被检查。如果发现这些边缘实际上并没有快速通向目标，那么其他边缘也必须被检查。 - Niklas B.

Answer 1

A*算法利用启发式函数猜测节点到目标的最小成本。因此，在选择节点时，不仅要分析从起点到该节点的成本，还要考虑从该节点到目标的预计成本。这样可以忽略可能导向错误方向的路径。

例如，如果您的启发式函数使用节点之间的地理距离，则先检查通往北部的道路（因为它们具有较小的预计总成本）。但是，在算法执行期间，这些通往北部的道路可能会累计非常长的实际距离（可能是因为有很多曲线）。然后还可以检查通往南部的道路。因此，如果南部的路径比所有弯曲通向北部的道路更短（不考虑英国实际道路图），则可以先向南走一段路再直接向北走。

启发式函数的性质定义了算法的质量。如果启发式函数给出距离的下限（即无法以比启发式函数所说的更便宜的成本到达目标），则该路径确实是最短路径。如果启发式函数不是下限，则可能允许其他路径（这可能是算法运行时间和路径质量之间的权衡）。启发式函数估计最小成本得越好，您就会检查越少的错误方向。即，如果启发式函数是恒定的，则最终得到的是普通的Dijkstra算法。如果启发式函数计算到目标的实际成本，则只会遵循最短路径，不会检查其他节点。

- Nico Schertler

---

非常好的解释。 - Niklas B.