dynamic-programming
Решение проблем графа с использованием динамического программирования

Алгоритм Флойда-Варшалла

Алгоритм Флойда-Варшалла заключается в поиске кратчайших путей в взвешенном графе с положительными или отрицательными весами ребер. Однократное выполнение алгоритма найдет длины (суммированные веса) кратчайших путей между всеми парами вершин. С небольшим изменением он может печатать кратчайший путь и может обнаруживать отрицательные циклы в графике. Floyd-Warshall - это алгоритм динамического программирования.

Давайте посмотрим на пример. Мы будем применять алгоритм Флойда-Варшалла на этом графике:

Первое, что мы делаем, - взять две двумерные матрицы. Это матрицы смежности . Размер матриц будет полным числом вершин. Для нашего графика возьмем 4 * 4 матрицы. Матрица расстояний будет хранить минимальное расстояние, найденное до сих пор между двумя вершинами. Сначала для ребер, если есть ребро между uv и расстояние / вес w , мы будем хранить: distance[u][v] = w . Для всех ребер, которые не существуют, мы собираемся положить бесконечность . Матрица пути предназначена для регенерации минимального расстояния между двумя вершинами. Поэтому, если есть путь между u и v , мы собираемся поместить path[u][v] = u . Это означает, что лучший способ прийти к вершине-v из вершины-u - использовать ребро, соединяющее v с u . Если между двумя вершинами нет пути, мы собираемся указать N, указав, что пути нет. Две таблицы для нашего графика будут выглядеть так:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Поскольку нет петли, диагонали устанавливаются N. И расстояние от самой вершины равно 0 .

Чтобы применить алгоритм Флойда-Варшалла, мы будем выбирать среднюю вершину k . Тогда для каждой вершины i мы проверим, можем ли мы перейти от i к k, а затем к к j , где j - другая вершина и минимизирующая стоимость перехода от i к j . Если текущее расстояние [i] [j] больше расстояния [i] [k] + расстояние [k] [j] , мы собираемся положить расстояние [i] [j] равным суммированию этих двух расстояний , И путь [i] [j] будет установлен в путь [k] [j] , так как лучше перейти от i к k , а затем к к j . Все вершины будут выбраны как k . У нас будет 3 вложенных цикла: для k, идущих от 1 до 4, я иду от 1 до 4 и j идет от 1 до 4. Мы собираемся проверить:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Итак, что мы в основном проверяем, для каждой пары вершин мы получаем более короткое расстояние, пройдя через другую вершину? Общее количество операций для нашего графика будет 4 * 4 * 4 = 64 . Это означает, что мы будем делать эту проверку 64 раза. Давайте посмотрим на некоторые из них:

Когда k = 1 , i = 2 и j = 3 , расстояние [i] [j] равно -2 , что не больше расстояния [i] [k] + расстояние [k] [j] = -2 + 0 = -2 . Таким образом, он останется неизменным. Опять же, когда k = 1 , i = 4 и j = 2 , расстояние [i] [j] = бесконечность , что больше расстояния [i] [k] + расстояние [k] [j] = 1 + 3 = 4 , Таким образом, мы положили расстояние [i] [j] = 4 и положили путь [i] [j] = path [k] [j] = 1 . Это означает, что для перехода от вершины-4 к вершине-2 путь 4-> 1-> 2 короче существующего пути. Так мы заполняем обе матрицы. Расчет для каждого шага показан здесь . После внесения необходимых изменений наши матрицы будут выглядеть так:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Это наша кратчайшая матрица расстояния. Например, кратчайшее расстояние от 1 до 4 равно 3, а кратчайшее расстояние между 4 и 3 равно 2 . Наш псевдокод будет:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Печать пути:

Чтобы напечатать путь, мы проверим матрицу Path . Чтобы напечатать путь от u до v , мы начнем с пути [u] [v] . Мы установим изменение v = path [u] [v], пока не найдем путь [u] [v] = u и не выталкиваем все значения пути [u] [v] в стеке. После нахождения u , мы напечатаем u и начнем выскакивать элементы из стека и печатать их. Это работает, потому что в матрице пути хранится значение вершины, которое имеет самый короткий путь к v из любого другого узла. Псевдокод будет:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Поиск отрицательного краевого цикла:

Чтобы узнать, есть ли отрицательный цикл ребер, нам нужно проверить основную диагональ матрицы расстояния . Если какое-либо значение на диагонали отрицательное, это означает, что на графике есть отрицательный цикл.

Сложность:

Сложность алгоритма Флойда-Варшалла равна O (V³), а сложность пространства: O (V²) .

Минимальная крышка вершин

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

Мы хотим установить стражников по некоторым пунктам. Сторож может охранять все дороги, связанные с точкой. Проблема в том, каково минимальное количество сторожей, необходимых для покрытия всех дорог? Если мы установим сторожей в узлах A , B , H , I и J , мы можем покрыть все дороги.

Это наше оптимальное решение. Нам нужно по крайней мере 5 стражей, чтобы охранять весь город. Как это определить?

Сначала нам нужно понять, что это NP-трудная проблема, то есть проблема не имеет решения полиномиального времени. Но если граф был деревом , это означает, что если у него были (n-1) узлы, где n - число ребер, и на графике нет цикла, мы можем решить его с помощью динамического программирования.

Чтобы построить решение DP, нам нужно выполнить две стратегии:

1. Если в узле нет сторожа, все подключенные к нему узлы должны иметь сторожа, или все дороги не будут покрыты. Если u и v связаны, а u не имеет какого-либо сторожа, то v должен иметь сторожа.
2. Если в узле есть сторож, другой подключенный к нему узел может иметь или не иметь сторожа. Это означает, что нет необходимости иметь сторожа, но это может быть полезно. Если u и v связаны, а u имеет сторожа, мы проверим и найдем, что выгодно для нас:
   • Установка сторожа в v .
   • Не устанавливать сторожа в v .

Давайте определим рекурсивную функцию с состоянием, являющимся текущим узлом, в котором мы находимся, и имеет ли он сторожа или нет. Вот:

F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.

Функция вернет количество сторожа в оставшихся узлах.

Возьмем дерево примеров:

Мы можем легко сказать, что если мы не ставим сторожа на узел- А , нам придется ставить стражей на узлы- B , C и D. Мы можем вывести:

F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0

Он возвращает нам необходимое количество сторожей, если мы не ставим сторожа в узел- A . Мы добавили 0 в конце, потому что мы не установили какого-либо сторожа в нашем текущем узле.

Теперь F(A,1) означает, что мы устанавливаем сторожа в узел- A . Для этого мы можем либо установить сторожей во всех подключенных узлах, либо нет. Мы возьмем тот, который предоставляет нам минимальное количество сторожей.

F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1

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

Одна вещь, мы должны быть осторожны, то есть, как только мы перейдем к дочернему узлу, мы никогда не оглянемся на родительский узел. Из приведенного выше примера мы отправились в B из A , поэтому родительский [B] = A. Поэтому мы не вернемся к A с B.

Чтобы определить базовый случай, мы можем заметить, что если из узла мы не можем перейти на какой-либо другой новый узел, мы вернем 1, если в нашем текущем узле есть сторож, 0, если в нашем текущем узел.

Лучше иметь список смежности для нашего дерева. Пусть список обозначается ребром . У нас будет массив dp [n] [2] , где n обозначает количество узлов для хранения вычисленных значений и инициализирует его с помощью -1 . У нас также будет родительский [n] массив, чтобы обозначить родительскую и дочернюю связь между узлами. Наш псевдокод будет выглядеть так:

Procedure f(u, isGuarded):
if edge[u].size is equal to 0                    //node doesn't have any new edge
    Return isGuarded
else if dp[u][isGuarded] is not equal to -1      //already calculated
    Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
    v := edge[u][i]
    if v is not equal to parent[u]               //not a parent
        parent[v] := u
        if isGuarded equals to 0                 //not guarded, must set a watchman
            sum := sum + f(v,1)
        else                                     //guarded, check both
            sum := sum + min(f(v,1), f(v,0)
        end if
    end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]

Если мы обозначим node- A как root, мы будем называть функцию: min(f(A,1), f(A,0)) . Это означает, что мы также проверим, оптимально ли установить сторожа в корневом узле или нет. Это наше решение DP. Эта проблема также может быть решена с использованием алгоритма максимального соответствия или максимального потока.