A *实现缓慢的Python

Question

这是我实现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)) 

随着第一张地图的路径中找到立竿见影。然而，在第二条路上，即使在半小时之后，路径仍未找到。我尝试使用更快的列表，但没有任何区别。有人能指出问题出在哪里吗？

Answer 1

与实现的问题不是性能，而是它实际上是不正确 - 它第二地图从未完成！

在从关闭集合中删除节点的部分中缺少else: continue - 如果该节点已经是任一集合的一部分，则不得将其添加到打开的集合中！