Dijkstra算法与A*算法相比，何以更适合用于寻找最短路径？
2个回答
11
它并不比Dijkstra算法更擅长找到最短路径。只要使用A*的可接受启发式，它就能比Dijkstra算法更快地找到最短路径。
正如Mehrad在评论中指出的那样，如果你给A*一个返回0的启发式函数，它就会退化成Dijkstra算法。
维基百科关于A*搜索算法的文章上有大量关于这方面的好信息。
- Matthew Manela
3
如果您想要找到从给定源节点到图中所有节点的最短路径，Dijkstra算法比A*更好，因为如果不在特定目标处停止，Dijkstra会覆盖整个图。与简单的Dijkstra相比，A*是一种面向目标的算法，因此需要知道源和目标节点。如果您想要用A*算法覆盖具有N个节点的整个图，您基本上必须从源节点运行算法N次。
对于从源节点到图中许多目标的最短路径，Dijkstra也可能更好。根据目标的位置（尤其是距离源的距离），目标数M，图的大小，A*启发式的质量，将存在某个折点，其中运行一个Dijkstra比运行M次A*算法更好或性能更低。 编辑：受Matthew正确的批评评论的启发，我重新表述了一下并添加了一些注释：
对于从源节点到图中许多目标的最短路径，Dijkstra也可能更好。根据目标的位置（尤其是距离源的距离），目标数M，图的大小，A*启发式的质量，将存在某个折点，其中运行一个Dijkstra比运行M次A*算法更好或性能更低。 编辑：受Matthew正确的批评评论的启发，我重新表述了一下并添加了一些注释：
- Dijkstra在找到到所有节点的最短路径方面并不比A*更好。正确的说法应该是：它不比A*差。
- 要使用A*找到到所有节点的最短路径，可以将估计到目标节点成本的函数设置为零（因为没有目标节点）。将估计到目标节点成本的函数设置为零使A*与Dijkstra相同；Dijkstra是A*的一种特殊情况。（如果将函数设置为零，是否仍应将算法称为“A*”（而不只是“Dijkstra”）是有问题的，因为具有非零函数是A*的核心。）
- 当我们尝试找到到所有节点的最短路径时，我们也可以说：Dijkstra就足够了。 A*的细化在这里是不必要的，也没有帮助我们。
- 对于搜索图表的最后一个注释也适用，例如：查找距离给定源节点最近的标记节点。由于您事先不知道目标，因此无法定义估计到搜索节点成本的函数，因此不能应用A*（在较窄的意义上的非零函数）。
- Slauma
2
1我认为你关于Dijkstra更擅长查找所有节点的观点是不正确的。在A*算法中，你可以简单地省略对目标节点的早期检查，它将会像Dijkstra一样完成相同的任务。 - Matthew Manela
是的，你说得对。我在我的回答中添加了一些注释。但我仍然不满意。我本不应该回答的。 - Slauma
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接