100种算法【Python版】第25篇——Bidirectional Search算法

1 算法原理

Bidirectional Search（双向搜索）算法是为了解决图中最短路径问题而提出的一种搜索策略，旨在提高搜索效率。该算法的核心思想是同时从起点和终点进行搜索，直到两个搜索相遇。这种方法有效地减少了搜索空间，特别在图或迷宫较大时，能够显著降低计算时间。

Bidirectional Search的基本原理是同时从起点和终点进行广度优先搜索（BFS），直到正向搜索和反向搜索在某个节点上相遇。该算法利用了以下几个关键概念：

• 双向扩展: 从起点和终点分别开始搜索，每一步扩展都考虑到当前搜索的状态。
• 相遇检测: 在每一步扩展后，检查当前搜索是否与对方的搜索相遇。这一相遇点即为最短路径的一个部分。
• 路径合并: 一旦找到相遇点，利用记录的路径信息重建完整路径。

Bidirectional Search算法的完整流程
（1）初始化:
创建两个队列，一个用于正向搜索（从起点开始），一个用于反向搜索（从终点开始）。
初始化两个集合或字典，分别用于记录已访问的节点及其路径。