Поиск в ширину по всем путям

Прежде всего, спасибо за внимание к этому вопросу.

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

Вот мой код BFS:

def makePath(predecessors, last):
    return makePath(predecessors, predecessors[last]) + [last] if last else []

def BFS1b(node, goal):
    Q = [node]
    predecessor = {node:None}

    while Q:
        current = Q.pop(0)
        if current[0] == goal:
            return makePath(predecessor, goal)

        for subnode in graph[current[0]][2:]:
            if subnode[0] not in predecessor:
                predecessor[subnode[0]] = current[0]
                Q.append(subnode[0])

Концептуальный толчок в правильном направлении будет принят с благодарностью.

tl;dr Как мне использовать BFS для поиска всех путей между двумя узлами?

Вот график, так как я не знаю, как ответить на вопрос Джеффа Маркадо.

graph = {   'A':[366, 3,    ('Z',   75 ), ('T', 118), ('S', 140)],
            'Z':[374, 2,    ('A',   75 ), ('O', 71 )],
            'T':[329, 2,    ('A',   118), ('L', 111)],
            'L':[244, 2,    ('T',   111), ('M', 70 )],
            'M':[241, 2,    ('L',   70 ), ('D', 75 )],
            'D':[242, 2,    ('M',   75 ), ('C', 120)],
            'C':[160, 3,    ('D',   120), ('R', 146), ('P', 138)],
            'R':[193, 3,    ('C',   146), ('P', 97 ), ('S', 80 )],
            'S':[253, 4,    ('R',   80 ), ('F', 99 ), ('O', 151), ('A', 140)],
            'O':[380, 2,    ('S',   151), ('Z', 71 )],
            'P':[100, 3,    ('C',   138), ('R', 97 ), ('B', 101)],
            'F':[176, 2,    ('S',   99 ), ('B', 211)],
            'B':[  0, 4,    ('P',   101), ('F', 211), ('G', 90 ), ('U', 85 )],
            'G':[ 77, 1,    ('B',   90 )],
            'U':[ 80, 3,    ('B',   85 ), ('H', 98 ), ('V', 142)],
            'H':[151, 2,    ('U',   98 ), ('E', 86 )],
            'E':[161, 1,    ('H',   86 )],
            'V':[199, 2,    ('U',   142), ('I', 92 )],
            'I':[226, 2,    ('V',   92 ), ('N', 87 )],
            'N':[243, 1,    ('I',   87 )],
            'W':[400, 1,    ('X',   100)],
            'X':[400, 1,    ('W',   100)],}

python breadth-first-search
person Amndeep7    schedule 31.10.2012    source источник
comment
Являются ли эти графы ациклическими? Режиссер? Деревья с корнями?   -  person Jeff Mercado    schedule 01.11.2012
comment
@JeffMercado Мы еще не рассмотрели эти различия, я показал график, который мы должны использовать, если это поможет.   -  person Amndeep7    schedule 01.11.2012
comment
Вам нужно разделить работу на отдельные функции. Я бы создал функции для получения следующих узлов, удаления ребер, которые вы израсходовали, и возврата путей.   -  person kreativitea    schedule 01.11.2012
comment
@ Amndeep7: пожалуйста, прочитайте вики-тег домашнего задания. Если это домашнее задание или вам нужны только указания, а не код, укажите это в своем вопросе. Не используйте тег домашнего задания.   -  person Mat    schedule 01.11.2012
comment
@Mat: Спасибо, что сообщили мне о состоянии тега домашнего задания, я позабочусь о том, чтобы больше его не использовать.   -  person Amndeep7    schedule 01.11.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

Что касается ядра алгоритма, имейте в виду, что поиск BFS будет исследовать не один путь за раз, а все. Таким образом, вы не можете просто сохранить один узел в своей очереди, а скорее путь.

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

Наконец, когда в очереди больше нет неполных путей (== очередь пуста), вернуть список решений.

person Maxime Chéramy    schedule 01.11.2012
comment
Я намеренно дал указания только потому, что это школьное задание. Изменения по сравнению с исходным кодом небольшие (удалить предшественника, использовать пути в очереди, удалить makePath, использовать список для хранения решений). - person Maxime Chéramy; 01.11.2012
comment
Что помогло, так это использование путей в очереди - я застрял, так как не мог найти способ отслеживать отдельные пути. Спасибо за вашу помощь. - person Amndeep7; 01.11.2012