Вопрос по graph, algorithm, c++, c – График обхода n шагов

7

Имеется простой неориентированный граф, подобный этому:

enter image description here

Начиная с D, A, B или C (V_start) & # x2014; Я должен рассчитать, сколько возможных путей существует от начальной точки (V_start) к начальной точке (V_start) изn шаги, где каждое ребро и вершину можно посещать неограниченное количество раз.

Я думал о том, чтобы сделать первый глубокий поиск, останавливаясь, когдаsteps > n || (steps == n && vertex != V_start)Однако это становится довольно дорого, если, например,n = 1000000, Моя следующая мысль привела меня к объединению DFS с динамическим программированием, однако именно здесь я застрял.

(Это не домашнее задание, просто я застреваю, играя с графиками и алгоритмами ради обучения.)

Как бы я решил это в разумные сроки с большимn?

Тогда существует бесконечное количество путей? aib
@aib: так как длина путей конечна, в некоторых случаях существует только огромное количество комбинаций :) Matthieu M.
Ах, изn шаги. Пропустил это. aib
Можете ли вы использовать ребро более одного раза на одном пути? gabitzish
Да. (Моржовый наполнитель) skinkelynet

Ваш Ответ

2   ответа
20

Создать матрицуnИксn содержит 0 и 1 (1 для ячейкиmat[i][j] если есть путь отi вj). Умножьте эту матрицу на себяk раз (рассмотрим использование быстрого возведения в степень матрицы). Затем в ячейке матрицыmat[i][j] у вас есть количество путей с длинойk начиная сi и заканчивается вj.

NOTE: Быстрое возведение в степень матрицы в основном совпадает с быстрым возведением в степень, просто вместо этого вы умножаете числа, вы умножаете матрицы.

NOTE2: Давайте предположим,n это количество вершин в графе. Тогда алгоритм, который я предлагаю здесь, выполняется во временной сложности O (logk * п3) и имеет сложность памяти O (n2). Вы можете улучшить его немного больше, если используете оптимизированное умножение матриц, как описаноВот, Тогда сложность времени станет O (логk * пlog27).

EDIT По просьбе Антуана я включаю объяснение, почему этот алгоритм действительно работает:

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

Предположим, что пока силаk если я подниму матрицу к властиk У меня вmat[i][j] количество путей с длинойk междуi а такжеj.

Теперь давайте рассмотрим следующий шагk + 1, Очевидно, что каждый путь длиныk + 1 состоит из префикса длиныk и еще один край. Это в основном означает, что пути длиныk + 1 можно рассчитать по (здесь я обозначаю какmat_pow_k матрица возведена вkth power)

num_paths (x, y, k + 1) = суммаi=0i<n mat_pow_k [x] [i] * mat [i] [y]

Снова:n это количество вершин в графе. Это может занять некоторое время, чтобы понять, но в основном исходная матрица имеет 1 в своемmat[i][y] ячейка, только если есть прямой край междуx а такжеy, И мы посчитаем все возможные префиксы такого края, чтобы сформировать путь длиныk + 1.

Однако последнее, что я написал, на самом деле вычислениеk + 1святая силаmat, что доказывает шаг индукции и мое утверждение.

Что такоеn в сумме?
Да, конечно, нет проблем. Начинаю работать над этим.
@ Antoine Готово - я добавил доказательства по индукции, надеюсь, это будет достаточно понятно.
Спасибо вам за отличный ответ.
Можете ли вы добавить детали о том, почему это работает?
2

dynamic programming проблема:

define a f[n][m] to be the number of paths from the starting point to point n in m steps from every point n to its adjacent k, you have formula: f[k][m+1] = f[k][m+1] + f[n][m] in the initialization, all f[n][m] will be 0, but f[starting_point][0] = 1 so you can calculate the final result

псевдокод:

memset(f, 0, sizeof(f));
f[starting_point][0] = 1;
for (int step = 0; step < n; ++step) {
    for (int point = 0; point < point_num; ++point) {
        for (int next_point = 0; next_point < point_num; ++ next_point) {
            if (adjacent[point][next_point]) {
                f[next_point][step+1] += f[point][step];
            }
        }
    }
}
return f[starting_point][n]

Похожие вопросы