双向搜索 - 元素码农

发布时间: 2025-03-21 18:28

↑

# 双向搜索

双向搜索（Bidirectional Search）是一种高级搜索算法，它同时从起点和终点开始搜索，当两个搜索过程相遇时，就找到了一条从起点到终点的路径。这种方法通常比单向搜索更快，因为两个搜索前沿会在中间某处相遇。

## 基本原理

双向搜索的工作原理如下：
1. 同时从起点和终点开始搜索
2. 维护两个搜索前沿（通常使用队列或集合）
3. 交替扩展两个搜索前沿
4. 检查是否有节点同时出现在两个搜索前沿中
5. 如果找到这样的节点，则可以构造完整的路径

## 代码实现

### 基本实现（使用BFS）

```python
from collections import deque

def bidirectional_search(graph, start, end):
    # 如果起点就是终点
    if start == end:
        return [start]
    
    # 从起点和终点开始的两个搜索前沿
    forward_queue = deque([(start, [start])])
    backward_queue = deque([(end, [end])])
    
    # 记录已访问的节点和它们的路径
    forward_visited = {start: [start]}
    backward_visited = {end: [end]}
    
    while forward_queue and backward_queue:
        # 扩展正向搜索
        vertex, path = forward_queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor in backward_visited:
                # 找到相遇点，合并路径
                return path + backward_visited[neighbor][::-1][1:]
            if neighbor not in forward_visited:
                forward_visited[neighbor] = path + [neighbor]
                forward_queue.append((neighbor, path + [neighbor]))
        
        # 扩展反向搜索
        vertex, path = backward_queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor in forward_visited:
                # 找到相遇点，合并路径
                return forward_visited[neighbor] + path[::-1][1:]
            if neighbor not in backward_visited:
                backward_visited[neighbor] = path + [neighbor]
                backward_queue.append((neighbor, path + [neighbor]))
    
    return None  # 没有找到路径

# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B', 'G'],
    'E': ['B', 'G'],
    'F': ['C', 'G'],
    'G': ['D', 'E', 'F']
}

path = bidirectional_search(graph, 'A', 'G')
print("找到的路径:", ' -> '.join(path) if path else "没有找到路径")
```

### 使用启发式函数的双向搜索

```python
from heapq import heappush, heappop

def bidirectional_a_star(graph, start, end, heuristic):
    def expand_frontier(frontier, visited, is_forward):
        if not frontier:
            return None
        
        f_score, current, path = heappop(frontier)
        
        for neighbor, cost in graph[current].items():
            if neighbor in visited:
                continue
            
            new_path = path + [neighbor]
            new_cost = f_score - heuristic(current, end if is_forward else start)
            new_cost += cost + heuristic(neighbor, end if is_forward else start)
            
            visited[neighbor] = new_path
            heappush(frontier, (new_cost, neighbor, new_path))
        
        return None
    
    forward_frontier = [(heuristic(start, end), start, [start])]
    backward_frontier = [(heuristic(end, start), end, [end])]
    
    forward_visited = {start: [start]}
    backward_visited = {end: [end]}
    
    while forward_frontier and backward_frontier:
        # 检查是否找到相遇点
        for node in forward_visited:
            if node in backward_visited:
                forward_path = forward_visited[node]
                backward_path = backward_visited[node]
                return forward_path + backward_path[::-1][1:]
        
        # 交替扩展两个方向
        expand_frontier(forward_frontier, forward_visited, True)
        expand_frontier(backward_frontier, backward_visited, False)
    
    return None

# 使用示例（带距离的图）
graph_with_costs = {
    'A': {'B': 4, 'C': 3},
    'B': {'A': 4, 'D': 5, 'E': 2},
    'C': {'A': 3, 'F': 6},
    'D': {'B': 5, 'G': 3},
    'E': {'B': 2, 'G': 4},
    'F': {'C': 6, 'G': 5},
    'G': {'D': 3, 'E': 4, 'F': 5}
}

def manhattan_distance(a, b):
    # 这里使用简单的字符串距离作为示例
    return abs(ord(a) - ord(b))

path = bidirectional_a_star(graph_with_costs, 'A', 'G', manhattan_distance)
print("找到的路径:", ' -> '.join(path) if path else "没有找到路径")
```

## 性能分析

### 时间复杂度
- 最好情况：O(b^(d/2))，其中b是分支因子，d是起点到终点的距离
- 最坏情况：O(b^d)，但实际上很少发生
- 平均情况：显著优于单向搜索

### 空间复杂度
- O(b^(d/2))，需要存储两个搜索前沿的节点

### 优缺点分析

优点：
1. 搜索速度快，通常比单向搜索更高效
2. 可以结合其他搜索策略（如启发式搜索）
3. 特别适合已知起点和终点的路径搜索
4. 在大规模图中效果显著

缺点：
1. 实现相对复杂
2. 需要额外的空间存储两个搜索前沿
3. 需要有效的相遇检测机制
4. 不适合只知道起点的搜索问题

## 应用场景

1. 社交网络中的关系链接查找
2. 地图导航系统中的路径规划
3. 游戏AI中的路径搜索
4. 大规模图数据库的查询优化

## 实际应用示例

### 1. 社交网络好友推荐

```python
class SocialNetwork:
    def __init__(self):
        self.connections = {}
    
    def add_connection(self, user1, user2):
        if user1 not in self.connections:
            self.connections[user1] = set()
        if user2 not in self.connections:
            self.connections[user2] = set()
        
        self.connections[user1].add(user2)
        self.connections[user2].add(user1)
    
    def find_connection_path(self, user1, user2):
        def expand_connections(queue, visited, other_visited):
            if not queue:
                return None
            
            current, path = queue.popleft()
            
            for friend in self.connections.get(current, []):
                if friend in other_visited:
                    return path, other_visited[friend]
                
                if friend not in visited:
                    visited[friend] = path + [friend]
                    queue.append((friend, path + [friend]))
            
            return None
        
        forward_queue = deque([(user1, [user1])])
        backward_queue = deque([(user2, [user2])])
        
        forward_visited = {user1: [user1]}
        backward_visited = {user2: [user2]}
        
        while forward_queue and backward_queue:
            # 交替扩展两个方向
            result = expand_connections(
                forward_queue, forward_visited, backward_visited)
            if result:
                forward_path, backward_path = result
                return forward_path + backward_path[::-1][1:]
            
            result = expand_connections(
                backward_queue, backward_visited, forward_visited)
            if result:
                backward_path, forward_path = result
                return forward_path + backward_path[::-1][1:]
        
        return None

# 使用示例
network = SocialNetwork()
network.add_connection("Alice", "Bob")
network.add_connection("Bob", "Charlie")
network.add_connection("Charlie", "David")
network.add_connection("David", "Eve")
network.add_connection("Eve", "Frank")

path = network.find_connection_path("Alice", "Frank")
print("社交连接路径:", ' -> '.join(path) if path else "没有找到连接路径")
```

### 2. 迷宫求解

```python
def solve_maze_bidirectional(maze, start, end):
    def is_valid(x, y):
        return (0 <= x < len(maze) and
                0 <= y < len(maze[0]) and
                maze[x][y] == 0)
    
    def get_neighbors(pos):
        x, y = pos
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        return [(x + dx, y + dy) for dx, dy in directions
                if is_valid(x + dx, y + dy)]
    
    forward_queue = deque([(start, [start])])
    backward_queue = deque([(end, [end])])
    
    forward_visited = {start: [start]}
    backward_visited = {end: [end]}
    
    while forward_queue and backward_queue:
        # 扩展正向搜索
        current, path = forward_queue.popleft()
        for neighbor in get_neighbors(current):
            if neighbor in backward_visited:
                return path + backward_visited[neighbor][::-1][1:]
            
            if neighbor not in forward_visited:
                forward_visited[neighbor] = path + [neighbor]
                forward_queue.append((neighbor, path + [neighbor]))
        
        # 扩展反向搜索
        current, path = backward_queue.popleft()
        for neighbor in get_neighbors(current):
            if neighbor in forward_visited:
                return forward_visited[neighbor] + path[::-1][1:]
            
            if neighbor not in backward_visited:
                backward_visited[neighbor] = path + [neighbor]
                backward_queue.append((neighbor, path + [neighbor]))
    
    return None

# 使用示例
maze = [
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)
end = (4, 4)

path = solve_maze_bidirectional(maze, start, end)
if path:
    print("找到路径:", path)
    # 可视化路径
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if (i, j) in path:
                print("* ", end="")
            else:
                print(f"{maze[i][j]} ", end="")
        print()
else:
    print("没有找到路径")
```

## 优化技巧

1. 平衡两个方向的扩展
```python
def balanced_expansion(forward_queue, backward_queue):
    # 选择较小的队列进行扩展
    if len(forward_queue) < len(backward_queue):
        return True  # 扩展正向
    return False  # 扩展反向
```

2. 使用启发式函数
```python
def estimate_distance(node1, node2):
    # 根据问题特点设计启发式函数
    return some_heuristic_value

def choose_expansion_direction(forward_frontier, backward_frontier):
    forward_best = min(n.f_score for n in forward_frontier)
    backward_best = min(n.f_score for n in backward_frontier)
    return forward_best < backward_best
```

3. 优化相遇检测
```python
def optimize_meeting_detection(forward_visited, backward_visited):
    # 使用更小的集合进行检查
    if len(forward_visited) > len(backward_visited):
        forward_visited, backward_visited = backward_visited, forward_visited
    
    # 检查相交
    for node in forward_visited:
        if node in backward_visited:
            return node
    return None
```

## 常见问题和解决方案

1. 内存消耗
- 问题：两个搜索前沿占用大量内存
- 解决：使用迭代加深或限制搜索深度

2. 不平衡扩展
- 问题：一个方向扩展过快
- 解决：实现动态平衡策略