🗊Презентация Динамическое программирование. Примеры задач

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Динамическое программирование. Примеры задач, слайд №1Динамическое программирование. Примеры задач, слайд №2Динамическое программирование. Примеры задач, слайд №3Динамическое программирование. Примеры задач, слайд №4Динамическое программирование. Примеры задач, слайд №5Динамическое программирование. Примеры задач, слайд №6Динамическое программирование. Примеры задач, слайд №7Динамическое программирование. Примеры задач, слайд №8Динамическое программирование. Примеры задач, слайд №9Динамическое программирование. Примеры задач, слайд №10Динамическое программирование. Примеры задач, слайд №11Динамическое программирование. Примеры задач, слайд №12Динамическое программирование. Примеры задач, слайд №13Динамическое программирование. Примеры задач, слайд №14Динамическое программирование. Примеры задач, слайд №15Динамическое программирование. Примеры задач, слайд №16Динамическое программирование. Примеры задач, слайд №17Динамическое программирование. Примеры задач, слайд №18Динамическое программирование. Примеры задач, слайд №19Динамическое программирование. Примеры задач, слайд №20Динамическое программирование. Примеры задач, слайд №21Динамическое программирование. Примеры задач, слайд №22Динамическое программирование. Примеры задач, слайд №23Динамическое программирование. Примеры задач, слайд №24Динамическое программирование. Примеры задач, слайд №25Динамическое программирование. Примеры задач, слайд №26Динамическое программирование. Примеры задач, слайд №27Динамическое программирование. Примеры задач, слайд №28Динамическое программирование. Примеры задач, слайд №29Динамическое программирование. Примеры задач, слайд №30Динамическое программирование. Примеры задач, слайд №31Динамическое программирование. Примеры задач, слайд №32Динамическое программирование. Примеры задач, слайд №33Динамическое программирование. Примеры задач, слайд №34Динамическое программирование. Примеры задач, слайд №35Динамическое программирование. Примеры задач, слайд №36Динамическое программирование. Примеры задач, слайд №37Динамическое программирование. Примеры задач, слайд №38Динамическое программирование. Примеры задач, слайд №39Динамическое программирование. Примеры задач, слайд №40Динамическое программирование. Примеры задач, слайд №41Динамическое программирование. Примеры задач, слайд №42Динамическое программирование. Примеры задач, слайд №43Динамическое программирование. Примеры задач, слайд №44Динамическое программирование. Примеры задач, слайд №45Динамическое программирование. Примеры задач, слайд №46
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Динамическое программирование. Примеры задач. Доклад-сообщение содержит 46 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Динамическое программирование. Примеры задач Федор Царев Спецкурс «Олимпиадное программирование» Лекция 5
Описание слайда:
Динамическое программирование. Примеры задач Федор Царев Спецкурс «Олимпиадное программирование» Лекция 5

Слайд 2


Цель лекции Изучить еще несколько примеров задач, решаемых с помощью динамического программирования, и их решения
Описание слайда:
Цель лекции Изучить еще несколько примеров задач, решаемых с помощью динамического программирования, и их решения

Слайд 3


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

Слайд 4


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

Слайд 5


Наибольшая возрастающая подпоследовательность Задана последовательность чисел a1, a2, …, an Необходимо найти возрастающую подпоследовательность наибольшей длины 1 5 3 7 1 4 10 15
Описание слайда:
Наибольшая возрастающая подпоследовательность Задана последовательность чисел a1, a2, …, an Необходимо найти возрастающую подпоследовательность наибольшей длины 1 5 3 7 1 4 10 15

Слайд 6


Перебор? Число различных подпоследовательностей: (2n – 1) Можно применять для n ≤ 20
Описание слайда:
Перебор? Число различных подпоследовательностей: (2n – 1) Можно применять для n ≤ 20

Слайд 7


Разбиение на подзадачи Идея: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai Попробуйте построить рекуррентную формулу Более точно: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai, последний элемент в которой - ai
Описание слайда:
Разбиение на подзадачи Идея: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai Попробуйте построить рекуррентную формулу Более точно: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai, последний элемент в которой - ai

Слайд 8


Рекуррентная формула d[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в ai
Описание слайда:
Рекуррентная формула d[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в ai

Слайд 9


Начальные условия Можно сделать немного проще Считаем, что в начало добавлен a0=–∞, а d[0] = 0 Теперь можно не делать никаких предположений, так как всегда найдется некоторый индекс j
Описание слайда:
Начальные условия Можно сделать немного проще Считаем, что в начало добавлен a0=–∞, а d[0] = 0 Теперь можно не делать никаких предположений, так как всегда найдется некоторый индекс j

Слайд 10


Пример (1)
Описание слайда:
Пример (1)

Слайд 11


Пример (2)
Описание слайда:
Пример (2)

Слайд 12


Пример (3)
Описание слайда:
Пример (3)

Слайд 13


Пример (4)
Описание слайда:
Пример (4)

Слайд 14


Пример (5)
Описание слайда:
Пример (5)

Слайд 15


Пример (6)
Описание слайда:
Пример (6)

Слайд 16


Пример (7)
Описание слайда:
Пример (7)

Слайд 17


Пример (8)
Описание слайда:
Пример (8)

Слайд 18


Пример (9)
Описание слайда:
Пример (9)

Слайд 19


Программа d[0] := 0; for i := 1 to n do begin max := 0; for j := 1 to i – 1 do begin if (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 – 1 do begin if (a[j] < a[i]) and (d[j] > max) then begin max := d[j]; end; end; d[i] := max + 1; end;

Слайд 20


Восстановление ответа Где находится длина L наибольшей возрастающей подпоследовательности?
Описание слайда:
Восстановление ответа Где находится длина L наибольшей возрастающей подпоследовательности?

Слайд 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 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;

Слайд 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;

Слайд 23


Пример
Описание слайда:
Пример

Слайд 24


Время работы Время работы этого алгоритма – O(n2) Можно ли быстрее?
Описание слайда:
Время работы Время работы этого алгоритма – O(n2) Можно ли быстрее?

Слайд 25


Более быстрый алгоритм Похоже, что от вычисления d[i] никуда не деться Попробуем вычислять d[i] быстрее Пусть last[i] – минимальное последнее число в возрастающей подпоследовательности длины i
Описание слайда:
Более быстрый алгоритм Похоже, что от вычисления d[i] никуда не деться Попробуем вычислять d[i] быстрее Пусть last[i] – минимальное последнее число в возрастающей подпоследовательности длины 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 можно сделать подпоследовательность длины j, поэтому last[j] ≤ last[i] (last[j] – минимальный, last[i] – некоторый)

Слайд 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] < a[i] ≤ last[j] Это означает, что максимальная длина подпоследовательности, которая заканчивается в a[i] есть j (d[i] = j) Позицию j надо искать с помощью двоичного поиска Время работы алгоритма – O(nlogn)

Слайд 28


Упражнения Продумать, как сохранять информацию для восстановления ответа Реализовать этот алгоритм
Описание слайда:
Упражнения Продумать, как сохранять информацию для восстановления ответа Реализовать этот алгоритм

Слайд 29


Задача о рюкзаке Есть рюкзак вместимостью W и n предметов, каждый из которых характеризуется ценностью pi и весом wi Необходимо выбрать несколько предметов так, чтобы их суммарная ценность была максимальна, а суммарный вес не превышал W
Описание слайда:
Задача о рюкзаке Есть рюкзак вместимостью W и n предметов, каждый из которых характеризуется ценностью pi и весом wi Необходимо выбрать несколько предметов так, чтобы их суммарная ценность была максимальна, а суммарный вес не превышал W

Слайд 30


Разбиение на подзадачи Два параметра – число обработанных предметов и вместимость рюкзака c[i][j] – максимальная суммарная стоимость, которую можно набрать первыми i предметами так, чтобы их вес не превосходил j
Описание слайда:
Разбиение на подзадачи Два параметра – число обработанных предметов и вместимость рюкзака c[i][j] – максимальная суммарная стоимость, которую можно набрать первыми i предметами так, чтобы их вес не превосходил j

Слайд 31


Рекуррентная формула
Описание слайда:
Рекуррентная формула

Слайд 32


Начальные условия c[0][j] = 0 для j=0…W c[i][0] = 0 для i=0…n
Описание слайда:
Начальные условия c[0][j] = 0 для j=0…W c[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 begin for 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] := -INF; end; end; for i := 0 to n – 1 do begin for 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;

Слайд 35


Восстановление ответа Необходимо запоминать для каждого состояния (i, j) надо ли брать очередной предмет Реализуйте сами!
Описание слайда:
Восстановление ответа Необходимо запоминать для каждого состояния (i, j) надо ли брать очередной предмет Реализуйте сами!

Слайд 36


Время работы алгоритма Время работы этого алгоритма – O(nW) Таким образом, он применим только для относительно небольших значений весов предметов
Описание слайда:
Время работы алгоритма Время работы этого алгоритма – O(nW) Таким образом, он применим только для относительно небольших значений весов предметов

Слайд 37


Упражнения Решите задачу о рюкзаке для случая, когда имеется неограниченное число предметов каждого типа Решите задачу о рюкзаке для случая, когда предметы можно брать не полностью (не золотые слитки, а золотой песок) Решите смешанную задачу о рюкзаке – часть предметов можно брать только полностью, а остальные – можно и не полностью
Описание слайда:
Упражнения Решите задачу о рюкзаке для случая, когда имеется неограниченное число предметов каждого типа Решите задачу о рюкзаке для случая, когда предметы можно брать не полностью (не золотые слитки, а золотой песок) Решите смешанную задачу о рюкзаке – часть предметов можно брать только полностью, а остальные – можно и не полностью

Слайд 38


Оптимальная триангуляция многоугольника Задан выпуклый многоугольник Необходимо разбить его на треугольники, проведя несколько диагоналей Суммарный периметр треугольников должен быть как можно меньшим Кстати, сколько придется провести диагоналей, если в многоугольнике N углов?
Описание слайда:
Оптимальная триангуляция многоугольника Задан выпуклый многоугольник Необходимо разбить его на треугольники, проведя несколько диагоналей Суммарный периметр треугольников должен быть как можно меньшим Кстати, сколько придется провести диагоналей, если в многоугольнике N углов?

Слайд 39


Нумерация вершин многоугольника Вершины (n+1)-угольника нумеруются числами от 0 до n При этом когда говорится о вершине «номер k» имеется в виду вершина «номер k mod n» (то есть vn=v0, …)
Описание слайда:
Нумерация вершин многоугольника Вершины (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
Описание слайда:
Строение оптимального решения Рассмотрим оптимальную триангуляцию заданного (n+1)-угольника v0,v1, …, vn Ребро v0vn входит в некоторый треугольник Пусть это треугольник v0vnvk Тогда стоимость триангуляции равна Стоимость этого треугольника + Стоимость триангуляции v0, v1, …, vk + Стоимость триангуляции vk, vk+1, …, vn

Слайд 42


Рекуррентная формула d[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i<j≤n) Ответ находится в d[1][n]
Описание слайда:
Рекуррентная формула d[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i<j≤n) Ответ находится в d[1][n]

Слайд 43


Восстановление ответа Для каждой подзадачи необходимо запомнить оптимальное значение числа k Реализуйте самостоятельно!
Описание слайда:
Восстановление ответа Для каждой подзадачи необходимо запомнить оптимальное значение числа k Реализуйте самостоятельно!

Слайд 44


Упражнения Пусть стоимостью треугольника считается его площадь. Как найти оптимальную триангуляцию? Пусть необходимо минимизировать суммарную длину проведенных диагоналей. Как найти оптимальную триангуляцию в этом случае?
Описание слайда:
Упражнения Пусть стоимостью треугольника считается его площадь. Как найти оптимальную триангуляцию? Пусть необходимо минимизировать суммарную длину проведенных диагоналей. Как найти оптимальную триангуляцию в этом случае?

Слайд 45


Выводы Рассмотрены три примера задач, решаемых методом динамического программирования Метод заполнения таблицы может быть реализован двумя способами – «динамика вперед» и «динамика назад» Необходимо следить за тем, чтобы не выполнялись переходы из недостижимых состояний
Описание слайда:
Выводы Рассмотрены три примера задач, решаемых методом динамического программирования Метод заполнения таблицы может быть реализован двумя способами – «динамика вперед» и «динамика назад» Необходимо следить за тем, чтобы не выполнялись переходы из недостижимых состояний

Слайд 46


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию