【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)。
  • 每个状态被更新入队多次,扩展出队多次,最终完成记忆化搜索后,记录数组中保存了最小代价。
赞赏