Динамическое программирование - Презентация

Динамическое программирование Лекция 20План лекции Понятие динамического программирования Примеры Сумма геометрической прогрессии Суммирование набора Задача о рюкзаке Произведение матриц Алгоритм Флойда-УОРШАЛЛАРИЧАРД Беллман ~1940 Какой алгоритм назван в честь этого ученого? Описание процесса решения задачи, при котором решение одной задачу вычисляется на основании решения "предшествующих" задач Один из методов численного решения задач оптимизации Первоначально часть системного анализа Понятие динамического ПРОГРАММИРОВАНИЯТЕРМИН «динамическое программирование» происходит от термина «математическое программирование», который является синонимом слова «оптимизация» Слово «программирование» в словосочетании «динамическое программирование» к традиционному программированию почти никакого отношения не имеет Слово «программа» в Д.П. означает оптимальную последовательность действий для получения решения задачи Расписание событий на выставке называют программой и понимают как допустимую последовательность событий Понятие динамического ПРОГРАММИРОВАНИЯПОНЯТИЕ динамического программирования Последовательность действий в Д.П. имеет вид Разбиение задачи на подзадачи меньшего размера Нахождение оптимального решения подзадач рекурсивно Вычисление оптимального решения исходной задачи на основании оптимальных решений подзадач Деление на подзадачи происходит до тех пор, пока не получатся тривиальные задачи, решаемые за константное время В общем случае требование оптимальности может отсутствовать (Д.П. с постоянной целевой функцией) Например, вычисление n! можно рассматривать как задачу Д.П. с постоянной целевой функцией и тривиальными задачами 1! = 1Понятие динамического программирования Простая рекурсивная реализация будет расходовать время на вычисление решений для задач, которые уже один раз решались Чтобы избежать такого хода событий будем сохранять в таблице решение каждой решенной подзадачи Когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто возьмем его из таблицы Этот прием называется КЭШИРОВАНИЕПОНЯТИЕ динамического программирования Динамическим программированием называется способ программирования, при котором задача разбивается на подзадачи , вычисление идет от малых подзадач к большим, решения подзадач запоминаются в таблице и используются при решении больших задач Заполнение таблицы в Д.П. называется прямым ходом Исходные данные подзадач называются параметрами Задачу можно рассматривать как функцию, аргументами которой являются параметры задачи Например, при нахождении суммы набора чисел параметрами задачи будут количество чисел и их ЗНАЧЕНИЯПОНЯТИЕ динамического программирования Под подзадачей понимается та же постановка задачи, но с меньшим числом параметров или с тем же числом параметров, но при этом хотя бы один из параметров имеет меньшее значение Преимущество Д.П. состоит в том, что каждую подзадачу мы решаем ровно один раз Сведение решения задачи к решению подзадач записывается в виде соотношений , которые выражают значение целевой функции для исходной задачи через значения целевой функции для подзадач З начения аргументов у любой из функций в правой части соотношения меньше значения аргументов функции в левой части соотношения Если аргументов несколько, то достаточно уменьшения одного из НИХПОНЯТИЕ динамического программирования Динамическое программирование может быть применено к задачам оптимизации , в которых решением является последовательность шагов, приводящая к достижению минимума или максимума целевой функции Процедура восстановления оптимального решения называется обратным ходом Соотношения между значением целевой функции для Оптимальное решение более сложной Чтобы выписать рекуррентные соотношения, связывающие оптимальные значения параметра для подзадач, двигаясь снизу вверх, вычислить оптимальные решения для подзадач и используя их построить оптимальное решение для поставленной задачи Для применения Д.П. бывает удобно решать не заданную задачу, а более общую задачу, и рассматривать исходную задачу как частный случай этой более общей ЗАДАЧИРАССМОТРИМ пример. Параметры подзадач : k 0 T (i , 0) = 1 при i ? 1 всегда можно набрать вес, равный 0 Пример - суммирование НАБОРАПРИМЕР - суммирование набора Для оптимального решения из двух возможных вариантов нужно выбрать наилучший i-ый предмет в набор не берется T (i , j ) = T (i - 1, j ) Решение задачи с i предметами сводится к решению задачи с i - предметом i-ый предмет в набор берется T (i , j ) = T (i-1, j - w i ) Масса оставшихся предметов уменьшается на величину w i Эта ситуация возможна, если масса i-го предмета не больше значения j Соотношения T(i, j)= T(i-1, j) при j i ) - наименьшая из сумм этих трех членов по всем возможным значениям k , лежащим между i и j - 1.