Алгоритм * не находит кратчайший путь - PullRequest
Новая
       5

Алгоритм * не находит кратчайший путь

4 голосов
/ 19 сентября 2011

Я пытаюсь реализовать алгоритм A * в python, но столкнулся с проблемой при попытке найти путь к этой карте: 

X X X X X X X     S = Start
0 0 0 X 0 0 0     E = End
0 S 0 X 0 E 0     X = Wall
0 0 0 X 0 0 0
0 0 0 0 0 0 0

Я использую метод Манхэттена.Моя реализация находит путь, но не самый короткий.Ошибка начинается со второго хода - после движения вправо.В этот момент он может двигаться вверх, и стоимость эвристики будет равна четырем (три справа, одна вниз) или вниз (три справа, одна вверх).Есть ли способ, чтобы он выбрал кратчайший путь?

Код: 

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 __gt__(self, other):
        if other != None:
            return self.f > other.f
        return True

    def __str__(self):
        return "(" + str(self.x) + "," + str(self.y) + ") " + str(self.f)

def find_path(start, end, open_list, closed_list, map, no_diag=True, i=1):
    closed_list.append(start)
    if start == end or start == None:
         return closed_list
     new_open_list = []
     for x, y in [(-1,1),(-1,-1),(1,-1),(1,1),(0,-1),(0,1),(-1,0),(1,0)]:
        full_x = start.x + x
        full_y = start.y + y
        g = 0
        if x != 0 and y != 0:
            if no_diag:
                continue
            g = 14
        else:
            g = 10
        h = 10 * (abs(full_x - end.x) + abs(full_y - end.y))
        n = Node((full_x,full_y),g,h,start)
        if 0 <= full_y < len(map) and 0 <= full_x < len(map[0]) and map[full_y][full_x] != 1 and n not in closed_list:
            if n in open_list:
                if open_list[open_list.index(n)].g > n.g:
                    new_open_list.append(n)
                else:
                    new_open_list.append(open_list[open_list.index(n)])
            else:
                new_open_list.append(n)
    if new_open_list == None or len(new_open_list) == 0:
        return find_path(start.parent, end, open_list, closed_list, map, no_diag, i-1)
    new_open_list.sort()
    return find_path(new_open_list[0], end, new_open_list, closed_list, map, no_diag)

1 Ответ

7 голосов
/ 19 сентября 2011

Кажется, вы создаете новый открытый список для каждого узла, который содержит только соседей этого узла.По сути, это делает ваш поиск формой поиска в глубину, в то время как A * должен быть поиском в первую очередь.

Вам нужно использовать один открытый список, который будет обновляться соседями каждого узла при посещении этого сайта.узел.Старые узлы в открытом списке должны оставаться там до тех пор, пока они не пройдут и не будут перемещены в закрытый список.

Что касается того, что вы сказали в своем вопросе, все в порядке поиска, чтобы попытаться двигаться вверх, прежде чем вниз (так как согласноэвристика, они на одинаковом расстоянии от цели).Важно то, что в итоге выбранный путь будет самым коротким.

...