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

A*算法是一种启发式搜索算法，常用于解决路径规划问题，比如寻找从起点到终点的最短路径。在迷宫寻路问题中，它结合了广度优先搜索(BFS)和最佳优先搜索(DFS)的思想。

以下是使用Python实现A*算法的基本框架：

import heapq

def heuristic(a, b):
    # 计算两点之间的曼哈顿距离或其他适合的启发式函数
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(maze, start, end):
    frontier = [(0, start)]  # 开放列表，初始状态的f值为0
    came_from = {}          # 存储已经访问过的节点信息
    cost_so_far = {start: 0}  # 当前状态下到达节点的成本

    while frontier:
        _, current = heapq.heappop(frontier)

        if current == end:  # 如果找到目标，返回路径
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return list(reversed(path))

        for neighbor in neighbors(maze, current):  # 遍历相邻未访问节点
            tentative_g_score = cost_so_far[current] + 1  # 距离当前节点的代价
            if neighbor not in cost_so_far or tentative_g_score < cost_so_far.get(neighbor):
                cost_so_far[neighbor] = tentative_g_score
                priority = tentative_g_score + heuristic(neighbor, end)
                heapq.heappush(frontier, (priority, neighbor))
                came_from[neighbor] = current  # 更新回溯信息

# 假设neighbors函数返回给定节点周围的可行邻居
def neighbors(maze, node):
    row, col = node  # 将坐标转换为行和列
    possible_neighbors = []
    for drow, dcol in [(0, 1), (0, -1), (1, 0), (-1, 0)]:  # 上下左右
        new_row, new_col = row + drow, col + dcol
        if 0 <= new_row < len(maze) and 0 <= new_col < len(maze[0]):
            if maze[new_row][new_col] != 1:  # 避免非法位置（墙）
                possible_neighbors.append((new_row, new_col))
    return possible_neighbors

# 使用示例
maze = [[0, 1, 0], [0, 0, 0], [0, 1, 0]]  # 0代表空地，1代表墙壁
path = a_star_search(maze, (0, 0), (len(maze)-1, len(maze[0])-1))
print("Path found:", path)

在这个例子中，`heuristic`函数可以根据实际情况选择合适的启发式函数。`a_star_search`函数的核心是通过`heapq`库维护一个优先队列，总是处理下一个看起来最接近目标的节点。