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

Question

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

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

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

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

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

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

---

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

На такой диаграмме:

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

• А, Б
• А, Б, В
• А, Б, В, Г
• А, Д
• A, D, C
• A, D, C, B

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

родовое слово

---

< sizesUPD3:

Проблема в том, что обычный алгоритм поиска в глубину сначала будет идти по одному из путей к: (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 как непосещенные, как в самом начале алгоритма.

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

родовое слово

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

Answer 1

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

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

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

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

Answer 2

Я не понимаю вопроса. Если у меня есть граф 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–1740 3456103284420
• 20–330665665962403999

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

Answer 3

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

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

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