BFS算法的优化 双向宽度优先搜索
2023-09-14 09:11:51 时间
双向宽度优先搜索 (Bidirectional BFS) 算法适用于如下的场景:
- 无向图
- 所有边的长度都为 1 或者长度都一样
- 同时给出了起点和终点
以上 3 个条件都满足的时候,可以使用双向宽度优先搜索来求出起点和终点的最短距离。
算法描述
双向宽度优先搜索本质上还是BFS,只不过变成了起点向终点和终点向起点同时进行扩展,直至两个方向上出现同一个子节点,搜索结束。我们还是可以利用队列来实现:一个队列保存从起点开始搜索的状态,另一个保存从终点开始的状态,两边如果相交了,那么搜索结束。起点到终点的最短距离即为起点到相交节点的距离与终点到相交节点的距离之和。
Q.双向BFS是否真的能提高效率?
假设单向BFS需要搜索 N 层才能到达终点,每层的判断量为 X,那么总的运算量为 X ^ NXN. 如果换成是双向BFS,前后各自需要搜索 N / 2 层,总运算量为 2 * X ^ {N / 2}2∗XN/2。如果 N 比较大且X 不为 1,则运算量相较于单向BFS可以大大减少,差不多可以减少到原来规模的根号的量级。
from collections import deque def doubleBFS(start, end): if start == end: return 1 # 分别从起点和终点开始的两个BFS队列 startQueue, endQueue = deque(), deque() startQueue.append(start) endQueue.append(end) step = 0 # 从起点开始和从终点开始分别访问过的节点集合 startVisited, endVisited = set(), set() startVisited.add(start) endVisited.add(end) while len(startQueue) and len(endQueue): startSize, endSize = len(startQueue), len(endQueue) # 按层遍历 step += 1 for _ in range(startSize): cur = startQueue.popleft() for neighbor in cur.neighbors: if neighbor in startVisited: # 重复节点 continue elif neighbor in endVisited: # 相交 return step else: startVisited.add(neighbor) startQueue.append(neighbor) step += 1 for _ in range(endSize): cur = endQueue.popleft() for neighbor in cur.neighbors: if neighbor in endVisited: continue elif neighbor in startVisited: return step else: endVisited.add(neighbor) endQueue.append(neighbor) return -1
学习建议
Bidirectional BFS 掌握起来并不是很难,算法实现上稍微复杂了一点(代码量相对单向 BFS 翻倍),掌握这个算法一方面加深对普通 BFS 的熟练程度,另外一方面,基本上写一次就能记住,如果在面试中被问到了如何优化 BFS 的问题,Bidirectional BFS 几乎就是标准答案了。
参考资料
https://www.geeksforgeeks.org/bidirectional-search
应用例题
Shortest Path in Undirected Graph
Knight Shortest Path
Knight Shortest Path II
相关文章
- 关于搜索挖掘所想
- 数据结构与算法之美-11 图 深度和广度优先搜索 [MD]
- Atitit 数据挖掘之道 attilax总结 艾龙著 1. 数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。1 2. 数据(Data)-信息(information)-知识(K
- Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS,最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)
- 【华为云技术分享】自动网络搜索(NAS)在语义分割上的应用(二)
- 智能优化算法应用:基于麻雀搜索优化K-means图像分割算法 - 附代码
- 智能优化算法:瞬态搜索优化算法 -附代码
- 智能优化算法:回溯搜索优化算法-附代码
- 基于信息共享搜索策略的自适应灰狼算法-附代码
- 具有随机分形自适应搜索策略的蚁狮优化算法-附代码
- 一种优化局部搜索能力的灰狼算法 -附代码
- Python实现直方图梯度提升回归模型(HistGradientBoostingRegressor算法)并基于网格搜索进行优化同时绘制PDP依赖图项目实战
- 【Android Gradle 插件】自定义 Gradle 任务 ⑯ ( 从任务容器 TaskContainer 中搜索 Gradle 任务 | 压缩 packageDebug 任务输出文件 )
- 【Leetcode刷题Python】35. 搜索插入位置
- LeetCode 653. 两数之和 IV - 输入二叉搜索树
- 基于Astar算法的栅格地图最优路径搜索matlab仿真,可以修改任意数量栅格