基于Python实现A*算法在无权节点地图中的寻路需求

需求说明 #

输入为嵌套列表形式的网格地图，元素含义如下：

• 0：墙体
• 2、3、4：不同类型障碍物
• 1：可通行空白区域
• *：起点
• $$$：终点

需要实现一个Python函数，完成以下操作：

1. 从起点出发，通过父节点追踪标记路径方向
2. 到达终点后，回溯得到从起点到终点的最短路径
3. 返回包含路径坐标（行、列）的列表

实现方案 #

核心思路 #

因为是无权网格，A*算法的启发函数选用曼哈顿距离（计算高效且适配网格场景），核心流程分为：

• 地图预处理：定位起点、终点，统一可通行/障碍物规则
• A*路径搜索：用优先队列管理待检查节点，记录每个节点的父节点用于回溯
• 路径回溯：从终点反向遍历父节点，得到正向路径

完整代码实现 #

import heapq

def find_shortest_path(grid):
    # 定位起点和终点坐标
    start = None
    end = None
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '*':
                start = (i, j)
            elif grid[i][j] == '$$$':
                end = (i, j)

    if not start or not end:
        return []  # 找不到起点或终点，返回空路径

    # 定义可通行区域：1、*、$$$ 均为可走节点
    passable = {'*', '$$$', 1}
    # 定义四个移动方向：上下左右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 初始化A*算法核心数据结构
    open_heap = []
    heapq.heappush(open_heap, (0, start))  # 存储(f值, 节点坐标)
    
    parent = {}  # 记录每个节点的父节点，用于路径回溯
    g_score = {start: 0}  # 节点到起点的实际步数
    f_score = {start: manhattan_distance(start, end)}  # f = g + h（h为启发值）

    # 开始A*搜索循环
    while open_heap:
        # 取出当前f值最小的节点
        current_f, current_node = heapq.heappop(open_heap)
        
        # 到达终点则立即回溯路径
        if current_node == end:
            return reconstruct_path(parent, start, end)
        
        # 遍历四个方向的邻居节点
        for dx, dy in directions:
            neighbor = (current_node[0] + dx, current_node[1] + dy)
            # 检查邻居是否在地图边界内
            if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols:
                # 检查邻居是否为可通行区域
                if grid[neighbor[0]][neighbor[1]] not in passable:
                    continue
                
                # 计算邻居节点的g值（当前节点g值+1，无权网格每步代价为1）
                tentative_g = g_score[current_node] + 1
                
                # 如果邻居未被记录，或新路径更短，则更新节点信息
                if neighbor not in g_score or tentative_g < g_score[neighbor]:
                    parent[neighbor] = current_node
                    g_score[neighbor] = tentative_g
                    f_score[neighbor] = tentative_g + manhattan_distance(neighbor, end)
                    heapq.heappush(open_heap, (f_score[neighbor], neighbor))
    
    # 遍历完所有节点仍未找到终点，返回空路径
    return []

def manhattan_distance(a, b):
    """计算两个坐标间的曼哈顿距离，作为A*的启发函数"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def reconstruct_path(parent, start, end):
    """从终点反向回溯到起点，生成正向路径列表"""
    path = []
    current = end
    while current != start:
        path.append(current)
        current = parent.get(current)
        if not current:  # 父节点不存在，说明路径中断
            return []
    path.append(start)
    # 反转得到从起点到终点的正向路径
    return path[::-1]

代码关键说明 #

1. 地图预处理：提前遍历网格定位起点终点，避免搜索过程中重复判断
2. 曼哈顿距离：作为启发函数保证不会高估路径长度，确保A*能找到最短路径
3. 优先队列：通过heapq实现，确保每次处理的是当前最优（f值最小）的节点
4. 父节点追踪：parent字典记录每个节点的来源，实现需求中的「方向标记」
5. 路径回溯：从终点反向遍历父节点，反转后得到正向路径

测试示例 #

# 测试用网格地图
test_grid = [
    ['*', 1, 0, 1, '$$$'],
    [1, 1, 0, 1, 1],
    [0, 1, 1, 1, 0],
    [1, 2, 3, 4, 1]
]

path = find_shortest_path(test_grid)
print("最短路径坐标：", path)
# 输出示例：[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3), (0, 4)]

内容的提问来源于stack exchange，提问作者Jules