迷宫自动寻路算法计算11*13迷宫从（7,12）到（7,1）的路径python

对于11x13的迷宫，如果你想要使用Dijkstra's algorithm（迪杰斯特拉算法）或者A*搜索算法来计算从点`(7, 12)`到`(7, 1)`的最短路径，Python可以这样实现。这里我会给出一个简化版的A*算法示例，假设迷宫是通过二维列表表示，其中0代表空地，1代表墙壁：

import heapq

# 定义迷宫数据
maze = [[0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1],
        [0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0],
        [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0],
        [1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
        [0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0],
        [0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0],
        [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1],
        [1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]]

# 定义节点结构
class Node:
    def __init__(self, x, y, cost=0, g=0, h=0):
        self.x = x
        self.y = y
        self.g = g
        self.h = h
        self.f = g + h  # A*算法中f值等于g+h

def a_star_search(start, end):
    start_node = Node(start[0], start[1])
    end_node = Node(end[0], end[1])

    open_set = [(start_node.f, start_node)]
    came_from = {}
    while open_set:
        _, current_node = heapq.heappop(open_set)

        if current_node == end_node:
            path = []
            while current_node in came_from:
                path.append((current_node.x, current_node.y))
                current_node = came_from[current_node]
            return path[::-1]  # 返回路径

        for dx, dy in [(0, -1), (-1, 0), (0, 1), (1, 0)]:  # 上下左右四个方向
            neighbor_x, neighbor_y = current_node.x + dx, current_node.y + dy
            if 0 <= neighbor_x < len(maze) and 0 <= neighbor_y < len(maze[0]):
                if maze[neighbor_x][neighbor_y] == 0:  # 遇到空地
                    new_cost = current_node.g + 1
                    if neighbor_x not in came_from or new_cost < came_from[neighbor_x].g:
                        came_from[neighbor_x] = current_node
                        neighbor_node = Node(neighbor_x, neighbor_y, cost=new_cost,
                                             g=current_node.g + 1, h=abs(neighbor_x - end_node.x) + abs(neighbor_y - end_node.y))
                        heapq.heappush(open_set, (neighbor_node.f, neighbor_node))

a_star_path = a_star_search((7, 12), (7, 1))
print("从(7, 12)到(7, 1)的最短路径:", a_star_path)