A* 执行缓慢的 Python

Question

这是我在 Python 中实现的 A*

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 - 如果该节点已经是任一集的一部分 - 则不得将其添加到开集中！