双向搜索

双向搜索（Bidirectional Search）是一种图搜索算法，它同时从起点和终点出发进行搜索，直到两个搜索路径相遇。该算法通过减少搜索空间显著提高效率，特别适用于已知目标状态且图结构对称的场景。

算法原理[编辑 | 编辑源代码]

双向搜索的核心思想是同时运行两个广度优先搜索（BFS）：

一个从初始节点（起点）向目标节点（终点）推进（正向搜索）。
另一个从目标节点向初始节点回溯（反向搜索）。

当两个搜索的边界（即当前待探索的节点集合）出现交集时，算法终止并返回合并后的路径。其时间复杂度从单向BFS的 $O (b^{d})$ 降低至 $O (b^{d / 2})$ ，其中 $b$ 是分支因子， $d$ 是路径深度。

算法步骤[编辑 | 编辑源代码]

1. 初始化两个队列：`queue_start`（正向搜索）和`queue_end`（反向搜索）。 2. 分别用起点和终点初始化这两个队列，并记录已访问节点。 3. 每次迭代中：

  * 从`queue_start`中取出一个节点，扩展其邻居，检查是否在反向搜索的已访问集合中。
  * 从`queue_end`中取出一个节点，扩展其邻居，检查是否在正向搜索的已访问集合中。

4. 若发现交集，则重构完整路径并返回。

代码实现[编辑 | 编辑源代码]

以下是Python实现双向BFS的示例（假设图为无向图）：

from collections import deque

def bidirectional_bfs(graph, start, end):
    if start == end:
        return [start]

    # 初始化正向和反向队列及已访问字典
    queue_start = deque([start])
    visited_start = {start: None}
    queue_end = deque([end])
    visited_end = {end: None}

    while queue_start and queue_end:
        # 正向搜索一步
        current_start = queue_start.popleft()
        for neighbor in graph[current_start]:
            if neighbor not in visited_start:
                visited_start[neighbor] = current_start
                queue_start.append(neighbor)
                if neighbor in visited_end:  # 交集检测
                    return reconstruct_path(visited_start, visited_end, neighbor)

        # 反向搜索一步
        current_end = queue_end.popleft()
        for neighbor in graph[current_end]:
            if neighbor not in visited_end:
                visited_end[neighbor] = current_end
                queue_end.append(neighbor)
                if neighbor in visited_start:  # 交集检测
                    return reconstruct_path(visited_start, visited_end, neighbor)

    return None  # 无路径

def reconstruct_path(visited_start, visited_end, meeting_node):
    # 从交会节点向起点回溯
    path = []
    node = meeting_node
    while node is not None:
        path.append(node)
        node = visited_start[node]
    path.reverse()  # 反转得到正向路径

    # 从交会节点向终点回溯（跳过交会节点避免重复）
    node = visited_end[meeting_node]
    while node is not None:
        path.append(node)
        node = visited_end[node]
    return path

# 示例图（无向图用邻接表表示）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 测试
print(bidirectional_bfs(graph, 'A', 'F'))  # 输出: ['A', 'C', 'F']