Блог

Это моя реализация 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))
  

С первой картой путь найден сразу. На втором, однако, даже через полчаса путь не найден. Я пытался использовать более быстрый список, но это не имело никакого значения. Может кто-нибудь, пожалуйста, указать, в чем проблема?

Проблема с вашей реализацией заключается не в производительности, а скорее в том, что она на самом деле неверна — она никогда не заканчивается для второй карты!

В части, где узел удаляется из закрытого набора, отсутствует else: continue — если узел уже является частью любого набора — его нельзя добавлять в открытый набор!