A* 未加权图
A* for unweighted graphs
在未加权的有向图上使用 A* 搜索算法寻找最短路径是否有意义？
从阅读 http://www.cs.cmu.edu/~cga/ai-course/astar.pdf 看来，A* 在内存方面可能很昂贵，对于未加权的图也是如此，它甚至如何确定启发式？
这 post 似乎得出结论 A* 不应该用于未加权的图形。
在未加权的有向图上寻找最短路径的 best/lease 昂贵算法是什么？只是一个简单的 BFS？
完整的 A* 没有意义，除非你有一个有用的启发式方法来使用它。也就是说，如果您的启发式是猜测每个节点与目标的可能距离相同，那么 A* 搜索将给您与 BFS 相同的结果，因为您将查看通过较短路径到达的每个节点，然后再查看一个较长的节点到达的节点。
至于最好的，我知道的最好的算法是从两端开始的BFS，使用散列来检测第一个交集。也就是说，您标记源和目标。然后将源扩展到 1 的深度，然后将目标扩展到 1 的深度，然后将源扩展到 2 的深度，然后将目标扩展到 2 的深度，依此类推。当你相交时，你有从两个方向到交叉路口的最短路径。所以从源头遍历到交点，再从交点回到目标。
例如，这种算法用于在 LinkedIn 等大型社交网络中查找与您关系密切的人。
如果您有启发式算法，请使用 A*。如果你不这样做，就不要。
通常未加权的图具有可以利用的额外结构，例如。如果你的图实际上是一个二维网格，跳点搜索比普通的 A* 快得多。我们需要更多地了解您的问题域，以便进一步推荐。
在未加权的有向图上使用 A* 搜索算法寻找最短路径是否有意义？
从阅读 http://www.cs.cmu.edu/~cga/ai-course/astar.pdf 看来，A* 在内存方面可能很昂贵，对于未加权的图也是如此，它甚至如何确定启发式？
这 post
在未加权的有向图上寻找最短路径的 best/lease 昂贵算法是什么？只是一个简单的 BFS？
完整的 A* 没有意义，除非你有一个有用的启发式方法来使用它。也就是说，如果您的启发式是猜测每个节点与目标的可能距离相同，那么 A* 搜索将给您与 BFS 相同的结果，因为您将查看通过较短路径到达的每个节点，然后再查看一个较长的节点到达的节点。
至于最好的，我知道的最好的算法是从两端开始的BFS，使用散列来检测第一个交集。也就是说，您标记源和目标。然后将源扩展到 1 的深度，然后将目标扩展到 1 的深度，然后将源扩展到 2 的深度，然后将目标扩展到 2 的深度，依此类推。当你相交时，你有从两个方向到交叉路口的最短路径。所以从源头遍历到交点，再从交点回到目标。
例如，这种算法用于在 LinkedIn 等大型社交网络中查找与您关系密切的人。
如果您有启发式算法，请使用 A*。如果你不这样做，就不要。
通常未加权的图具有可以利用的额外结构，例如。如果你的图实际上是一个二维网格，跳点搜索比普通的 A* 快得多。我们需要更多地了解您的问题域，以便进一步推荐。