Блог

У меня есть неориентированный невзвешенный граф с N вершинами, пронумерованными от 1 до N. И мне нужно найти количество способов длины K, чтобы вернуться из первой вершины обратно в саму себя. В течение этого пути разрешается несколько раз возвращаться к первой (или любой другой) вершине. Одно из возможных решений состоит в том, чтобы взять матрицу смежности, найти K-ю степень этой матрицы, а затем верхний левый элемент результирующей матрицы будет ответом на проблему. Временная сложность этого метода составляет O(N^3 * log(K)). Но есть ли более быстрый подход к этой проблеме?

Короткий ответ: Да, вы всегда можете сделать лучше, чем O(N^3 log K) .

Длинный ответ: Сложность самого быстрого подхода зависит от того, насколько велик K, и, в меньшей степени, от текущего представления вашего графика и количества ребер в графике. Конкретная терминология для этой проблемы — «подсчет закрытых прогулок».

Маленький К

Используйте динамическое программирование. Для данной начальной вершины x мы имеем 2-мерное состояние DP.

Пусть DP[ y ][ i] — количество переходов длины i от нашей начальной вершины до y. Тогда DP[ y ][ 1 ] равно 1, если y примыкает к нашей начальной вершине, или 0 в противном случае. Рекуррентное соотношение для i > 1 таково: DP[ y ][ i] — сумма по всем соседям w из y (DP[ w ][ i- 1 ])

Тогда ваш ответ будет DP[ K ][ 1 ].

Короткий код Python для этого, предполагающий, что график представляет собой представление списка смежности:

 dp = [[0 for _ in range(N   1)] for _ in range(K   1)]

for neighbor in graph[1]:
    dp[1][neighbor] = 1

for walk_length in range(2, K   1):
    for vertex in range(1, N   1):
        for neighbor in graph[vertex]:
            dp[walk_length][neighbor]  = dp[walk_length - 1][vertex]

print(dp[K][1])
 

Временная сложность такова O(K * (N E)) , где E-количество ребер. Дополнительная сложность пространства заключается O(NK) в том , что его можно уменьшить O(N) с небольшим усилием. Если ваш график плотный, то в худшем |E| = O(N^2) случае так оно и есть O(K * N * N) ; если ваш график разрежен , как дерево, то так оно и есть O(K * N) . Преобразование между матрицей смежности и списками смежности является аддитивным фактором O(N^2) .

Большой К

Насколько мне удалось найти, лучший ответ (с точки зрения сложности) для большого K-это использовать тактику, аналогичную возведению в степень матрицы смежности, которую вы предложили. Такой подход верен, но мы можем быть немного умнее.

Напомним, что матрица смежности невзвешенного неориентированного графа является реальной симметричной матрицей и, следовательно, она диагонализуема. Пусть матрица смежности равна A и имеет спектральное разложение как A = P * D * (P^-1), где D — диагональная матрица. Затем мы находим верхний левый элемент A^K = P * (D^K) * (P^-1), для которого требуется N экспонент отдельных собственных значений в K-й степени с последующим 2N умножениями и сложениями.

Поскольку размер собственных значений ограничен максимальной степенью, или O(N) , доминирующий член определяется стоимостью вычисления x^K для числа x с O(log N) цифрами. Определение временной сложности здесь сложно: мы должны начать говорить о вычислительных моделях и стоимости умножения целых чисел. Ваша O(N^3 log K) привязка работает, если мы говорим о модели вычислений со словесной оперативной памятью или модели, в которой машинные слова достаточно велики, чтобы обрабатывать выходные данные. Это также работает в более общем плане, если вы хотите получить ответ только по модулю некоторого фиксированного числа. В противном случае, если K сколь угодно велико, наши N степеней собственных значений могут иметь по O(K) битов, поэтому этот последний шаг может занять O( K * N log log N) время, что все равно более эффективно, чем исходное полное матричное возведение в степень (что, по крайней мере O(N^2 * K^2) , в этом случае).

Сложность разложения матрицы тесно связана со сложностью умножения матрицы, что является открытой проблемой. Это между N^2 и N^(2,373), но вопрос теоретически оптимальной сложности лучше всего решать в вопросах математического обмена, подобных этому, и обычно не имеет отношения к практическим задачам.