编辑“︁双向搜索”︁

{{DISPLAYTITLE:双向搜索}}

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

== 算法原理 ==
双向搜索的核心思想是同时运行两个[[广度优先搜索]]（BFS）：
* 一个从初始节点（起点）向目标节点（终点）推进（正向搜索）。
* 另一个从目标节点向初始节点回溯（反向搜索）。

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

=== 算法步骤 ===
1. 初始化两个队列：`queue_start`（正向搜索）和`queue_end`（反向搜索）。
2. 分别用起点和终点初始化这两个队列，并记录已访问节点。
3. 每次迭代中：
   * 从`queue_start`中取出一个节点，扩展其邻居，检查是否在反向搜索的已访问集合中。
   * 从`queue_end`中取出一个节点，扩展其邻居，检查是否在正向搜索的已访问集合中。
4. 若发现交集，则重构完整路径并返回。

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

<syntaxhighlight lang="python">
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']
</syntaxhighlight>

'''输入说明'''：图以邻接表形式存储，起点为`'A'`，终点为`'F'`。<br>
'''输出结果'''：路径`['A', 'C', 'F']`。

== 可视化过程 ==
<mermaid>
graph LR
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    E --> F
</mermaid>

1. 正向搜索：A → B, C；反向搜索：F → C, E。
2. 在节点C处交集，合并路径得到A → C → F。

== 应用场景 ==
* '''社交网络关系链查找'''：如寻找两人之间的最短好友链。
* '''拼图游戏求解'''：已知初始状态和目标状态时快速找到移动步骤。
* '''路由规划'''：在地图应用中同时从出发地和目的地搜索路径。

== 复杂度分析 ==
{| class="wikitable"
|+ 时间复杂度对比
! 算法 !! 时间复杂度 !! 空间复杂度
|-
| 单向BFS || <math>O(b^d)</math> || <math>O(b^d)</math>
|-
| 双向BFS || <math>O(b^{d/2})</math> || <math>O(b^{d/2})</math>
|}

== 注意事项 ==
* '''适用条件'''：需明确知道目标节点，且反向搜索的邻居获取成本不能过高。
* '''终止条件'''：任一方向的队列为空时需提前终止（无解）。
* '''路径重构'''：需正确处理交会节点的拼接逻辑。

== 扩展阅读 ==
* 双向搜索也可与[[Dijkstra算法]]结合用于加权图的最短路径问题。
* 在状态空间较大时（如15拼图问题），双向搜索能减少内存消耗。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:搜索算法]]