A*算法求解迷宫问题用于实际应用场景

### 使用A*算法解决迷宫问题

#### A*算法简介
A*(A-star)算法是一种静态网络中求解最短路径最为有效的直接搜索方法之一[^3]。此算法不仅适用于电子游戏中的角色导航，在机器人技术里也广泛应用于自动行驶车辆的路径规划。

#### 应用场景描述
对于迷宫这类具有明确起点与终点的问题，可以利用A*来找到两者间的一条最优行走线路。特别是在存在多个障碍物的情况下，能够有效地避开这些阻碍并寻得最短距离或最少代价的通路[^5]。

#### 示例代码实现
以下是基于Python编写的简单版本A*算法用于处理固定大小(5×5)迷宫的例子：

import heapq

def heuristic(a, b):  # 启发式估计函数
    return abs(b[0]-a[0]) + abs(b[1]-a[1])

def a_star_search(maze, start, goal):
    open_set = []
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    
    heapq.heappush(open_set,(f_score[start], start))
    
    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]

        for dx, dy in [(0,-1),(-1,0),(1,0),(0,1)]:
            neighbor = (current[0]+dx,current[1]+dy)
            
            tentative_g_score = g_score.get(current, float('inf')) + 1
            
            if not (0<=neighbor[0]<len(maze)) or \
               not (0<=neighbor[1]<len(maze[0])) or \
               maze[neighbor[0]][neighbor[1]]==1 or\
               tentative_g_score >= g_score.get(neighbor,float('inf')):
                   continue
                
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = g_score[neighbor] + heuristic(goal, neighbor)
            heapq.heappush(open_set, (f_score[neighbor], neighbor))

maze = [[0]*5 for _ in range(5)]
for i,j in ((1,2),(2,2),(2,3),(3,3)):
    maze[i][j]=1
    
print("Maze:")
for row in maze:
    print(row)

path=a_star_search(maze, (0,0), (4,4))
if path is None:
    print("\nNo solution found.")
else:
    print(f"\nThe shortest path from top-left to bottom-right corner:\n{path}")

上述程序定义了一个`heuristic()`作为启发式的评估成本估算器；并通过优先队列维护待探索节点列表，每次选取F值最小者继续深入考察直至抵达目标位置或是穷尽所有可能性为止。最后打印出由起始坐标至终止坐标的最短路径序列[^4]。