不确定这是否是正确的地方，但是，
我在Java中编写了双向广度优先搜索算法，该算法同时从图中的起始节点和图中的目标节点进行搜索 . 在具有3000000（300万）个节点的图中，其中所有节点都与平均4个其他节点连接（与双向/双向边连接），在平庸的CPU上平均只需0.5秒即可找到最短路径任何两个随机节点，大约10秒是我发现超过30次测试运行的最坏情况时间 .
假设只需要搜索一条路径（例如，在绘制起点和目的地之间的路线时），在这种情况下使用具有合适启发式的A *算法会有什么好处？是的，找到路径可能会稍快一些，但A *很可能找不到最短的路径 .
有人可以详细说明为什么A *经常被选择而不是双向广度优先搜索，以及它在性能（计算时间，内存使用，找到最佳解决方案的机会等）方面的优势？
还有，复活节快乐大家！
1 回答
双向搜索在可行时很好，但它依赖于能够像开始节点一样容易地生成目标节点（例如，如何在国际象棋游戏中选择目标节点？），并且分支因子在两个方向上都相似 . 它依赖于能够向后退去，来到那里 . 即使你有一个很好的启发式，你也不可能在搜索的反向部分中从中获得很多优势 .