Все пары все пути на графике

Question

Возможно, это проблема без оптимального решения.Предположим, у меня есть ориентированный граф, я понятия не имею, есть ли у него циклы или нет (обнаружение циклов будет одним из аспектов этой проблемы).Учитывая набор вершин (возможно, миллионы вершин), мне нужно сосчитать все различные пути (пути без повторяющихся вершин) между всеми уникальными парами данного графа.Как бы я решил эту ситуацию?

Давайте рассмотрим метод грубой силы, чтобы сделать это:

• Вычислить все возможные пары из графика.

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

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

Могут ли люди указать, что из этого может пойти не так?Давайте подумаем о проблеме таким образом, каковы вычислительные проблемы, связанные с поиском всех отличных путей между всеми городами планеты, и если кто-то даже попытается решить эту проблему, с чего начать?

Править: Некоторые из представленных алгоритмов дают результаты за O (n!) Факториальное время.Это несколько сложное вычисление для одной машины с ограниченными ресурсами для обработки.Кто-нибудь знает методы сокращения карты, чтобы разбить проблему обхода графа на меньшие куски?

Answer 1

Обобщение Флойд-Варшалла, которое получает грубое приближение путей, таково:

 procedure FloydWarshall ()
    for k := 1 to n
       for i := 1 to n
          for j := 1 to n
             path[i][j] = path[i][j] + path[i][k]*path[k][j] 

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

Таким образом, разбейте граф на n произвольных матриц суб-смежности размера kxk, вычислите выше для каждой из них.Теперь у вас есть количество путей и вы начинаете объединять подматрицы, пересчитывая часть вышеупомянутого в объединенную матрицу.Т.е. нам нужно только пересчитать n / 2 значения для k при рекомбинации.Я нашел это, которое выглядит как похожее направление http://theory.stanford.edu/~oldham/publications/generalized/asgsp.pdf.

Answer 2

Думали ли вы, сколько таких путей может существовать?

В таком графе с V вершинами у вас есть около V ^ 2 разных пар. Давайте представим наихудший сценарий, когда у вас есть полный граф (тот, где существуют ребра между каждой парой). У путей может быть где угодно от 1 ребра до ребер V-1, потому что вы не допускаете дублирование вершин в пути.

Между каждой парой вершин:

1. Существует только один путь с 1 ребром;
2. Существуют пути V-2 с 2 ребрами: с использованием любой промежуточной вершины, которая не является исходной или конечной;
3. Существуют (V-2) (V-3) пути с 3 ребрами: используются любые две разные промежуточные вершины;
4. Есть (V-2) (V-3) (V-4) пути с 4 ребрами;
5. Есть пути prod {k = 1 -> n-1} (V-k-1) с n ребрами.

Учитывая это, мы знаем, что существует не более V ^ 2 * sum {i = 1 -> V-1} (prod {k = 1 -> i-1} (Vk-1)) общих путей для граф с V вершинами.

Таким образом, общее количество путей равно P (V) = V ^ 2 * sum {i = 1 -> V-1} (prod {k = 1 -> i-1} (Vk-1)) = V ^ 2 * sum {i = 1 -> V-1} (O (V ^ V)) = O (V ^ 3 * V ^ V) = O (V!).

Теперь представьте себе идеальный мир, в котором вы можете вычислять каждый путь за постоянное время. Ваш алгоритм потребует O (1 * V!) = O (V!) Времени для запуска, что нецелесообразно.

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

Answer 3

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