Как мне найти все «длинные» простые ациклические пути в графе?

Допустим, у нас есть полносвязный ориентированный граф G. Вершины [a,b,c]. Между каждой вершиной есть ребра в обоих направлениях.

Учитывая начальную вершину a, я хотел бы пройти по графу во всех направлениях и сохранить путь только тогда, когда я попаду в вершину, которая уже находится на пути.

Итак, функция full_paths(a,G) должна возвращать:

- [{a,b}, {b,c}, {c,d}]
- [{a,b}, {b,d}, {d,c}]
- [{a,c}, {c,b}, {b,d}]
- [{a,c}, {c,d}, {d,b}]
- [{a,d}, {d,c}, {c,b}]
- [{a,d}, {d,b}, {b,c}]

Мне не нужны «неполные» результаты, такие как [{a,b}] или [{a,b}, {b,c}], потому что они уже содержатся в первом результате.

Есть ли другой способ сделать это, кроме создания набора мощности G и фильтрации результатов определенного размера?

Как я могу это рассчитать?

Редактировать: как указал Итан, это можно решить с помощью метода поиска в глубину, но, к сожалению, я не понимаю, как его модифицировать, чтобы он сохранял путь перед возвратом (я использую Ruby Gratr для реализации моего алгоритма)


path graph traversal directed-graph powerset
person skanatek    schedule 11.11.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

person ethan    schedule 11.11.2011
comment
Итан, я думал о dfs, но не понимаю, как точно записывать каждый путь. - person skanatek; 11.11.2011
comment
Посмотрите параметры обратного вызова и пример, приведенный в документации для bfs. . Вы можете использовать обратные вызовы, чтобы отслеживать пройденные ребра и посещенные вершины, чтобы отслеживать каждый путь. - person ethan; 12.11.2011

arrow_upward
1
arrow_downward

Если вы знаете, что ваш граф G полностью связан, то существует N! путей длины N, где N — это количество вершин в графе G. Вы можете легко вычислить его таким образом. У вас есть N возможностей выбора начальной точки, затем для каждой начальной точки вы можете выбрать N-1 вершин в качестве второй вершины на пути и так далее, когда вы можете выбрать только последнюю непосещенную вершину на каждом пути. Итак, у вас есть N*(N-1)*...*2*1 = N! возможных путей. Когда вы не можете выбрать начальную точку, т.е. она задана, это то же самое, что найти пути в графе G' с N-1 вершинами. Все возможные пути представляют собой перестановку набора всех вершин, т.е. в вашем случае все вершины, кроме начальной точки. Когда у вас есть перестановка, вы можете сгенерировать путь:

perm_to_path([A|[B|_]=T]) -> [{A,B}|perm_to_path(T)];
perm_to_path(_) -> [].

самый простой способ генерировать перестановки

permutations([]) -> [];
permutations(L) ->
  [[H|T] || H <- L, T <- permutations(L--[H])].

Итак, в вашем случае:

paths(A, GV) -> [perm_to_path([A|P]) || P <- permutations(GV--[A])].

где GV — список вершин графа G.

Если вам нужна более эффективная версия, вам потребуется немного больше хитрости.

person Hynek -Pichi- Vychodil    schedule 12.11.2011