#关于BFS的拓展（2）——双向广搜，A*

这两种都是BFS的优化方法。

双向广搜

相当于从起点和终点轮流进行扩展，最后如果两边各自有一个状态发生重复的话，说明这两个搜索过程相遇了，由此可以合并出起点到终点的最小步数。

一般适用于最小步数模型，即把这个状态看做无向图的一个点。

再有一个小优化就是每一次扩展时选择当前队列里元素个数较少的一方来扩展。

把BFS里的队列改为优先队列（小根堆），每次取优先队列的队头元素。

存储的时候存储从起点到当前点的真实距离和从当前点到终点的估价距离。

排序关键字是两个距离之和，估计的是当前这条路径从起点到终点的估价距离。

A*就是在扩展时每次都选择两个距离之和最小的点来扩展，未雨绸缪的感觉。

当终点第一次出队时算法结束。

要注意的是只能保证终点第一次出队的时候是最优解，其余点不一定。