实验四 A*算法求解迷宫寻路问题实验实例Python代码

A*算法是一种启发式搜索算法，常用于解决像迷宫寻路这样的最短路径问题。在Python中实现A*算法通常会包含以下几个步骤：

1. 定义状态节点（Node）类，存储当前位置、代价（g值）、启发式值（h值）以及前驱节点。

class Node:
    def __init__(self, pos, g=0, h=0):
        self.pos = pos
        self.g = g
        self.h = h
        self.parent = None

2. 定义A*函数，输入为起点、终点和当前网格世界的数据结构（如邻接矩阵或邻接列表）。

def a_star(start, end, graph, heuristic):
    open_set = [start]
    came_from = {}
    start.g = 0
    start.h = heuristic(start, end)

    while open_set:
        current = min(open_set, key=lambda node: node.g + node.h)
        if current == end:
            return reconstruct_path(came_from, end)
        open_set.remove(current)
        
        for neighbor in graph[current.pos]:
            tentative_g = current.g + graph[current.pos][neighbor]
            if neighbor not in came_from or tentative_g < came_from[neighbor].g:
                came_from[neighbor] = current
                neighbor.g = tentative_g
                neighbor.h = heuristic(neighbor, end)
                neighbor.parent = current
                open_set.append(neighbor)

3. 计算启发式函数，这里假设曼哈顿距离（ Manhattan distance）作为例子，可以根据实际需求选择其他合适的方式。

def heuristic(node, goal):
    return abs(node.pos[0] - goal.pos[0]) + abs(node.pos[1] - goal.pos[1])

4. `reconstruct_path` 函数用来从终点逆向重建路径。

def reconstruct_path(came_from, current):
    path = []
    while current is not None:
        path.append(current.pos)
        current = came_from[current]
    return path[::-1]  # 返回路径数组，因为添加顺序是从后往前

运行这个算法时，你可以提供一个表示迷宫的地图，并设置起始点和目标点，A*会返回一条从起点到终点的最短路径。