A*寻路算法可视化

指标	复杂度	说明
时间复杂度	O(E)	最坏情况，取决于启发函数质量
实际性能	远优于Dijkstra	启发式引导减少探索节点
空间复杂度	O(V)	存储Open和Closed列表

代码实现

import heapq

def heuristic(a, b):
    """曼哈顿距离"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def astar(grid, start, goal):
    """A*寻路算法
    grid: 2D网格, 0=可通行, 1=障碍
    """
    rows, cols = len(grid), len(grid[0])
    
    # 四方向移动
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    open_set = []
    heapq.heappush(open_set, (0, start))
    
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    
    while open_set:
        _, current = heapq.heappop(open_set)
        
        if current == goal:
            # 重建路径
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for dx, dy in directions:
            neighbor = (current[0] + dx, current[1] + dy)
            
            # 边界和障碍检查
            if (0 <= neighbor[0] < rows and
                0 <= neighbor[1] < cols and
                grid[neighbor[0]][neighbor[1]] == 0):
                
                tentative_g = g_score[current] + 1
                
                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(open_set, (f, neighbor))
    
    return None  # 无路径

import java.util.*;

public class AStar {
    
    static int heuristic(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
    
    public static List<int[]> astar(
            int[][] grid, int[] start, int[] goal) {
        
        int rows = grid.length, cols = grid[0].length;
        int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        
        // 优先队列: [f值, x, y]
        PriorityQueue<int[]> openSet = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
        
        Map<String, int[]> cameFrom = new HashMap<>();
        Map<String, Integer> gScore = new HashMap<>();
        
        String startKey = start[0] + "," + start[1];
        gScore.put(startKey, 0);
        openSet.offer(new int[]{
            heuristic(start, goal), start[0], start[1]
        });
        
        while (!openSet.isEmpty()) {
            int[] curr = openSet.poll();
            int x = curr[1], y = curr[2];
            
            if (x == goal[0] && y == goal[1]) {
                // 重建路径
                return reconstructPath(cameFrom, goal);
            }
            
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                    && grid[nx][ny] == 0) {
                    // 更新邻居...
                }
            }
        }
        return null;
    }
}

核心概念

时间与空间复杂度

应用场景

代码实现