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

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

1 голос
/ 11 ноября 2011

Допустим, у нас есть полностью связный ориентированный граф 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 для реализации моего алгоритма)

Ответы [ 2 ]

1 голос
/ 12 ноября 2011

Если вы знаете, что ваш граф 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.

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

1 голос
/ 11 ноября 2011

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

...