Динамическое программирование (Динамическое планирование), страница 2

Динамическое программирование

Алгоритм Уоршалла. Основная особенность алгоритма заключается в том, что можно вычислить все элементы каждой матрицы R(k) на основании ее непосредственного предшественника R(k-1). Пусть элемент на пересечении i-ой строки и j-го столбца матрицы R(k) равен 1. Это значит, что существует путь из i-ой вершины в j-ую вершину, в котором все промежуточные вершины имеют номера не выше k. Что касается такого пути, то возможны две ситуации. Первая: список промежуточных вершин не содержит k-ую. Тогда соответствующий элемент в матрице R(k-1) также равен 1. Вторая: путь содержит среди прочих k-ую промежуточную вершину.

Динамическое программирование

• Алгоритм Уоршалла.
• Это означает, что существует путь из i-ой в k-ую вершину такой, что все промежуточные вершины в нем имеют номера не больше, чем k-1 и существует путь из k-ой в j-ую вершину такой, что все промежуточные вершины имеют номера не больше, чем k-1. Таким образом, в матрице R(k-1) на соответствующих местах стоят 1. Истинно утверждение и обратное к данному. Отсюда вытекает следующее рекуррентное правило:
• Если элемент равен 1 в R(k-1), то он остается равен 1 и в R(k).
• Если элемент равен 0 в R(k-1), то он становится равным 1 в R(k), если равны 1 элементы с индексами (i,k) и (k,j) в R(k-1).

Динамическое программирование

Алгоритм Уоршалла. Пример.

a

b

c

d

Динамическое программирование

Алгоритм Уоршалла. a b c d 1 новый путь a 0 1 0 0 R(0) b 0 0 0 1 c 0 0 0 0 d 1 0 1 0 i = 4, j = 2, k = 1 a b c d 2 новых пути a 0 1 0 0 i = 1, j = 4, k = 2 R(1) b 0 0 0 1 c 0 0 0 0 d 1 1 1 0 i = 4, j = 4, k = 2

Динамическое программирование

Алгоритм Уоршалла. a b c d нет новых путей a 0 1 0 1 k ≤ 3 R(2) b 0 0 0 1 c 0 0 0 0 d 1 1 1 1 a b c d 5 новых путей a 0 1 0 1 i = 1, j = 1,3, k ≤ 4 R(3) b 0 0 0 1 i = 2, j = 1,2,3, k ≤ 4 c 0 0 0 0 d 1 1 1 1

Динамическое программирование

Алгоритм Уоршалла. a b c d a 1 1 1 1 R(4) b 1 1 1 1 c 0 0 0 0 d 1 1 1 1 Временная эффективность алгоритма Θ(n³). Можно не использовать отдельные матрицы для промежуточных результатов алгоритма.

Динамическое программирование

Алгоритм Уоршалла. Warshall (A[n,n]) Входные данные: Матрица смежности A графа с n вершинами. Выходные данные: Матрица транзитивного замыкания графа. R(0)ij = Aij for k = 1 to n do for i = 1 to n do for j = 1 to n do R(k)[i,j]= R(k-1)[i,j]||(R(k-1)[i,k]&&R(k-1)[k,j]) return R(n)[n,n]

Динамическое программирование

Алгоритм Уоршалла. void warshall(int A[][5],int T[][5],int n) { int i,j,k; for (i=0;i<n;i++) // P(0) = A for (j=0;j<n;j++) T[i][j] = A[i][j]; for (k=0;k<n;k++) // Алгоритм Уоршалла for (i=0;i<n;i++) for (j=0;j<n;j++) T[i][j] =T[i][j] || (T[i][k] && T[k][j]); }

Динамическое программирование

Алгоритм Флойда. Задача поиска кратчайших путей между всеми парами вершин состоит в поиске для данного взвешенного связного графа (ориентированного или неориентированного) расстояний от каждой вершины до всех других вершин. Для записи длин кратчайших путей удобно воспользоваться матрицей D размером n*n, которая называется матрицей расстояний (distance matrix).

Динамическое программирование

Алгоритм Флойда. Алгоритм Флойда вычисляет матрицу расстояний взвешенного графа с n вершинами посредством построения последовательности D(0), … , D(k-1), D(k), … , D(n) Рекуррентное соотношение d(k)ij = min {d(k-1)ij, d(k-1)ik + d(k-1)kj} для k≥1 d(0)ij = wij.

Динамическое программирование

Алгоритм Флойда. Элемент d(k)ij равен длине кратчайшего пути среди всех путей из i-ой к j-ой вершине, в которых промежуточные вершины (если таковые есть) не могут иметь номера, превышающие k. Как и в алгоритме Уоршалла, мы можем вычислить все элементы каждой матрицы D(k) на основании информации об элементах предшествующей ей матрицы D(k-1). Каждый из путей состоит из пути от i-ой до k-ой вершины, причем все промежуточные вершины имеют номера не выше k-1, и пути от k-ой до i-ой вершины, у которой все промежуточные вершины также имеют номера не выше k-1.

Динамическое программирование

Алгоритм Флойда. Пример.

2

a

b

7

6

3

c

d

1

Динамическое программирование

Алгоритм Флойда. Пример. a b c d a 0 ∞ 3 ∞ D(0) b 2 0 ∞ ∞ k = 1 c ∞ 7 0 1 d 6 ∞ ∞ 0

Динамическое программирование

Алгоритм Флойда. Пример. a b c d a 0 ∞ 3 ∞ D(1) b 2 0 5 ∞ k ≤ 2 c ∞ 7 0 1 d 6 ∞ 9 0

Динамическое программирование

Алгоритм Флойда. Пример. a b c d a 0 ∞ 3 ∞ D(2) b 2 0 5 ∞ k ≤ 3 c 9 7 0 1 d 6 ∞ 9 0

Динамическое программирование