A*搜索算法详解（Python实现路径规划与人工智能寻路）

A*算法的基本步骤

1. 将起点加入“开放列表”（待探索的节点）。
2. 重复以下过程，直到找到终点或开放列表为空：
• 从开放列表中取出 f(n) 最小的节点作为当前节点。
• 将其移入“关闭列表”（已探索的节点）。
• 检查当前节点的所有邻居：
• 如果邻居是障碍物或已在关闭列表，跳过。
• 计算该邻居的 g、h、f 值。
• 如果该邻居不在开放列表，则加入；否则，若新路径更优（g 更小），则更新其父节点和 g 值。
3. 如果终点被加入开放列表并被选中，则回溯路径；否则无解。

Python实现A*算法

下面我们用 Python 编写一个简单的 A* 算法，用于在二维网格中寻找路径。我们将使用曼哈顿距离作为启发函数。

import heapqclass Node:    def __init__(self, position, parent=None):        self.position = position  # (x, y)        self.parent = parent        self.g = 0  # 起点到当前点的实际代价        self.h = 0  # 当前点到终点的预估代价        self.f = 0  # 总代价 f = g + h    def __eq__(self, other):        return self.position == other.position    def __lt__(self, other):        return self.f < other.fdef heuristic(a, b):    """曼哈顿距离作为启发函数"""    return abs(a[0] - b[0]) + abs(a[1] - b[1])def astar(grid, start, end):    """A* 算法主函数    grid: 二维列表，0 表示可通行，1 表示障碍    start: 起点坐标 (x, y)    end: 终点坐标 (x, y)    """    start_node = Node(start)    end_node = Node(end)    open_list = []    closed_set = set()    heapq.heappush(open_list, start_node)    while open_list:        current_node = heapq.heappop(open_list)        closed_set.add(current_node.position)        # 找到终点        if current_node == end_node:            path = []            while current_node:                path.append(current_node.position)                current_node = current_node.parent            return path[::-1]  # 反转路径        # 探索四个方向（上下左右）        neighbors = [            (0, 1), (1, 0), (0, -1), (-1, 0)        ]        for dx, dy in neighbors:            neighbor_pos = (                current_node.position[0] + dx,                current_node.position[1] + dy            )            # 检查边界和障碍            if (                neighbor_pos[0] < 0 or neighbor_pos[0] >= len(grid) or                neighbor_pos[1] < 0 or neighbor_pos[1] >= len(grid[0]) or                grid[neighbor_pos[0]][neighbor_pos[1]] == 1 or                neighbor_pos in closed_set            ):                continue            neighbor_node = Node(neighbor_pos, current_node)            neighbor_node.g = current_node.g + 1            neighbor_node.h = heuristic(neighbor_pos, end)            neighbor_node.f = neighbor_node.g + neighbor_node.h            # 检查是否已在 open_list 中且新路径更优            in_open = False            for node in open_list:                if node.position == neighbor_pos and neighbor_node.g < node.g:                    node.g = neighbor_node.g                    node.f = neighbor_node.f                    node.parent = current_node                    in_open = True                    break            if not in_open:                heapq.heappush(open_list, neighbor_node)    return None  # 无路径# 示例使用if __name__ == "__main__":    grid = [        [0, 0, 0, 0, 1],        [1, 1, 0, 1, 0],        [0, 0, 0, 0, 0],        [0, 1, 1, 1, 0],        [0, 0, 0, 0, 0]    ]    start = (0, 0)    end = (4, 4)    path = astar(grid, start, end)    if path:        print("找到路径：", path)    else:        print("未找到路径")

应用场景与SEO关键词总结

A*搜索算法广泛应用于游戏AI寻路、机器人路径规划、地图导航系统等场景。掌握这一算法，是迈向人工智能寻路和Python路径规划的重要一步。

本文覆盖的核心SEO关键词包括：

• A*搜索算法
• Python路径规划
• A*算法教程
• 人工智能寻路

希望这篇教程能帮助你理解并实现A*算法！动手试试修改网格和起点终点，观察路径变化吧！