Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Динамическое программирование. Примеры задач
Содержание
- 1. Динамическое программирование. Примеры задач
- 2. Цель лекцииИзучить еще несколько примеров задач, решаемых с помощью динамического программирования, и их решения
- 3. Признаки возможности применения ДПВозможность разбиения задачи на
- 4. Этапы решения задачи методом динамического программированияРазбиение задачи
- 5. Наибольшая возрастающая подпоследовательностьЗадана последовательность чисел a1, a2,
- 6. Перебор?Число различных подпоследовательностей: (2n – 1)Можно применять для n ≤ 20
- 7. Разбиение на подзадачиИдея: найти наибольшую возрастающую подпоследовательность
- 8. Рекуррентная формулаd[i] – длина наибольшей возрастающей подпоследовательности,
- 9. Начальные условияМожно сделать немного прощеСчитаем, что в
- 10. Пример (1)
- 11. Пример (2)
- 12. Пример (3)
- 13. Пример (4)
- 14. Пример (5)
- 15. Пример (6)
- 16. Пример (7)
- 17. Пример (8)
- 18. Пример (9)
- 19. Программаd[0] := 0;for i := 1 to
- 20. Восстановление ответаГде находится длина L наибольшей возрастающей
- 21. Вычисление с сохранением информации для восстановления ответаd[0]
- 22. Восстановление ответаprocedure restore(i : integer);begin if (i > 0) then begin restore(prev[i]); write(a[i]); end;end;
- 23. Пример1 3 4 10 15
- 24. Время работыВремя работы этого алгоритма – O(n2)Можно ли быстрее?
- 25. Более быстрый алгоритмПохоже, что от вычисления d[i]
- 26. Свойство массива lastЭтот массив является неубывающимДействительно, пусть
- 27. Вычисление d[i]Находим место в массиве last, на
- 28. УпражненияПродумать, как сохранять информацию для восстановления ответаРеализовать этот алгоритм
- 29. Задача о рюкзакеЕсть рюкзак вместимостью W и
- 30. Разбиение на подзадачиДва параметра – число обработанных
- 31. Рекуррентная формулаОчередной предмет можно либо взять, либо не взять
- 32. Начальные условияc[0][j] = 0 для j=0…Wc[i][0] = 0 для i=0…n
- 33. Два способа реализацииМетод заполнения таблицы можно реализовать
- 34. «Динамика вперед»for i := 0 to n
- 35. Восстановление ответаНеобходимо запоминать для каждого состояния (i, j) надо ли брать очередной предметРеализуйте сами!
- 36. Время работы алгоритмаВремя работы этого алгоритма –
- 37. УпражненияРешите задачу о рюкзаке для случая, когда
- 38. Оптимальная триангуляция многоугольникаЗадан выпуклый многоугольникНеобходимо разбить его
- 39. Нумерация вершин многоугольникаВершины (n+1)-угольника нумеруются числами от
- 40. Разбиение на подзадачиПосле вырезания одного треугольника, многоугольника распадается на два, которые можно рассматривать отдельно
- 41. Строение оптимального решенияРассмотрим оптимальную триангуляцию заданного (n+1)-угольника
- 42. Рекуррентная формулаd[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i j
- 43. Восстановление ответаДля каждой подзадачи необходимо запомнить оптимальное значение числа kРеализуйте самостоятельно!
- 44. УпражненияПусть стоимостью треугольника считается его площадь. Как
- 45. ВыводыРассмотрены три примера задач, решаемых методом динамического
- 46. Спасибо за внимание!Вопросы? Комментарии?fedor.tsarev@gmail.com
- 47. Скачать презентанцию
Цель лекцииИзучить еще несколько примеров задач, решаемых с помощью динамического программирования, и их решения
Слайды и текст этой презентации
Слайд 1Динамическое программирование. Примеры задач
Федор Царев
Спецкурс «Олимпиадное программирование»
Лекция 5
13.04.2009
Санкт-Петербург, Гимназия 261
Слайд 2Цель лекции
Изучить еще несколько примеров задач, решаемых с помощью динамического
программирования, и их решения
Слайд 3Признаки возможности применения ДП
Возможность разбиения задачи на подзадачи (метод «разделяй-и-властвуй»)
Наличие
свойства оптимальности для подзадач – оптимальный ответ для большой задачи
строится на основе оптимальных ответов для меньшихНаличие перекрывающихся подзадач
Слайд 4Этапы решения задачи методом динамического программирования
Разбиение задачи на подзадачи
Построение рекуррентной
формулы для вычисления значения функции (включая начальные условия)
Вычисление значения функции
для всех подзадач (важен порядок вычисления)Восстановление структуры оптимального ответа
Слайд 5Наибольшая возрастающая подпоследовательность
Задана последовательность чисел a1, a2, …, an
Необходимо найти
возрастающую подпоследовательность наибольшей длины
1 5 3 7 1 4 10
15 
Слайд 7Разбиение на подзадачи
Идея: найти наибольшую возрастающую подпоследовательность среди первых i
элементов: a1, a2, …, ai
Попробуйте построить рекуррентную формулу
Более точно: найти
наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai, последний элемент в которой - ai
Слайд 8Рекуррентная формула
d[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в
ai
Считается, что максимум равен нулю, если таких индексов j нет
![Рекуррентная формулаd[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в aiСчитается, что максимум равен нулю, если таких](/img/thumbs/a5e98516fc9b7128b27d10561e1f01cc-800x.jpg "Динамическое программирование. Примеры задач Рекуррентная формулаd[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в aiСчитается,")
Слайд 9Начальные условия
Можно сделать немного проще
Считаем, что в начало добавлен a0=–∞,
а d[0] = 0
Теперь можно не делать никаких предположений, так
как всегда найдется некоторый индекс j![Начальные условияМожно сделать немного прощеСчитаем, что в начало добавлен a0=–∞, а d[0] = 0Теперь можно не делать](/img/thumbs/052fb8ecc73c6bd00b29d371c7655420-800x.jpg "Динамическое программирование. Примеры задач Начальные условияМожно сделать немного прощеСчитаем, что в начало добавлен a0=–∞, а")
Слайд 19Программа
d[0] := 0;
for i := 1 to n do begin
max
:= 0;
for j := 1 to i – 1 do
beginif (a[j] < a[i]) and
(d[j] > max) then begin
max := d[j];
end;
end;
d[i] := max + 1;
end;
![Программаd[0] := 0;for i := 1 to n do begin max := 0; for j := 1 to i](/img/thumbs/b88bb24ab0a9b93666c905ec5c351eb8-800x.jpg "Динамическое программирование. Примеры задач Программаd[0] := 0;for i := 1 to n do begin max :=")
Слайд 20Восстановление ответа
Где находится длина L наибольшей возрастающей подпоследовательности?
L := 0;
pos
:= -1;
for i := 1 to n do begin
if (d[i]
> max) then beginmax := d[i];
pos := i;
end;
end;
Слайд 21Вычисление с сохранением информации для восстановления ответа
d[0] := 0;
prev[0] :=
-1;
for i := 1 to n do begin
max := 0;
bestj
:= -1;for j := 1 to i – 1 do begin
if (a[j] < a[i]) and
(d[j] > max) then begin
max := d[j];
bestj := j;
end;
end;
d[i] := max + 1;
prev[i] := bestj;
end;
![Вычисление с сохранением информации для восстановления ответаd[0] := 0;prev[0] := -1;for i := 1 to n do](/img/thumbs/5d31629ff42a0bf5af6aa6975c90dca4-800x.jpg "Динамическое программирование. Примеры задач Вычисление с сохранением информации для восстановления ответаd[0] := 0;prev[0] := -1;for")
Слайд 22Восстановление ответа
procedure restore(i : integer);
begin
if (i > 0) then begin
restore(prev[i]);
write(a[i]);
end;
end;
![Восстановление ответаprocedure restore(i : integer);begin if (i > 0) then begin restore(prev[i]); write(a[i]); end;end;](/img/thumbs/4159633a00a5e722f453ccf7db300698-800x.jpg "Динамическое программирование. Примеры задач Восстановление ответаprocedure restore(i : integer);begin if (i > 0) then begin restore(prev[i]); write(a[i]); end;end;")
Слайд 25Более быстрый алгоритм
Похоже, что от вычисления d[i] никуда не деться
Попробуем
вычислять d[i] быстрее
Пусть last[i] – минимальное последнее число в возрастающей
подпоследовательности длины i ![Более быстрый алгоритмПохоже, что от вычисления d[i] никуда не детьсяПопробуем вычислять d[i] быстрееПусть last[i] – минимальное последнее](/img/thumbs/12a771b84d16147ca6ec6368d3c4262b-800x.jpg "Динамическое программирование. Примеры задач Более быстрый алгоритмПохоже, что от вычисления d[i] никуда не детьсяПопробуем вычислять")
Слайд 26Свойство массива last
Этот массив является неубывающим
Действительно, пусть i < j,
но last[i] > last[j]
Из подпоследовательности длины i можно сделать подпоследовательность
длины j, поэтому last[j] ≤ last[i] (last[j] – минимальный, last[i] – некоторый)![Свойство массива lastЭтот массив является неубывающимДействительно, пусть i < j, но last[i] > last[j]Из подпоследовательности длины i](/img/thumbs/7155294401630571cb33165e316b6475-800x.jpg "Динамическое программирование. Примеры задач Свойство массива lastЭтот массив является неубывающимДействительно, пусть i < j, но")
Слайд 27Вычисление d[i]
Находим место в массиве last, на которое следует поставить
a[i] – такую позицию j, что last[j-1] < a[i] ≤
last[j]Это означает, что максимальная длина подпоследовательности, которая заканчивается в a[i] есть j (d[i] = j)
Позицию j надо искать с помощью двоичного поиска
Время работы алгоритма – O(nlogn)
![Вычисление d[i]Находим место в массиве last, на которое следует поставить a[i] – такую позицию j, что last[j-1]](/img/thumbs/42160c2170ab37afebe69931a47dec43-800x.jpg "Динамическое программирование. Примеры задач Вычисление d[i]Находим место в массиве last, на которое следует поставить a[i]")
Слайд 28Упражнения
Продумать, как сохранять информацию для восстановления ответа
Реализовать этот алгоритм
Слайд 29Задача о рюкзаке
Есть рюкзак вместимостью W и n предметов, каждый
из которых характеризуется ценностью pi и весом wi
Необходимо выбрать несколько
предметов так, чтобы их суммарная ценность была максимальна, а суммарный вес не превышал W
Слайд 30Разбиение на подзадачи
Два параметра – число обработанных предметов и вместимость
рюкзака
c[i][j] – максимальная суммарная стоимость, которую можно набрать первыми i
предметами так, чтобы их вес не превосходил j![Разбиение на подзадачиДва параметра – число обработанных предметов и вместимость рюкзакаc[i][j] – максимальная суммарная стоимость, которую можно](/img/thumbs/aa64850bd7f34acbdb2ce66d5acfa6bd-800x.jpg "Динамическое программирование. Примеры задач Разбиение на подзадачиДва параметра – число обработанных предметов и вместимость рюкзакаc[i][j]")
![Начальные условияc[0][j] = 0 для j=0…Wc[i][0] = 0 для i=0…n](/img/thumbs/fd32ceb3837316513a3ba0512e6e1ff2-800x.jpg "Динамическое программирование. Примеры задач Начальные условияc[0][j] = 0 для j=0…Wc[i][0] = 0 для i=0…n")
Слайд 33Два способа реализации
Метод заполнения таблицы можно реализовать двумя способами
«Динамика назад»
(этот метод использовался во всех рассмотренных задачах)
«Динамика вперед»
Слайд 34«Динамика вперед»
for i := 0 to n do begin
for j
:= 0 to W do begin
c[i][j] := -INF;
end;
end;
for i :=
0 to n – 1 do beginfor j := 0 to W do begin
if (c[i][j] = -INF) then continue;
c[i+1][j]:=max(c[i][j], c[i+1][j]);
if (j + w[i + 1] <= W) then begin
c[i + 1][j + w[i + 1]] = max(c[i][j] + p[i+1],
c[i + 1][j + w[i + 1]]);
end;
end;
end;
![«Динамика вперед»for i := 0 to n do begin for j := 0 to W do begin c[i][j] :=](/img/thumbs/5734c96bbd71876c0ac65bebdd308002-800x.jpg "Динамическое программирование. Примеры задач «Динамика вперед»for i := 0 to n do begin for j :=")
Слайд 35Восстановление ответа
Необходимо запоминать для каждого состояния (i, j) надо ли
брать очередной предмет
Реализуйте сами!
Слайд 36Время работы алгоритма
Время работы этого алгоритма – O(nW)
Таким образом, он
применим только для относительно небольших значений весов предметов
Слайд 37Упражнения
Решите задачу о рюкзаке для случая, когда имеется неограниченное число
предметов каждого типа
Решите задачу о рюкзаке для случая, когда предметы
можно брать не полностью (не золотые слитки, а золотой песок)Решите смешанную задачу о рюкзаке – часть предметов можно брать только полностью, а остальные – можно и не полностью
Слайд 38Оптимальная триангуляция многоугольника
Задан выпуклый многоугольник
Необходимо разбить его на треугольники, проведя
несколько диагоналей
Суммарный периметр треугольников должен быть как можно меньшим
Кстати, сколько
придется провести диагоналей, если в многоугольнике N углов?
Слайд 39Нумерация вершин многоугольника
Вершины (n+1)-угольника нумеруются числами от 0 до n
При
этом когда говорится о вершине «номер k» имеется в виду
вершина «номер k mod n» (то есть vn=v0, …)
Слайд 40Разбиение на подзадачи
После вырезания одного треугольника, многоугольника распадается на два,
которые можно рассматривать отдельно
Слайд 41Строение оптимального решения
Рассмотрим оптимальную триангуляцию заданного (n+1)-угольника v0,v1, …, vn
Ребро
v0vn входит в некоторый треугольник
Пусть это треугольник v0vnvk
Тогда стоимость триангуляции
равнаСтоимость этого треугольника +
Стоимость триангуляции v0, v1, …, vk +
Стоимость триангуляции vk, vk+1, …, vn
Слайд 42Рекуррентная формула
d[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i
в d[1][n]
Начальные условия:
d[i][i] = 0
d[i][j] = -∞ при i >
j![Рекуррентная формулаd[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i j](/img/thumbs/bd484d7bac9a5d56cb66b92c1e4f3ace-800x.jpg "Динамическое программирование. Примеры задач Рекуррентная формулаd[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i j")
Слайд 43Восстановление ответа
Для каждой подзадачи необходимо запомнить оптимальное значение числа k
Реализуйте
самостоятельно!
Слайд 44Упражнения
Пусть стоимостью треугольника считается его площадь. Как найти оптимальную триангуляцию?
Пусть
необходимо минимизировать суммарную длину проведенных диагоналей. Как найти оптимальную триангуляцию
в этом случае?
Слайд 45Выводы
Рассмотрены три примера задач, решаемых методом динамического программирования
Метод заполнения таблицы
может быть реализован двумя способами – «динамика вперед» и «динамика
назад»Необходимо следить за тем, чтобы не выполнялись переходы из недостижимых состояний
