Dijkstra 算法在寻找最短路径方面如何优于 A* 算法？
问问题
2181 次
2 回答
11
寻找最短路径并不好。只要您对 A* 有一个可接受的启发式算法，它就会比 Dijkstra 更快地找到短路路径。
正如 Mehrad 在评论中指出的那样，如果你给它一个返回 0 的启发式函数，A* 就会降级为 Dijktras。
A*的维基百科文章有大量关于这一切的好信息。
于 2011-02-13T06:18:29.320 回答
3
如果您想找到从给定源节点到图中所有节点的最短路径，Dijkstra 比 A* 更好，因为如果您不在特定目标处停止，Dijkstra 无论如何都会覆盖整个图。与简单的 Dijkstra 相比，A* 是一种面向目标的算法，因此需要知道源节点和目标节点。如果你想用 A* 算法覆盖 N 个节点的整个图，你基本上必须从源节点运行算法 N 次。
Dijkstra 也可能更适合于查找从源节点到图的许多目标的最短路径。根据目标的位置（尤其是与源的距离）、目标的数量 M、图形的大小、A* 启发式的质量，运行一个 Dijkstra 会比运行更好或更差的性能会出现一些收支平衡点M 次 A* 算法。
编辑：受马修正确批评评论的启发，我重新措辞并添加评论：
- Dijkstra 在找到所有节点的最短路径方面并不比 A* 更好。正确的是：它并不比 A* 差。
- 要找到到具有 A* 的所有节点的最短路径，需要将估计目标节点成本的函数设置为零（因为没有目标节点）。将估计目标节点成本的函数设置为零使 A* 与 Dijkstra 相同；Dijkstra 是 A* 的一个特例。（如果函数设置为零，是否仍应将算法称为“A*”（而不仅仅是“Dijkstra”）是值得怀疑的，因为具有非零函数是 A* 的核心。）
- 当我们试图找到所有节点的最短路径时，我们也可以说：Dijkstra 就足够了。A* 的细化不是必需的，在这里对我们没有帮助。
- 最后一句话也适用于在图中进行搜索，例如：找到标有特定标志的节点，该标志最接近给定的源节点。由于您事先不知道目标，因此无法定义估计搜索节点成本的函数，因此 A*（狭义的非零函数）不适用。
于 2011-02-13T14:15:31.087 回答