'

Динамическое программирование. Основные концепции

Понравилась презентация – покажи это...





Слайд 0

Динамическое программирование. Основные концепции Федор Царев, Андрей Лушников Спецкурс «Олимпиадное программирование» Лекция 4 09.02.2009 Санкт-Петербург, Гимназия 261


Слайд 1

Цель лекции Изучить базовые идеи динамического программирования и простейшие примеры его применения Изучить методы реализации этих алгоритмов на языке программирования Pascal (Delphi)


Слайд 2

Чем не является динамическое программирование Динамическое программирование – не метод составления программ, а метод составления алгоритмов Динамическое программирование не имеет ничего общего с динамической памятью


Слайд 3

Где используется динамическое программирование? Алгоритм обработки графов Алгоритмы обработки строк Биоинформатика Распознавание речи Оптимизация запросов к базам данных Обработка изображений …


Слайд 4

Числа Фибоначчи Пример почти динамического программирования Fib(0) = Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2), n > 1


Слайд 5

Простой способ вычисления function fib(n : longint) : longint; begin if (n < 2) then begin result := 1; exit; end; result := fib(n - 1) + fib(n - 2); end;


Слайд 6

Дерево вычислений Медленно работает – время пропорционально значению числа Фибоначчи, которые растут примерно как 1.6n Много одинаковых поддеревьев


Слайд 7

Метод запоминания ответов После того, как число вычислено надо его запомнить, а не считать заново В массиве логического типа calculated хранится информация о том, вычислено соответствующее число или нет В массиве ans хранится вычисленное число


Слайд 8

Более быстрое вычисление function fib(n : longint) : longint; begin if (n < 2) then begin result := 1; exit; end; if (calculated[n]) then begin result := ans[n]; exit; end; result := fib(n - 1) + fib(n - 2); calculated[n] := true; ans[n] := result; end;


Слайд 9

Ациклический граф вычислений Содержит n вершин Каждое число вычисляется ровно один раз


Слайд 10

Что позволило ускорить вычисление? Перекрывающиеся подзадачи (много одинаковых поддеревьев) Небольшое число различных подзадач (для вычисления Fib(n) – примерно n подзадач) Возможность записывать ответы для подзадач


Слайд 11

Признаки возможности применения ДП Возможность разбиения задачи на подзадачи (метод «разделяй-и-властвуй») Наличие свойства оптимальности для подзадач – оптимальный ответ для большой задачи строится на основе оптимальных ответов для меньших Наличие перекрывающихся подзадач


Слайд 12

Этапы решения задачи методом динамического программирования Разбиение задачи на подзадачи Построение рекуррентной формулы для вычисления значения функции Вычисление значения функции для всех подзадач Восстановление структуры оптимального ответа


Слайд 13

Задача о наибольшей общей подпоследовательности На примере этой задачи будут рассматриваться указанные четыре этапа На базе этой задачи построена программа diff, которая используется в Linux для сравнения файлов Задача имеет приложения в биоинформатике


Слайд 14

Постановка задачи Заданы две строки: a1a2…an и b1b2…bm Необходимо найти строку максимальной длины, которая встречается в обеих заданных строках как подпоследовательность AGCAT GAC GA


Слайд 15

Медленное решение Перебрать все подпоследовательности одной из строк и проверить их вхождение в другую строку Число подпоследовательностей строки длиной n – 2n Поэтому время работы такого решения – O(m2n)


Слайд 16

Разбиение на подзадачи (1) Рассмотрим строки : a1a2…an и b1b2…bm Если последние символы совпадают (an=bm), то их нужно включить в ответ и отбросить Если они различны, то нужно попробовать отбросить только an, а потом только bm


Слайд 17

Разбиение на подзадачи (2) Подзадачами являются задачи такого типа «Найти наибольшую общую подпоследвательность строк a1a2…ai и b1b2…bk» Обозначим ответ (длину последовательности) на эту подзадачу как len[i][k]


Слайд 18

Рекуррентная формула


Слайд 19

Начальные условия len[0][k] = 0 для всех k len[i][0] = 0 для всех i


Слайд 20

Два метода вычисления «Сверху вниз» – рекурсия с запоминанием ответов «Снизу вверх» – заполнение таблицы


Слайд 21

Метод «сверху вниз» Решение больших подзадач начинается до того, как получены ответы для маленьких Маленькие решаются в процессе решения больших


Слайд 22

Программа function calc(i, k : integer) : integer; begin if (calculated[i][k]) then begin result := len[i][k]; exit; end; if (i = 0) or (k = 0) then begin result := 0; exit; end; if (a[i] = b[k]) then begin result := calc(i – 1, k – 1) + 1; end else begin result := max(calc(i – 1, k), calc(i, k – 1)); end; calculated[i][k] := true; len[i][k] := result; end;


Слайд 23

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


Слайд 24

Метод «снизу вверх» Заполняется таблица ответов на подзадачи в порядке возрастания размера подзадачи Когда начинается решение большой подзадачи, меньшие уже решены


Слайд 25

Программа len[0][0] := 0; for i := 1 to n do begin len[i][0] := 0; end; for k := 1 to m do begin len[0][k] := 0; end; for i := 1 to n do begin for k := 1 to m do begin if (a[i] = b[k]) then begin len[i][k] := len[i – 1][k – 1] + 1; end else begin len[i][k] := max(len[i–1][k], len[i][k-1]); end; end; end;


Слайд 26

Преимущества и недостатки Преимущества: Требуется меньше памяти, чем при методе «сверху вниз» и отсутствует рекурсия Быстрее работает в случае, когда необходимо вычислить ответы для всех подзадач Недостатки: Порядок заполнения таблицы не всегда прост (например, может потребоваться заполнять по диагоналям)


Слайд 27

Пример Красный цвет – начальные условия Зеленый цвет – случай ai = bk Желтый цвет – случай ai ? bk


Слайд 28

Восстановление структуры оптимального ответа Верхний путь – GA Нижний путь – AC


Слайд 29

Программа procedure restore(i, k : integer); begin if (i = 0) or (k = 0) then begin exit; end; if (a[i] = b[k]) then begin restore(i – 1, k – 1); write(a[i]); end else begin if (len[i – 1][k] = len[i][k]) then begin restore(i – 1, k); end else begin restore(i, k – 1); end; end; end;


Слайд 30

Как делать в общем случае? Такой метод работает в этой задаче, но не понятно, как его адаптировать к другим Общий метод состоит в том, чтобы запоминать, какой из вариантов в рекуррентной формуле был реализован


Слайд 31

Вычисление функции с запоминанием выбранного варианта for i := 1 to n do begin for k := 1 to m do begin if (a[i] = b[k]) then begin len[i][k] := len[i – 1][k – 1] + 1; back[i][k] := 1; end else begin if (len[i - 1][k] > len[i][k - 1]) then begin len[i][k] := len[i–1][k]; back[i][k] := 2; end else begin len[i][k] := len[i][k - 1]; back[i][k] := 3; end; end; end; end;


Слайд 32

Восстановление ответа procedure restore(i, k : integer); begin if (i = 0) or (k = 0) then begin exit; end; if (back[i][k] = 1) then begin restore(i – 1, k – 1); write(a[i]); end else if (back[i][k] = 2) then begin restore(i – 1, k); end else begin restore(i, k – 1); end; end;


Слайд 33

Упражнение – 1 Путь с максимальной суммой. Задан прямоугольник размером n на m, в каждой клетке которого находится число. За один ход можно сдвинуться вверх или вправо. Необходимо найти путь из левого нижнего угла в правый верхний с максимальной суммой чисел в посещенных клетках


Слайд 34

Упражнение – 2 Число путей. Задан прямоугольник размером n на m, некоторые клетки которого вырезаны. За один ход можно сдвинуться вверх или вправо. Необходимо найти число путей из левого нижнего угла в правый верхний


Слайд 35

Упражнение – 3 Максимальный подпалиндром. Задана строка. Необходимо найти наибольшую по длине подпоследовательность, которая является палиндромом (читается одинаково с обеих сторон)


Слайд 36

Упражнение – 4 Наибольшая возрастающая подпоследовательность. Задана последовательность из n чисел. Необходимо найти ее наибольшую по длине подпоследовательность, числа которой расположены в возрастающем порядке


Слайд 37

Литература Кормен, Лейзерсон, Ривест, Штайн «Алгоритмы. Построение и анализ», глава 15


Слайд 38

Выводы Динамическое программирование – метод составления алгоритмов Оно применимо в случае наличия перекрывающихся подзадач Решение задачи методом ДП состоит из четырех этапов: Разбиение задачи на подзадачи Построение рекуррентной формулы для вычисления значения функции Вычисление значения функции для всех подзадач Восстановление структуры оптимального ответа


Слайд 39

Спасибо за внимание! Вопросы? Комментарии? fedor.tsarev@gmail.com


×

HTML:





Ссылка: