优先队列BFS
- 在学了双端队列BFS后,我们知道可以怎样处理对于图上边权是1或0的情况。但是对于更加具有普遍性的情况,也就是每次扩展都有各自不同的“代价”时,我们想要求出从初始状态到每个状态的最小代价,就相当于在一张带权图上求出从起点到每个节点的最短路。
- 那么,我们有以下两个方案:
- 方案一:
- 我们可以采用一般的广搜,用一般的队列来存储。
- 此时因为我们不能保证每个状态第一次入队时就能得到最小代价,所以我们只能允许一个状态多次更新、多次出进队列,从而更新它的最值,直到队列为空。
- 那么我们会发现此时的BFS会对搜索树进行很多重复的遍历与更新,直到求出最优解,其实这就是“迭代”的思想。不妨讨论一下最坏情况,该算法的时间复杂度会从一般的BFS的O(N)变为O(N2)。那么其实在最短路问题中,对应的就是SPFA算法。
- 方案二:
- 其实除了以上的算法,我们可以通过将一般的队列改为优先队列来进行广搜。
- 形象的说这里的优先队列就相当于一个二叉堆。我们可以每次从队列中取出当前代价最小的状态进行扩展(此时该状态一定已经是最优解,因为队列中其他状态的当前代价都不小于它,所以以后就不能再更新它了),沿着各条分支把到达的新状态加入到优先队列中,不断搜索,直到队列为空。
- 那么我们再看优先队列BFS中,每个状态也会被多次更新、多次进出队列,一个状态可能以不同的代价在队列中同时存在。但是,当每个状态第一次从队列中取出时,就得到了从初始状态到该状态的最小代价。从而之后被取出时,我们就可以直接忽略,不进行扩展。
- 所以,优先队列BFS中每个状态只扩展一次,时间复杂度只多了维护二叉堆的代价。时间复杂度只会从一般BFS的O(N)变为O(N log N)。同样在最短路问题中,对应的是堆优化的Dijkstra算法。
- 那么我们可以对BFS的形式,按照对应在图上边权情况进行分类总结:
- 问题只求最少步数,等价于在边权都为1的图上求最短路。
我们使用一般的BFS,时间复杂度为O(N)。
每个状态只访问入队一次,第一次出队时即为该状态的最小代价。
- 问题每次扩展的代价可能是0或1,等价于在边权只有0或1的图上求最短路。
使用双端队列,时间复杂度为O(N)。
每个状态会被更新入队多次,只扩展一次,第一次出队时就是该状态的最小代价。
- 问题每次扩展的代价可能是任意数值,等价于一般的最短路问题。
- (1)使用优先队列BFS,时间复杂度O(N log N)。
- 每个状态被更新入队多次,只扩展一次,第一次出队时即是该状态的最小代价。
- (2)使用迭代思想+一般的BFS,时间复杂度O(N2)。
- 每个状态被更新入队多次,扩展出队多次,最终完成记忆化搜索后,记录数组中保存了最小代价。
x
感谢您的支持,我会继续努力的!
扫码打赏,你说多少就多少