非赋权图的A*

Question

在未加权的有向图上使用A*搜索算法来寻找最短路径有意义吗？

从读取http://www.cs.cmu.edu/~cga/ai-course/astar.pdf看起来A*在内存方面可能很昂贵，对于未加权的图，它如何确定启发式？

这篇文章here似乎得出结论，A*不应该用于未加权的图。

在未加权的有向图上寻找最短路径的最佳/昂贵的算法是什么？只是一个简单的BFS？

Answer 1

除非你有一个有用的启发式方法来使用它，否则整个A*是没有意义的。也就是说，如果您的启发式方法是猜测每个节点与目标的可能距离相同，那么A*搜索将给出与BFS相同的结果，因为您将先查看较短路径到达的每个节点，然后再查看较长路径到达的节点。

至于最好的算法，据我所知，最好的算法是从两端开始的BFS，使用散列来检测第一个交叉点。也就是说，您标记了源和目标。然后将源向外延伸到深度1，然后将目标向外延伸到深度1，然后将源向外延伸到深度2，然后将目标向外延伸到深度2，依此类推。当你相交时，你有从两个方向到交叉口的最短路径。因此，从源到交叉点遍历一个，然后交叉点回到目标。

例如，在像LinkedIn这样的大型社交网络中，这是一种被用来找出你身边的人的算法。

Answer 2

如果你有一个启发式，使用A*。如果你不这样做，那就不要做。

通常，未加权图具有可以利用的额外结构，例如。如果你的图形实际上是一个2D网格，跳点搜索比正常的A*要快得多。我们需要更多地了解您的问题域才能进一步推荐。