A*搜索算法 - 元素码农

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

↑

# A*搜索算法

A*（A-Star）搜索算法是一种启发式搜索算法，它结合了Dijkstra算法的路径成本和启发式搜索的估计成本，能够高效地找到从起点到终点的最短路径。A*算法在路径规划、游戏AI和机器人导航等领域有广泛应用。

## 基本原理

A*算法的核心思想是：
1. 使用评估函数f(n) = g(n) + h(n)
   - g(n)：从起点到当前节点的实际代价
   - h(n)：从当前节点到目标节点的估计代价（启发函数）
2. 维护一个优先队列（开放列表）
3. 每次选择f值最小的节点进行扩展
4. 直到找到目标节点或确定无解

## 代码实现

### 基本实现

```python
from heapq import heappush, heappop

class Node:
    def __init__(self, position, g_cost, h_cost, parent=None):
        self.position = position
        self.g_cost = g_cost  # 从起点到当前节点的代价
        self.h_cost = h_cost  # 从当前节点到终点的估计代价
        self.f_cost = g_cost + h_cost  # 总估计代价
        self.parent = parent
    
    def __lt__(self, other):
        return self.f_cost < other.f_cost

def manhattan_distance(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

def a_star(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    
    def is_valid(x, y):
        return 0 <= x < rows and 0 <= y < cols and grid[x][y] == 0
    
    # 定义可能的移动方向（上、右、下、左）
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # 初始化开放列表和关闭列表
    open_list = []
    closed_set = set()
    
    # 创建起始节点
    start_node = Node(start, 0, manhattan_distance(start, end))
    heappush(open_list, start_node)
    
    while open_list:
        current = heappop(open_list)
        
        if current.position == end:
            # 找到路径，重建路径
            path = []
            while current:
                path.append(current.position)
                current = current.parent
            return path[::-1]
        
        closed_set.add(current.position)
        
        # 探索相邻节点
        for dx, dy in directions:
            next_x = current.position[0] + dx
            next_y = current.position[1] + dy
            next_pos = (next_x, next_y)
            
            if not is_valid(next_x, next_y) or next_pos in closed_set:
                continue
            
            g_cost = current.g_cost + 1
            h_cost = manhattan_distance(next_pos, end)
            
            neighbor = Node(next_pos, g_cost, h_cost, current)
            
            # 检查是否已经在开放列表中
            for node in open_list:
                if node.position == next_pos and node.g_cost <= g_cost:
                    break
            else:
                heappush(open_list, neighbor)
    
    return None  # 没有找到路径

# 使用示例
grid = [
    [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 = a_star(grid, start, end)
if path:
    print("找到路径:", path)
    # 可视化路径
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if (i, j) in path:
                print("* ", end="")
            else:
                print(f"{grid[i][j]} ", end="")
        print()
else:
    print("没有找到路径")
```

### 带对角线移动的实现

```python
def euclidean_distance(pos1, pos2):
    return ((pos1[0] - pos2[0]) ** 2 + (pos1[1] - pos2[1]) ** 2) ** 0.5

def a_star_diagonal(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    
    def is_valid(x, y):
        return 0 <= x < rows and 0 <= y < cols and grid[x][y] == 0
    
    # 包含对角线的移动方向
    directions = [
        (-1, 0), (0, 1), (1, 0), (0, -1),  # 上右下左
        (-1, -1), (-1, 1), (1, -1), (1, 1)   # 对角线
    ]
    
    # 移动代价（直线移动代价为1，对角线移动代价为1.414）
    costs = [1, 1, 1, 1, 1.414, 1.414, 1.414, 1.414]
    
    open_list = []
    closed_set = set()
    
    start_node = Node(start, 0, euclidean_distance(start, end))
    heappush(open_list, start_node)
    
    while open_list:
        current = heappop(open_list)
        
        if current.position == end:
            path = []
            while current:
                path.append(current.position)
                current = current.parent
            return path[::-1]
        
        closed_set.add(current.position)
        
        for (dx, dy), cost in zip(directions, costs):
            next_x = current.position[0] + dx
            next_y = current.position[1] + dy
            next_pos = (next_x, next_y)
            
            if not is_valid(next_x, next_y) or next_pos in closed_set:
                continue
            
            # 检查对角线移动时是否会穿墙
            if abs(dx) == 1 and abs(dy) == 1:
                if grid[current.position[0]][next_y] == 1 or \
                   grid[next_x][current.position[1]] == 1:
                    continue
            
            g_cost = current.g_cost + cost
            h_cost = euclidean_distance(next_pos, end)
            
            neighbor = Node(next_pos, g_cost, h_cost, current)
            
            for node in open_list:
                if node.position == next_pos and node.g_cost <= g_cost:
                    break
            else:
                heappush(open_list, neighbor)
    
    return None
```

## 性能分析

### 时间复杂度
- 最好情况：O(1) - 起点就是终点
- 最坏情况：O(b^d) - 需要遍历所有节点
- 平均情况：O(b * d) - 其中b是分支因子，d是解的深度

### 空间复杂度
- O(b^d) - 需要存储搜索过程中的所有节点

### 优缺点分析

优点：
1. 保证找到最优路径（当启发函数满足条件时）
2. 搜索效率高，避免不必要的探索
3. 灵活性强，可以通过调整启发函数优化性能
4. 适用于多种路径规划问题

缺点：
1. 内存消耗较大
2. 启发函数的设计影响算法性能
3. 在某些情况下可能退化为Dijkstra算法
4. 不适合高维空间搜索

## 应用场景

1. 游戏寻路系统
2. 机器人导航
3. GPS导航系统
4. 网络路由优化

## 实际应用示例

### 1. 游戏地图寻路

```python
class GameMap:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.obstacles = set()
        self.terrain_costs = {}  # 不同地形的移动代价
    
    def add_obstacle(self, x, y):
        self.obstacles.add((x, y))
    
    def set_terrain_cost(self, x, y, cost):
        self.terrain_costs[(x, y)] = cost
    
    def get_movement_cost(self, pos):
        return self.terrain_costs.get(pos, 1.0)
    
    def find_path(self, start, end):
        def heuristic(pos):
            return manhattan_distance(pos, end) * min(self.terrain_costs.values())
        
        def get_neighbors(pos):
            x, y = pos
            neighbors = []
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            
            for dx, dy in directions:
                new_x, new_y = x + dx, y + dy
                new_pos = (new_x, new_y)
                
                if (0 <= new_x < self.width and
                    0 <= new_y < self.height and
                    new_pos not in self.obstacles):
                    cost = self.get_movement_cost(new_pos)
                    neighbors.append((new_pos, cost))
            
            return neighbors
        
        # A*搜索实现
        open_list = [(0, start, [start])]
        closed_set = set()
        g_scores = {start: 0}
        
        while open_list:
            f_score, current, path = heappop(open_list)
            
            if current == end:
                return path
            
            if current in closed_set:
                continue
            
            closed_set.add(current)
            
            for neighbor, cost in get_neighbors(current):
                if neighbor in closed_set:
                    continue
                
                tentative_g = g_scores[current] + cost
                
                if neighbor not in g_scores or tentative_g < g_scores[neighbor]:
                    g_scores[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor)
                    heappush(open_list, (f_score, neighbor, path + [neighbor]))
        
        return None

# 使用示例
game_map = GameMap(10, 10)

# 添加障碍物
for x, y in [(2, 2), (2, 3), (2, 4), (3, 2), (4, 2)]:
    game_map.add_obstacle(x, y)

# 设置不同地形的移动代价
game_map.set_terrain_cost(1, 1, 2.0)  # 沼泽地形
game_map.set_terrain_cost(3, 3, 1.5)  # 丘陵地形

start = (0, 0)
end = (9, 9)

path = game_map.find_path(start, end)
if path:
    print("找到路径:", path)
else:
    print("没有找到路径")
```

### 2. 带时间窗口的路径规划

```python
class TimeWindowPathFinder:
    def __init__(self, grid, time_windows):
        self.grid = grid
        self.time_windows = time_windows  # 每个位置的可通行时间窗口
    
    def is_valid_move(self, pos, time):
        if pos not in self.time_windows:
            return True
        
        # 检查是否在任何时间窗口内
        for start_time, end_time in self.time_windows[pos]:
            if start_time <= time <= end_time:
                return False
        return True
    
    def find_path(self, start, end, start_time):
        def heuristic(pos, time):
            return manhattan_distance(pos, end)
        
        open_list = [(start_time + heuristic(start, start_time),
                      start_time, start, [start])]
        closed_set = set()
        
        while open_list:
            f_score, time, current, path = heappop(open_list)
            
            if current == end:
                return path, time
            
            state = (current, time)
            if state in closed_set:
                continue
            
            closed_set.add(state)
            
            # 考虑等待一个时间单位
            if self.is_valid_move(current, time + 1):
                heappush(open_list,
                         (time + 1 + heuristic(current, time + 1),
                          time + 1, current, path))
            
            # 考虑移动到相邻位置
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                next_x = current[0] + dx
                next_y = current[1] + dy
                next_pos = (next_x, next_y)
                
                if (0 <= next_x < len(self.grid) and
                    0