写一个A星算法的python代码给我
时间: 2024-05-02 14:20:52 浏览: 15
以下是一个简单的A星算法的Python代码示例:
```python
import heapq
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.g = float('inf')
self.h = float('inf')
self.f = float('inf')
self.parent = None
def __lt__(self, other):
return self.f < other.f
class AStar:
def __init__(self, grid, start, end):
self.grid = grid
self.start = start
self.end = end
self.width = len(grid[0])
self.height = len(grid)
self.open_list = []
self.closed_list = []
def heuristic(self, a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def get_neighbors(self, node):
neighbors = []
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
if dx == 0 and dy == 0:
continue
x = node.x + dx
y = node.y + dy
if x < 0 or x >= self.width or y < 0 or y >= self.height:
continue
if self.grid[y][x] == 1:
continue
neighbor = Node(x, y)
neighbors.append(neighbor)
return neighbors
def get_path(self):
path = []
node = self.end
while node.parent:
path.append((node.x, node.y))
node = node.parent
path.append((self.start.x, self.start.y))
path.reverse()
return path
def solve(self):
start_node = Node(self.start[0], self.start[1])
end_node = Node(self.end[0], self.end[1])
start_node.g = 0
start_node.h = self.heuristic(start_node, end_node)
start_node.f = start_node.g + start_node.h
heapq.heappush(self.open_list, start_node)
while self.open_list:
current_node = heapq.heappop(self.open_list)
if current_node.x == end_node.x and current_node.y == end_node.y:
return self.get_path()
self.closed_list.append(current_node)
for neighbor in self.get_neighbors(current_node):
if neighbor in self.closed_list:
continue
tentative_g_score = current_node.g + 1
if neighbor not in self.open_list:
heapq.heappush(self.open_list, neighbor)
elif tentative_g_score >= neighbor.g:
continue
neighbor.parent = current_node
neighbor.g = tentative_g_score
neighbor.h = self.heuristic(neighbor, end_node)
neighbor.f = neighbor.g + neighbor.h
return None
```
使用示例:
```python
grid = [[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0]]
astar = AStar(grid, (0, 0), (4, 4))
path = astar.solve()
print(path) # 输出 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
```
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.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)
![](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)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)