-1
这是我实现A *的Python中A *实现缓慢的Python
class Node:
def __init__(self, (x, y), g, h, parent):
self.x = x
self.y = y
self.g = g
self.h = h
self.f = g+h
self.parent = parent
def __eq__(self, other):
if other != None:
return self.x == other.x and self.y == other.y
return False
def __lt__(self, other):
if other != None:
return self.f < other.f
return False
def __str__(self):
return "(" + str(self.x) + "," + str(self.y) + ") " + str(self.f)
def mean(lst):
print sum(lst)/len(lst)
def find_path(start_node, end_node, map, no_diag=True):
open_list = [start_node]
closed_list = []
solution = []
while len(open_list) > 0:
open_list.sort()
current_node = open_list.pop(0)
if current_node == end_node:
while current_node != None:
solution.append(current_node)
current_node = current_node.parent
break
for x,y in [(0,-1), (1,0), (0,1), (-1,0)]:
touching_node = Node((current_node.x+x, current_node.y+y), 10, (abs(end_node.x-current_node.x) + abs(end_node.y-current_node.y))*10, current_node)
tile_in_range = touching_node.x >= 0 and touching_node.y >= 0 and touching_node.x < len(map[0]) and touching_node.y < len(map)
if not tile_in_range or touching_node == current_node.parent or map[touching_node.y][touching_node.x] == 1:
continue
if touching_node in open_list:
n = open_list[open_list.index(touching_node)]
if n > touching_node:
open_list.remove(n)
else:
continue
if touching_node in closed_list:
n = closed_list[closed_list.index(touching_node)]
if n > touching_node:
closed_list.remove(n)
open_list.add(touching_node)
closed_list.append(current_node)
return solution
map = [[1,1,0,1,0,0],
[0,0,0,0,1,0],
[0,0,1,0,0,0],
[0,0,0,1,0,0],
[0,1,0,1,1,1],
[0,1,0,0,0,0]]
map2 = [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,0,0,2,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
def test(map, start, end):
for r in map:
print r
res = find_path(Node(start,1000,1000,None), Node(end,1000,1000,None), map)
for n in res:
print n
test(map, (0,5), (5,0))
test(map2, (3,8), (2,11))
随着第一张地图的路径中找到立竿见影。然而,在第二条路上,即使在半小时之后,路径仍未找到。我尝试使用更快的列表,但没有任何区别。有人能指出问题出在哪里吗?
什么是排序列表?这不是一个标准类型。 – misha
在这里倾销代码并寻求帮助不是一个提问的好方法。你确认你的代码没有进入无限循环吗?你有没有分析你的代码? – delnan
@misha排序列表来自一个名为[blist]的模块(http://pypi.python.org/pypi/blist/)。我认为使用普通的旧list.sort()是导致减速的原因 - 事实并非如此。 – matio2matio