Оптимальное решение для: всех возможных ациклических путей в задаче о графах.

Я имею дело с неориентированным графом. Мне нужно найти все возможные ациклические пути в графе:

with G(V,E)
find all subsets of V that are acyclic paths

Я использую либо python scipy, либо matlab - в зависимости от того, что подходит. Есть ли умное решение для этого?

Я пытаюсь добиться этого с помощью поиска в ширину (см. вики)

У меня также есть этот набор инструментов в Matlab: http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox, но, похоже, для моей проблемы нет простого решения.

PS. На практике проблема формулируется так: Задача проектирования транзитной сети: найти такую ​​транспортную сеть, которая минимизирует затраты на пассажиров и операторов (т. е. оптимальную сеть метро для городской местности).

Заранее спасибо Рафаль


scipy matlab graph graph-theory
person Intelligent-Infrastructure    schedule 20.01.2011    source источник
comment
Было бы хорошо принять некоторые ответы   -  person ThomasMcLeod    schedule 24.01.2011

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, что проблема, указанная в вашем PS, может быть проблемой NP. Если это так, то есть простые решения только для графов с очень ограниченным числом узлов (N ~ ‹= 20). Другие решения будут приближенными, дающими начало только локальным оптимумам. Решение вашей проблемы, как указано в вопросе, будет заключаться в том, чтобы просто вычислить все перестановки порядков узлов. Опять же, это станет невыполнимым с вычислительной точки зрения при сравнительно небольшом количестве узлов (возможно, выше 20, но не намного).

person Chris Walton    schedule 20.01.2011
comment
Поскольку мой граф является разреженным графом, я не думаю, что результат будет близок ко всем перестановкам. Моя структура графа скорее похожа на дерево. - person Intelligent-Infrastructure; 20.01.2011
comment
ОК - извините, я не могу быть более полезным. - person Chris Walton; 21.01.2011

arrow_upward
0
arrow_downward

Вам нужны только кратчайшие пути между всеми парами вершин или действительно все пути?

person Tiago Peixoto    schedule 21.01.2011
comment
Результатом расчета будет область для задачи оптимизации. Чтобы убедиться, что найдено оптимальное решение, мне нужно получить все возможные пути, а не только самый короткий. - person Intelligent-Infrastructure; 24.01.2011
comment
Здесь есть соответствующее обсуждение: mathoverflow .net/questions/18603/ . Я думаю, что в целом вы будете вынуждены провести тщательный поиск. - person Tiago Peixoto; 27.01.2011