帮我写一个双向A*搜索的Python代码
时间: 2024-03-28 18:14:03 浏览: 21
好的,以下是双向A*搜索的Python代码:
```
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.f = 0
self.g = 0
self.h = 0
self.parent = None
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def astar(start, end, grid):
open_list_start = []
open_list_end = []
closed_list_start = []
closed_list_end = []
start_node = Node(start[0], start[1])
start_node.g = 0
start_node.h = abs(end[0]-start[0]) + abs(end[1]-start[1])
start_node.f = start_node.g + start_node.h
end_node = Node(end[0], end[1])
end_node.g = 0
end_node.h = abs(end[0]-start[0]) + abs(end[1]-start[1])
end_node.f = end_node.g + end_node.h
open_list_start.append(start_node)
open_list_end.append(end_node)
while len(open_list_start) > 0 and len(open_list_end) > 0:
current_start = open_list_start[0]
current_end = open_list_end[0]
for i in range(len(open_list_start)):
if open_list_start[i].f < current_start.f:
current_start = open_list_start[i]
for i in range(len(open_list_end)):
if open_list_end[i].f < current_end.f:
current_end = open_list_end[i]
open_list_start.remove(current_start)
open_list_end.remove(current_end)
closed_list_start.append(current_start)
closed_list_end.append(current_end)
if current_start == current_end:
path = []
temp = current_start
while temp is not None:
path.append((temp.x, temp.y))
temp = temp.parent
temp = current_end.parent
while temp is not None:
path.insert(0, (temp.x, temp.y))
temp = temp.parent
return path
neighbours_start = []
neighbours_end = []
for x_shift, y_shift in ((-1, 0), (0, 1), (1, 0), (0, -1)):
neighbour_start = Node(current_start.x + x_shift, current_start.y + y_shift)
neighbour_end = Node(current_end.x + x_shift, current_end.y + y_shift)
if neighbour_start.x < 0 or neighbour_start.x >= len(grid) or neighbour_start.y < 0 or neighbour_start.y >= len(grid[0]) or grid[neighbour_start.x][neighbour_start.y] == 1:
continue
if neighbour_end.x < 0 or neighbour_end.x >= len(grid) or neighbour_end.y < 0 or neighbour_end.y >= len(grid[0]) or grid[neighbour_end.x][neighbour_end.y] == 1:
continue
if neighbour_start in closed_list_start:
continue
if neighbour_end in closed_list_end:
continue
neighbour_start.g = current_start.g + 1
neighbour_start.h = abs(end[0]-neighbour_start.x) + abs(end[1]-neighbour_start.y)
neighbour_start.f = neighbour_start.g + neighbour_start.h
neighbour_start.parent = current_start
neighbour_end.g = current_end.g + 1
neighbour_end.h = abs(end[0]-neighbour_end.x) + abs(end[1]-neighbour_end.y)
neighbour_end.f = neighbour_end.g + neighbour_end.h
neighbour_end.parent = current_end
neighbours_start.append(neighbour_start)
neighbours_end.append(neighbour_end)
for neighbour_start in neighbours_start:
for open_node_start in open_list_start:
if neighbour_start == open_node_start and neighbour_start.g > open_node_start.g:
continue
open_list_start.append(neighbour_start)
for neighbour_end in neighbours_end:
for open_node_end in open_list_end:
if neighbour_end == open_node_end and neighbour_end.g > open_node_end.g:
continue
open_list_end.append(neighbour_end)
return None
grid = [[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 1, 0, 0]]
start = (0, 0)
end = (3, 3)
path = astar(start, end, grid)
print(path)
```
希望对您有所帮助!
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)