Python Maze BFS Кратчайший путь - PullRequest
Новая
       31

Python Maze BFS Кратчайший путь

0 голосов
/ 04 ноября 2019

Я изучаю алгоритмы поиска и пытаюсь реализовать алгоритм BFS, чтобы проверить, достижима ли цель в лабиринте при заданной стартовой позиции. Лабиринт был импортирован из текстового файла в виде 2D-массива. Мое решение, похоже, нашло цель, однако я не могу отобразить только выбранный путь, я могу отобразить только все посещенные узлы. Я хотел бы отобразить лабиринт после запуска алгоритма с маркерами, обозначающими пройденный путь. В настоящее время отображаются индексы, посещенные с помощью "."условное обозначение. Амперсанд представляет собой стену, которую нельзя пройти. Вот мой код: 

def BFS(maze, start, goal):

queue = deque([start])

visited = set(([start]))

while(queue):

    x, y = queue.popleft()

    if ((x,y) == goal):
        return x

    if (start != (x,y)):
        maze[x][y] = '.'

    visited.add((x,y))

    if (maze[x][y+1] != "&" and (x,y+1) not in visited):
        queue.append((x,y+1))

    if (maze[x][y-1] != "&" and (x,y-1) not in visited):
        queue.append((x,y-1))

    if (maze[x-1][y] != "&" and (x-1,y) not in visited):
        queue.append((x-1,y)) 

    if (maze[x+1][y] != "&" and (x+1,y) not in visited):
        queue.append((x+1,y))

Спасибо

1 Ответ

1 голос
/ 04 ноября 2019

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

...