Python启发式搜索算法详解（从零开始掌握A*路径规划）

用Python实现A*算法

下面是一个完整的A*算法实现，用于在二维网格中寻找从起点到终点的最短路径。

import heapqclass Node:    def __init__(self, position, parent=None):        self.position = position        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 a_star_search(grid, start, end):    open_list = []    closed_set = set()    start_node = Node(start)    end_node = Node(end)    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):                continue            if 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_node.position, end_node.position)            neighbor_node.f = neighbor_node.g + neighbor_node.h            # 如果已在open_list中且新路径更优，则更新            existing = False            for node in open_list:                if node == neighbor_node and neighbor_node.g < node.g:                    node.g = neighbor_node.g                    node.f = neighbor_node.f                    node.parent = current_node                    existing = True                    break            if not existing:                heapq.heappush(open_list, neighbor_node)    return None  # 无路径# 示例使用if __name__ == "__main__":    # 0 表示可通行，1 表示障碍物    grid = [        [0, 0, 0, 1, 0],        [0, 1, 0, 1, 0],        [0, 1, 0, 0, 0],        [0, 0, 0, 1, 0],        [0, 0, 0, 0, 0]    ]    start = (0, 0)    end = (4, 4)    path = a_star_search(grid, start, end)    print("找到的路径：", path)

代码解析

- Node 类表示搜索中的一个状态，包含位置、父节点和代价信息。

- heuristic 函数使用曼哈顿距离计算启发值，适用于只能上下左右移动的网格。

- a_star_search 是核心函数，使用优先队列（heapq）管理待探索节点。

应用场景

A*算法广泛应用于：

• 游戏AI中的角色自动寻路
• 机器人导航与路径规划
• 地图应用中的最短路线计算

总结

通过本教程，你已经掌握了Python启发式搜索算法的核心思想和A*实现方法。无论你是初学者还是有一定经验的开发者，都可以将此算法灵活运用于各种路径规划问题中。记住，选择合适的启发函数是提升搜索效率的关键！

关键词：Python启发式搜索算法、启发式搜索、A*算法、路径规划