Python实现A*算法
时间: 2023-12-04 18:06:10 浏览: 51
A*算法是一种启发式搜索算法,用于在图形上或网络中找到最短路径。以下是Python实现A*算法的示例代码:
```python
from queue import PriorityQueue
def astar(start, goal, graph):
"""
A*算法实现函数
:param start: 起点
:param goal: 终点
:param graph: 图形或网络
:return: 最短路径
"""
frontier = PriorityQueue() # 创建优先队列
frontier.put(start, 0) # 将起点加入队列中
came_from = {} # 存储每个节点的前一个节点
cost_so_far = {} # 存储起点到每个节点的距离
cost_so_far[start] = 0
while not frontier.empty(): # 遍历队列
current = frontier.get() # 取出队列中的节点
if current == goal: # 如果当前节点是终点,返回最短路径
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path
for next in graph.neighbors(current): # 遍历当前节点的邻居节点
new_cost = cost_so_far[current] + graph.cost(current, next) # 计算到邻居节点的距离
if next not in cost_so_far or new_cost < cost_so_far[next]: # 如果到邻居节点的距离更短,更新距离和前一个节点
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next) # 计算优先级
frontier.put(next, priority)
came_from[next] = current
return None
def heuristic(a, b):
"""
估计函数
:param a: 节点a
:param b: 节点b
:return: 估计距离
"""
return abs(a.x - b.x) + abs(a.y - b.y)
```
其中,`graph`是一个包含了节点和边的类,实现了`neighbors`方法和`cost`方法。`neighbors`方法返回当前节点的邻居节点列表,`cost`方法返回从当前节点到邻居节点的距离。`heuristic`函数是一个估计函数,用于估计从当前节点到终点的距离。
示例代码可能不是完整的,但可以作为A*算法的简单实现。