A*算法求解迷宫寻路问题（启发式算法）python代码

以下是使用A*算法求解迷宫寻路问题的Python代码示例：

import heapq

# 定义节点类
class Node:
    def __init__(self, x, y, g, h, parent):
        self.x = x
        self.y = y
        self.g = g
        self.h = h
        self.parent = parent

    def f(self):
        return self.g + self.h

# A*算法函数
def astar(maze, start, end):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四个方向
    rows, cols = len(maze), len(maze[0])

    def is_valid(x, y):
        return 0 <= x < rows and 0 <= y < cols and maze[x][y] == 0

    def heuristic(node):
        return abs(node.x - end[0]) + abs(node.y - end[1])

    start_node = Node(start[0], start[1], 0, heuristic(start), None)
    heap = [(start_node.f(), start_node)]
    visited = set()

    while heap:
        _, node = heapq.heappop(heap)
        if (node.x, node.y) == end:
            path = []
            while node:
                path.append((node.x, node.y))
                node = node.parent
            return path[::-1]

        if (node.x, node.y) in visited:
            continue
        visited.add((node.x, node.y))

        for dx, dy in directions:
            new_x, new_y = node.x + dx, node.y + dy
            if is_valid(new_x, new_y):
                new_node = Node(new_x, new_y, node.g + 1, heuristic(Node(new_x, new_y, 0, 0, None)), node)
                heapq.heappush(heap, (new_node.f(), new_node))

    return []

# 迷宫示例
maze = [
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start_point = (0, 0)
end_point = (4, 4)
path = astar(maze, start_point, end_point)
print(path)  # 输出最优路径