【OI学习笔记】优先队列BFS

优先队列BFS

• 在学了双端队列BFS后，我们知道可以怎样处理对于图上边权是1或0的情况。但是对于更加具有普遍性的情况，也就是每次扩展都有各自不同的“代价”时，我们想要求出从初始状态到每个状态的最小代价，就相当于在一张带权图上求出从起点到每个节点的最短路。
• 那么，我们有以下两个方案：

- 方案一：

• 我们可以采用一般的广搜，用一般的队列来存储。
• 此时因为我们不能保证每个状态第一次入队时就能得到最小代价，所以我们只能允许一个状态多次更新、多次出进队列，从而更新它的最值，直到队列为空。
• 那么我们会发现此时的BFS会对搜索树进行很多重复的遍历与更新，直到求出最优解，其实这就是“迭代”的思想。不妨讨论一下最坏情况，该算法的时间复杂度会从一般的BFS的O(N)变为O(N2)。那么其实在最短路问题中，对应的就是SPFA算法。

- 方案二：

• 其实除了以上的算法，我们可以通过将一般的队列改为优先队列来进行广搜。
• 形象的说这里的优先队列就相当于一个二叉堆。我们可以每次从队列中取出当前代价最小的状态进行扩展（此时该状态一定已经是最优解，因为队列中其他状态的当前代价都不小于它，所以以后就不能再更新它了），沿着各条分支把到达的新状态加入到优先队列中，不断搜索，直到队列为空。
• 那么我们再看优先队列BFS中，每个状态也会被多次更新、多次进出队列，一个状态可能以不同的代价在队列中同时存在。但是，当每个状态第一次从队列中取出时，就得到了从初始状态到该状态的最小代价。从而之后被取出时，我们就可以直接忽略，不进行扩展。
• 所以，优先队列BFS中每个状态只扩展一次，时间复杂度只多了维护二叉堆的代价。时间复杂度只会从一般BFS的O(N)变为O(N log N)。同样在最短路问题中，对应的是堆优化的Dijkstra算法。

- 那么我们可以对BFS的形式，按照对应在图上边权情况进行分类总结：

1. 问题只求最少步数，等价于在边权都为1的图上求最短路。
   我们使用一般的BFS，时间复杂度为O(N)。
   每个状态只访问入队一次，第一次出队时即为该状态的最小代价。
2. 问题每次扩展的代价可能是0或1，等价于在边权只有0或1的图上求最短路。
   使用双端队列，时间复杂度为O(N)。
   每个状态会被更新入队多次，只扩展一次，第一次出队时就是该状态的最小代价。
3. 问题每次扩展的代价可能是任意数值，等价于一般的最短路问题。

• (1)使用优先队列BFS，时间复杂度O(N log N)。
• 每个状态被更新入队多次，只扩展一次，第一次出队时即是该状态的最小代价。
• (2)使用迭代思想+一般的BFS，时间复杂度O(N2)。
• 每个状态被更新入队多次，扩展出队多次，最终完成记忆化搜索后，记录数组中保存了最小代价。