A*算法5*5迷宫寻路问题,用Python实现,列出代码
时间: 2024-05-15 18:17:33 浏览: 16
下面是一个简单的 Python 实现 A* 算法来解决 5x5 迷宫问题:
```python
from heapq import heappop, heappush
# 定义状态类
class State:
def __init__(self, cost, path, x, y):
self.cost = cost
self.path = path
self.x = x
self.y = y
def __lt__(self, other):
return self.cost < other.cost
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __repr__(self):
return f"<State x={self.x} y={self.y} cost={self.cost}>"
# 定义启发函数
def heuristic(state, goal):
return abs(state.x - goal.x) + abs(state.y - goal.y)
# 定义 A* 算法主函数
def astar(start, goal, maze):
heap = []
heappush(heap, start)
visited = set()
while heap:
current = heappop(heap)
if current == goal:
return current.path
if current in visited:
continue
visited.add(current)
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
x = current.x + dx
y = current.y + dy
if x < 0 or x >= 5 or y < 0 or y >= 5 or maze[x][y] == 1:
continue
next_state = State(current.cost + 1 + heuristic(State(x, y, 0, 0), goal),
current.path + [(x, y)],
x,
y)
heappush(heap, next_state)
return None
# 定义迷宫
maze = [
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 0]
]
# 定义起点和终点
start = State(0, [(0, 0)], 0, 0)
goal = State(0, [], 4, 4)
# 调用 A* 算法
path = astar(start, goal, maze)
# 输出结果
print(path)
```
上面代码中,`State` 类表示一个状态,包含当前的代价、路径、横坐标和纵坐标。`heuristic` 函数是启发函数,计算当前状态到终点状态的距离。`astar` 函数是 A* 算法主函数,使用堆来实现优先级队列。最后,定义迷宫,起点和终点,调用 A* 算法,输出结果。