0

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

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

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

4

1 回答 1

1

If you don't have any knowledge of an heuristic that fits to the content of the graph then you have to choose Dijkstra.

A* was developed for road maps, where for road distances the constraint applies that the direct distance is always shorter than going via another node. This constraint does not apply for general weighted graphs.

If you don't know such an additional constraint / heuristic of the content of your graph then you have to use Dijkstra

Further keep in mind that road map graphs are so huge that it is worth using A*. If your graph is not huge, then probably it is even not worth thinking whether to find any heuristic. Such a wrong heuristic could even make things worse.

So you could use Dijkstra, and only if you have a performance problem you could start thinking to find a heuristic.

于 2013-02-14T02:52:24.707 回答