Astar算法python
时间: 2023-11-10 21:02:55 浏览: 46
A*算法是一种常用于路径规划的搜索算法,可以用Python实现。实现A*算法的关键在于如何设置启发式函数,常用的是曼哈顿距离。以下是一个简单的实现代码:
```python
def astar(start, goal, graph):
"""
A*算法
"""
# 所有已探索过的节点
explored = []
# 待探索的节点
queue = [[start]]
while queue:
# 获取当前节点路径中的最后一个节点
path = queue.pop(0)
node = path[-1]
if node not in explored:
neighbours = graph[node]
for neighbour in neighbours:
new_path = list(path)
new_path.append(neighbour)
queue.append(new_path)
if neighbour == goal:
return new_path
explored.append(node)
return "No path found"
# 例子:地图上从A到H的最短路径
graph = {'A': ['B', 'E'],
'B': ['A', 'C'],
'C': ['B', 'D', 'F'],
'D': ['C', 'G'],
'E': ['A', 'F'],
'F': ['C', 'E', 'H'],
'G': ['D'],
'H': ['F']}
print(astar('A', 'H', graph))
```
输出结果为 `['A', 'E', 'F', 'H']`,表示从节点A到节点H的最短路径是 A->E->F->H。