Кратчайший путь в сетке с использованием BFS - PullRequest
Новая
       82

Кратчайший путь в сетке с использованием BFS

0 голосов
/ 23 марта 2019

Сетка состоит из следующих элементов как список списков Python 

g = [
    ['1', '1', '1', '1', '1'],
    ['S', '1', 'X', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['X', '1', '1', 'E', '1'],
    ['1', '1', '1', '1', 'X']
]

S указывает начало, E обозначает конец.

1 указывает разрешенные пути, X не разрешенные пути

Простой код обхода BFS: 

def find_path_bfs(s, e, grid):
    queue = list()
    path = list()
    queue.append(s)

    while len(queue) > 0:
        node = queue.pop(0)
        path.append(node)
        mark_visited(node, v)

        if node == e:
            break

        adj_nodes = get_neighbors(node, grid)
        for item in adj_nodes:
            if is_visited(item, v) is False:
                queue.append(item)

    return path

Насколько я могу судить, алгоритм работает правильно со следующим выводом 

[(1, 0), (1, 1), (2, 0), (0, 0), (2, 1), (0, 1), (2, 1), (0, 1), (2, 2), (3, 1), (0, 2), (2, 2), (3, 1), (0, 2), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 4), (3, 3)]

Каждый кортеж вСписок представляет индексы для узла в исходном графике.

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

1 Ответ

1 голос
/ 23 марта 2019

Чтобы получить кратчайший путь, вы также должны сохранить путь к текущему узлу в своей очереди, поэтому формат элемента очереди будет: 

(node, path_to_this_node)

Модифицированный код: 

def find_path_bfs(s, e, grid):
    queue = [(s, [])]  # start point, empty path

    while len(queue) > 0:
        node, path = queue.pop(0)
        path.append(node)
        mark_visited(node, v)

        if node == e:
            return path

        adj_nodes = get_neighbors(node, grid)
        for item in adj_nodes:
            if not is_visited(item, v):
                queue.append((item, path[:]))

    return None  # no path found
...