加权图的Dijkstra vs A*

Question

我正在尝试找出使用哪种算法来获得从给定起始节点到目标节点的最低成本路径。

A ----5---- B ---3--- C
|           |
|           /
D ----1-----E ------10------ F

我一直在研究Dijkstra和A*，因为它们都给出了这样一个问题的最佳解决方案。我的理解是Dijkstra只是一个启发式为0的A*。我已经实现了Dijkstra的算法，但想知道是否可以使用A*来代替。在上面这样一个非常简单的图中(没有任何其他信息)，是否有一个可接受的启发式算法，A*可以使用它来提供比Dijkstra更好的结果，或者Dijkstra是最优的算法吗？

Answer 1

如果你不了解适合图表内容的启发式方法，那么你必须选择Dijkstra。

A*是为道路地图开发的，其中，对于道路距离，约束适用于直接距离始终小于通过另一个节点的距离。此约束不适用于一般加权图。

如果您不知道图的内容的这种附加约束/启发式，那么您必须使用Dijkstra

此外，请记住，路线图图是如此巨大，因此值得使用A*。如果你的图不是很大，那么可能甚至不值得考虑是否要找到任何启发式方法。这种错误的启发式甚至会让事情变得更糟。

所以你可以使用Dijkstra，只有当你有性能问题时，你才可以开始考虑寻找启发式方法。