Измените мой BFS, чтобы он возвращал все пути, которые являются Целями и находятся на одном уровне, который минимален - PullRequest
Новая
       25

Измените мой BFS, чтобы он возвращал все пути, которые являются Целями и находятся на одном уровне, который минимален

0 голосов
/ 22 декабря 2018

Я реализовал алгоритм BFS, который проходит по сетке и возвращает путь от определенной начальной ячейки к любой ячейке, которая поддерживает некоторое условие остановки.Допустимые ходы вверх, вниз, влево, вправо.Я хочу изменить его, чтобы он возвращал все оптимальные (кратчайшие пути, то есть они находятся на одном уровне в поиске BFS), а не только первый найденный путь.Как я могу изменить его элегантным способом?

В моей реализации я выполняю поиск во всех ячейках, пока не попаду в ячейку, содержащую 2, и при этом избегаю ячеек, содержащих 4. Вот мой код: 

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if grid[y][x] == 2:
            return path
        for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
            if 0 <= x2 < len(grid[0]) and 0 <= y2 < len(grid) and  grid[y2][x2] != 4 and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

1 Ответ

0 голосов
/ 22 декабря 2018

Слишком долго для комментария, поэтому ставьте в качестве ответа.Я не проверял модификацию, но вот что я хотел бы сделать: 

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])

    # this contains all the paths found
    found_paths = []

    # search flag recording the shortest distance
    min_path_length = None

    while queue:
        path = queue.popleft()

        # check if we already passed the min_path_length's level
        if min_path_length is not None and min_path_length < len(path):
            break

        x, y = path[-1]
        if grid[y][x] == 2:
            # check if this is the first encounter of min_path
            if min_path_length is None: min_path_length = len(path)

            # we can double check len(path) == min_path_length before adding path
            # but that wouldn't be needed if this implementation is correct
            found_paths.append(path)

        for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
            if 0 <= x2 < len(grid[0]) and 0 <= y2 < len(grid) and  grid[y2][x2] != 4 and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

    return found_paths
...