Блог

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

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

У меня нет никакого завершенного фрагмента кода, который можно было бы предоставить здесь, потому что я не уверен, как:

• сохраните результаты (наряду с A-> B-> C-> мы также должны хранить A-> B и A-> B-> C);
• представить граф (орграф? список кортежей?);
• сколько рекурсий использовать (работать с каждой смежной вершиной?).

Как я могу найти все возможные пути из одной заданной исходной вершины в ориентированном циклическом графе в Erlang?

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

UPD2: Спасибо за комментарии, заставляющие задуматься! Да, мне нужно найти все простые пути, которые не имеют циклов от одной исходной вершины до всех остальных.

В графе, подобном этому:

с исходной вершиной A алгоритм должен найти следующие пути:

• A,B
• A, B, C
• A, B, C, D
• A, D
• A, D, C
• A, D, C, B

Следующий код выполняет эту работу, но он непригоден для использования с графами, имеющими более 20 вершин (я предполагаю, что что-то не так с рекурсией — занимает слишком много памяти, никогда не заканчивается):

 dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Resu<

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.
  

UPD3:

Проблема в том, что обычный алгоритм поиска в глубину сначала перейдет к одному из путей to: (A, B, C, D) или (A, D, C, B) и никогда не пойдет по второму пути.

В любом случае это будет единственный путь — например, когда обычный DFS возвращается из (A, B, C, D), он возвращается к A и проверяет, посещен ли D (второй сосед A). И поскольку обычная DFS поддерживает глобальное состояние для каждой вершины, D будет иметь состояние «посещения».

Итак, мы должны ввести зависящее от рекурсии состояние — если мы вернемся от (A, B, C, D) до A, у нас должно быть (A, B, C, D) в списке результатов, и мы должны иметь D, помеченный как не посещенный, как в самом началеалгоритма.

Я попытался оптимизировать решение для хвостовой рекурсии, но все же время выполнения алгоритма неосуществимо — для прохождения крошечного графа из 16 вершин с 3 ребрами на вершину требуется около 4 секунд:

 dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Resu<

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).
  

Есть идеи запустить это в приемлемое время?

Редактировать: Хорошо, теперь я понимаю, вы хотите найти все простые пути из вершины в ориентированном графе. Итак, как вы поняли, поиск в глубину с возвратом был бы подходящим. Общая идея состоит в том, чтобы перейти к соседу, затем перейти к другому (не к тому, который вы посетили) и продолжать идти, пока не зайдете в тупик. Затем вернитесь к последней вершине, в которой вы были, и выберите другого соседа и т. Д. Вам нужно правильно подобрать нужные биты, но это не должно быть слишком сложно. Например. на каждом шаге вам нужно пометить вершины «исследованными» или «неисследованными» в зависимости от того, посещали ли вы их раньше. Производительность не должна быть проблемой, правильно реализованный алгоритм должен занять, возможно, O (n ^ 2) времени. Итак, я не знаю, что вы делаете неправильно, возможно, вы посещаете слишком много соседей? Например. может быть, вы посещаете соседей, которых вы уже посетили, и проходите циклы или что-то в этом роде.

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

Редактировать: Да, извините, вы правы, стандартный поиск в DFS не будет работать в том виде, в каком он есть, вам нужно немного настроить его, чтобы он возвращался к вершинам, которые он посещал ранее. Таким образом, вам разрешено посещать любые вершины, кроме тех, которые вы уже сохранили в своем текущем пути. Это, конечно, означает, что мое время выполнения было совершенно неправильным, сложность вашего алгоритма будет зашкаливать. Если средняя сложность вашего графика равна d 1, то будет приблизительно d * d * d * … * d = d ^ n возможных путей. Таким образом, даже если каждая вершина имеет только 3 соседних, все равно остается довольно много путей, когда вы получаете более 20 вершин. На самом деле это невозможно обойти, потому что, если вы хотите, чтобы ваша программа выводила все возможные пути, тогда вам действительно придется выводить все d ^ n из них.

Мне интересно знать, нужно ли вам это для конкретной задачи или вы просто пытаетесь запрограммировать это из интереса. Если последнее, вам просто придется довольствоваться небольшими, слабо связанными графами.

Я не понимаю вопроса. Если у меня есть граф G = (V, E) = ({A,B}, {(A,B),(B,A)}), существует бесконечное количество путей от A до B {[A,B], [A,B,A,B], [A, B, A,B, A,B], …}. Как я могу найти все возможные пути к любой вершине в циклическом графе?

Редактировать:

Вы даже пытались вычислить или угадать рост возможных путей для некоторых графиков? Если у вас есть полностью связанный граф, вы получите

• 2 — 1
• 3 — 4
• 4 — 15
• 5 — 64
• 6 — 325
• 7 — 1956
• 8 — 13699
• 9 — 109600
• 10 — 986409
• 11 — 9864100
• 12 — 108505111
• 13 — 1302061344
• 14 — 16926797485
• 15 — 236975164804
• 16 — 3554627472075
• 17 — 56874039553216
• 18 — 966858672404689
• 19 — 17403456103284420
• 20 — 330665665962403999

Вы уверены, что хотите найти все пути для всех узлов? Это означает, что если вы вычисляете один миллион путей за одну секунду, потребуется 10 750 лет, чтобы вычислить все пути ко всем узлам в полностью связном графе с 20 узлами. Это верхняя граница для вашей задачи, поэтому я думаю, что вам это не понравится. Я думаю, вы хотите чего-то еще.

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

Вы можете увидеть пример здесь: некоторые матричные функции Erlang в функции maximise_assignment (комментарии, начинающиеся со строки 191 на сегодняшний день). Опять же, базовый алгоритм там довольно наивный и грубый, но распараллеливание довольно хорошо ускоряет его для многих форм матриц.

Я использовал аналогичный подход в прошлом, чтобы найти количество гамильтоновых путей в графе.