algorithm - 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 等大型社交网络中查找与您关系密切的人。