Алгоритм Флойда. Пример. a b c d a 0 10 3 4 D(3) b 2 0 5 6 k ≤ 4 c 9 7 0 1 d 6 16 9 0
Динамическое программирование
Алгоритм Флойда. Пример. a b c d a 0 10 3 4 D(4) b 2 0 5 6 c 7 7 0 1 d 6 16 9 0 Временная эффективность алгоритма Флойда – кубическая, как и временная эффективность алгоритма Уоршалла.
Динамическое программирование
Алгоритм Флойда. Floyd (W[n,n]) Входные данные: Весовая матрица W графа с n вершинами. Выходные данные: Матрица длин кратчайших путей. D(0)ij = Wij for k = 1 to n do for i = 1 to n do for j = 1 to n do D(k)[i,j] = min{D(k-1)[i,j], (D(k-1)[i,k]+D(k-1)[k,j])) return D(n)[n,n]
Динамическое программирование
Алгоритм Флойда. void floyd(int *a,int *p,int fn) { int i,j,k; for (i=0;i<fn;i++) for (j=0;j<fn;j++) if (a[i*fn+j] == 0) p[i*n+j] = 10000; else p[i*fn+j] = a[i*fn+j]; for (k=0;k<fn;k++) for (i=0;i<fn;i++) for (j=0;j<fn;j++) p[i*n+j] =(p[i*fn+j] <= (p[i*fn+k] + p[k*fn+j])) ? p[i*n+j] : (p[i*fn+k]+p[k*fn+j]); }
Динамическое программирование
Пример. Задача о рюкзаке. Даны n предметов с известными весами w1,…,wn и стоимостями v1,…,vn и рюкзак вместимости W. Требуется найти наиболее ценное подмножество предметов, помещающихся в рюкзаке. Для разработки алгоритма динамического программирования мы должны вывести рекуррентное соотношение, которое выражает решение экземпляра задачи о рюкзаке через решение его меньших подэкземпляров. Рассмотрим экземпляр, определяемый первыми i предметами, 1≤i≤n, весами w1,…,wi, стоимостями v1,…,vi и емкостью рюкзака 1≤j≤W.
Динамическое программирование
Динамическое программирование
Пример. Задача о рюкзаке. 2. Среди подмножеств, которые включают i-ый предмет (следовательно, j-wi≥0), оптимальное подмножество составляется из этого предмета и оптимального подмножества первых i-1 предметов, которое размещается в рюкзаке емкостью j-wi. Стоимость такого оптимального подмножества равна vi+V(i-1, j-wi). Таким образом, стоимость оптимального решения среди всех допустимых подмножеств из первых i предметов представляет собой большее из этих двух значений.
Динамическое программирование
Пример. Задача о рюкзаке. Конечно, если i-ый предмет не помещается в рюкзак, стоимость оптимального подмножества, выбранного из первых i предметов, оказывается той же, что и стоимость оптимального подмножества, выбранного из первых i-1 предметов. Это наблюдение приводит нас к следующему рекуррентному соотношению: max{V(i-1,j), vj+V(i-1,j-wi)}, если j-wi≥0, V(i,j) = { V(i-1,j), если j-wi<0.
Динамическое программирование
Пример. Задача о рюкзаке. Начальные условия удобно определить следующим образом: V(0,j)=0 при j≥0, и V(i,0)=0 при i≥0. Наша цель состоит в том, чтобы найти V(n,W) – максимальную стоимость подмножества из n предметов, которое помещается в рюкзак емкостью W, и само это подмножество. Строим таблицу. При i,j>0 для вычисления элемента таблицы на пересечении i-ой строки и j-го столбца V(i,j) мы берем значение элемента в предыдущей строке и том же столбце и сумму значений vi и элемента в предыдущей строке и столбце, отстоящем на wi столбцов слева, и находим максимальное из них.
Динамическое программирование
Пример. Задача о рюкзаке. Таблица для решения задачи о рюкзаке методом динамического программирования 0 … j-wi … j … W 0 0 … 0 … 0 … 0 … ………………………............................... wi,vi i-1 0 … V(i-1,j-wi) … V(i-1,j) ………. i 0 … … … V(i,j) ………. … …………………………………………… n 0 …………………Целевое значение
Динамическое программирование
Пример. Задача о рюкзаке. Рассмотрим экземпляр задачи, определяемый следующими данными. Емкость рюкзака W=5. Предмет Вес Стоимость 1 2 12 2 1 10 3 3 20 4 2 15
Динамическое программирование
Пример. Задача о рюкзаке. Таблица динамического программирования Емкость j i 0 1 2 3 4 5 0 0 0 0 0 0 0 w1=2, v1=12 1 0 0 12 12 12 12 w2=1, v2=10 2 0 10 12 22 22 22 w3=3, v3=20 3 0 10 12 22 30 32 w4=2, v4=15 4 0 10 15 25 30 37
Динамическое программирование
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.