A*算法python代码
时间: 2023-08-31 11:08:33 浏览: 127
下面是一个简单的Python实现A*算法的代码示例:
```python
class Node:
def __init__(self, position=None, parent=None):
self.position = position
self.parent = parent
self.g = 0 # 实际代价
self.h = 0 # 估计代价
self.f = 0 # 总代价
def astar(grid, start, end):
open_list = []
closed_list = []
start_node = Node(start)
end_node = Node(end)
open_list.append(start_node)
while open_list:
current_node = open_list[0]
current_index = 0
for index, node in enumerate(open_list):
if node.f < current_node.f:
current_node = node
current_index = index
open_list.pop(current_index)
closed_list.append(current_node)
if current_node.position == end_node.position:
path = []
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1] # 反转路径
neighbors = []
positions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
for position in positions:
node_position = (current_node.position[0] + position[0], current_node.position[1] + position[1])
if node_position[0] < 0 or node_position[0] >= len(grid) or node_position[1] < 0 or node_position[1] >= len(grid[0]):
continue
if grid[node_position[0]][node_position[1]] != 0:
continue
new_node = Node(node_position, current_node)
neighbors.append(new_node)
for neighbor in neighbors:
if neighbor in closed_list:
continue
neighbor.g = current_node.g + 1
neighbor.h = abs(neighbor.position[0] - end_node.position[0]) + abs(neighbor.position[1] - end_node.position[1])
neighbor.f = neighbor.g + neighbor.h
if neighbor in open_list:
if neighbor.g > current_node.g:
continue
open_list.append(neighbor)
return None
```
这段代码实现了一个简单的A*算法。它使用`Node`类来表示地图中的节点,每个节点都有位置、父节点和代价信息。`astar`函数接受一个网格、起始位置和目标位置作为输入,并返回从起始位置到目标位置的最优路径。
在函数内部,我们使用开放列表和关闭列表来追踪待考察的节点和已经考察过的节点。我们通过计算实际代价g、估计代价h和总代价f来确定每个节点的优先级,并按照优先级从高到低来选择下一个节点进行考察。
如果找到了目标节点,我们通过回溯每个节点的父节点来构建路径,并将其返回。如果开放列表为空而我们仍然没有找到目标节点,那么说明无法找到路径,我们返回`None`。
希望这个代码示例能够帮助你理解A*算法的实现!
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)