Ширина первая поисковая оптимизация - PullRequest
Новая
       33

Ширина первая поисковая оптимизация

0 голосов
/ 17 октября 2018

В последнее время я работал над некоторой вводной теорией графов , и натолкнулся на следующую формулировку проблемы:

Учитывая 2D матрицу в качестве входных данных, представляющихлабиринт (где ' E ' - начало матрицы, а ' S ' - конец), найдите длину кратчайшего пути от E до S. Стены в лабиринтеобозначается как « # », а доступные пробелы обозначаются «.».Также считается, что внешний край матрицы покрыт стенами.Если пути от E к S не существует, return -1.

Поскольку график не взвешен, я попытался реализовать алгоритм BFS , используя deque.Тем не менее, когда лабиринты начинают набирать около 500x500 , время выполнения достигает 10 с, а когда я пытаюсь подняться до 1000x1000 , это, очевидно, намного хуже.

Вот мой код: 

from collections import deque

def shortest_path_1(maze):
    wall, clear, endchar, startchar = '#', '.', 'S', 'E'
    height = len(maze)
    width = len(maze[0])

    def find_start(grid):
        for y in range(1, height-1):
            for x in range(1, width-1):
                if grid[y][x] == startchar:
                    return tuple([x, y])

    start = find_start(maze)

    queue = deque([[start]])

    seen = {start}
    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if maze[y][x] == endchar:
            return len(path)-1
        for (x2, y2) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 < x2 < width-1 and 0 < y2 < height-1 and maze[y2][x2] != wall and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

    return -1

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

Спасибо!

РЕДАКТИРОВАТЬ: Спасибо прекрасному человеку, который отредактировал мой вопрос, чтобы ключевые слова всплыли :).Вот пример матрицы, на которой вы можете запустить алгоритм: 

#####
#E#S#
#.#.#
#...#
#####

Это должно вернуть значение 6 .

EDIT2: исправлены некоторые небольшие ошибки.

1 Ответ

0 голосов
/ 17 октября 2018

Как указано в комментариях, вам не нужно хранить пути.Попробуйте это: 

from collections import deque

def shortest_path_1(maze):
    wall, clear, endchar, startchar = '#', '.', 'S', 'E'
    height = len(maze)
    width = len(maze[0])

    def find_start(grid):
        for y in range(1, height-1):
            for x in range(1, width-1):
                if grid[y][x] == startchar:
                    return (x, y, 0)

    start = find_start(maze)

    queue = deque([start])

    seen = set()
    while queue:
        x, y, d = queue.popleft()

        if not 0 <= x < width:
            continue
        if not 0 <= y < height:
            continue
        if maze[y][x] == wall:
            continue

        if maze[y][x] == endchar:
            return d

        if (x, y) in seen:
            continue
        seen.add((x, y))

        queue.append((x+1, y, d+1))
        queue.append((x-1, y, d+1))
        queue.append((x, y+1, d+1))
        queue.append((x, y-1, d+1))

    return -1

maze = [x for x in """
#####
#E#S#
#.#.#
#...#
#####
""".split('\n') if x]

print shortest_path_1(maze)
...