假设您没有到目标的距离的任何启发式函数，那么最佳的最佳解决方案是双向
BFS：
算法思想： 同时从源和目标进行BFS搜索：[BFS直到两者的深度均为1 ，直到两者的深度均为2，....]。
当找到位于两个BFS前端的顶点v时，该算法将结束。

算法行为 ：终止算法运行的顶点v将恰好在源和目标之间的中间。
在大多数情况下，此算法将产生比源BFS更好的结果（解释为什么比BFS更好），并且如果存在的话，肯定会提供答案。

为什么从源头上比BFS更好？
假设源到目标的距离是k，分支因子是B[每个顶点都有B边]。
BFS将打开：1 + B + B^2 + ... + B^k顶点。
双向BFS将打开：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)顶点。

对于较大的B和k，第二个显然比第一个好得多。

编辑：
注意，该解决方案不需要将整个图形存储在内存中，它只需要实现一个函数：successor(v)该函数将返回一个顶点的所有后继者[从v开始的1步之内即可获得的所有顶点]。这样，仅2 + 2B + ... + 2B^(k/2)应保存您打开的节点（如上所述）。为了进一步节省内存，您可以从一个方向使用迭代加深DFS而不是BFS，但是它将消耗更多时间。