在未加权有向图上使用 A* 搜索算法来查找最短路径是否有意义？
来自阅读http://www.cs.cmu.edu/~cga/ai-course/astar.pdf看起来 A* 在内存方面可能会很昂贵，对于未加权的图也是如此，它如何确定启发式？
这篇文章here似乎得出结论 A* 不应该用于未加权图。
用于在未加权有向图上查找最短路径的最佳/租赁昂贵算法是什么？只是一个简单的 BFS？
最佳答案
除非你有一个有用的启发式方法来使用它，否则完全的 A* 是没有意义的。也就是说，如果您的启发式是猜测每个节点与目标的可能距离相同，那么 A* 搜索将为您提供与 BFS 相同的结果，因为您将在查看更短路径之前先查看较短路径到达的每个节点。较长的节点到达的节点。
至于最好的，我所知道的最好的算法是从两端开始的 BFS，使用哈希来检测第一个交集。也就是说，您标记源和目标。然后将源向外延伸到深度 1，然后将目标延伸到深度 1，然后将源向外延伸到深度 2，然后将目标延伸到深度 2，依此类推。当相交时，您有从两个方向到达交叉点的最短路径。所以从源出发遍历到交点，然后从交点回到目标。
例如，这种算法用于在 LinkedIn 等大型社交网络中查找与您关系密切的人。
关于algorithm - A* 表示未加权图表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48630459/