BFS с python, не может найти решение, когда конечная точка далека от начальной точки - PullRequest
Новая
       3

BFS с python, не может найти решение, когда конечная точка далека от начальной точки

0 голосов
/ 24 марта 2020

ОСНОВНОЙ АЛГОРИТМ для BFS приведен ниже. Требуется очень много времени, когда endRow и endColumn находятся далеко от startRow и startColumn, чтобы найти путь между startPoint и endPoint в сетке 10x10. Любое логическое объяснение о том, как сократить время выполнения? 

nums = Queue.Queue()
nums.put("")
add = ""
maze  = createMaze()
maze[endRow][endColumn] = "O"

while not findEnd(maze, add): 
    add = nums.get()
    #print(add)
    for j in ["L", "R", "U", "D"]:
        put = add + j
        if valid(maze, put):
            nums.put(put)

1 Ответ

1 голос
/ 24 марта 2020

Детали вашей реализации выглядят неясными, но, насколько я могу судить, у вас нет массива visited, который бы отслеживал посещенные вами ячейки, что преобразует ваш алгоритм из O (N ^ 2) к чему-то сумасшедшему, например O (4 ^ N) (где N - высота / ширина массива, если они равны). Вам просто нужно сохранить такой массив и пометить значения, когда вы добавляете их в очередь, и стараться не добавлять их снова в следующий раз, когда их увидят.

...