Сохраняя путь поиска BFS - PullRequest
Новая
       10

Сохраняя путь поиска BFS

1 голос
/ 21 октября 2019

Учитывая лабиринт, начальную координату и конечную координату, 

maze = [
    [BLACK, BLACK, WHITE, WHITE],
    [BLACK, WHITE, WHITE, WHITE],
    [WHITE, WHITE, BLACK, WHITE],
    [WHITE, WHITE, BLACK, WHITE],
]
s = Coordinate(3, 0)
e = Coordinate(0, 3)

Я пытаюсь найти путь от начала до конца, используя BFS. Найти путь очень просто, но я борюсь с тем, чтобы сохранить путь к месту назначения. Я попробовал 

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
queue = collections.deque()
queue.append(s)
path = []
while queue:
    curr = queue.popleft()
    if curr == e:
        path.append(curr)
        return path
    path.append(curr)
    maze[curr.x][curr.y] = BLACK
    for x, y in directions:
        new_x, new_y = curr.x + x, curr.y + y
        if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
            continue
        queue.append(Coordinate(new_x, new_y))

Примерно так, но результат распечатывает все узлы, которые я посетил, вместо окончательного пути. Любые советы по сохранению правильного пути и удалению узла, который не принадлежит к окончательному пути?

Ответы [ 2 ]

1 голос
/ 21 октября 2019

Вместо ведения списка path вы можете поддерживать словарь edge_to, который отслеживает, какая из предыдущих вершин привела к посещению определенной вершины. Всякий раз, когда вы добавляете что-то в свою очередь, вы можете обновить edge_to. Модифицированная версия вашей функции с использованием этого подхода выглядит следующим образом: 

Coordinate = collections.namedtuple('Coordinate', ['x', 'y'])

def find_path(s, e):
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    queue = collections.deque()
    queue.append(s)
    edge_to = {s: None}

    while queue:
        curr = queue.popleft()
        if curr == e:
            return path(edge_to, curr)
        maze[curr.x][curr.y] = BLACK
        for x, y in directions:
            new_x, new_y = curr.x + x, curr.y + y
            if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
                continue
            c = Coordinate(new_x, new_y)
            edge_to[c] = curr
            queue.append(c)

Обратите внимание на вызов path(...), когда вы найдете свою конечную вершину. Эта функция просто строит список из словаря edge_to: 

def path(edge_to, end):
    curr = end
    res = []
    while curr != None:
        res.append(curr)
        curr = edge_to[curr]
    return list(reversed(res))

Для вашего заданного лабиринта, а также начальных и конечных координат мы получаем следующий вывод: 

s = Coordinate(3, 0)
e = Coordinate(0, 3)
print(find_path(s, e))

Вывод 

[Coordinate(x=3, y=0), Coordinate(x=2, y=0), Coordinate(x=2, y=1), Coordinate(x=1, y=1), Coordinate(x=1, y=2), Coordinate(x=0, y=2), Coordinate(x=0, y=3)]
0 голосов
/ 21 октября 2019 
for x, y in directions:
    new_x, new_y = curr.x + x, curr.y + y
    if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
        continue
    queue.append(Coordinate(new_x, new_y))

ваш queue.append(Coordinate(new_x, new_y)) работает каждый раз, когда выполняется цикл for.

Мы хотим, чтобы это условие выполнялось только при выполнении нашего условия if, поэтому давайте попробуем что-то вроде этого: 

for x, y in directions:
    new_x, new_y = curr.x + x, curr.y + y
    if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
        queue.append(Coordinate(new_x, new_y))
        continue

Когда наше условие if выполнено, добавьте его и продолжайте. Дайте мне знать, если это поможет.

...