Динамическое программирование - тема, которой в рунете посвящено довольно мало статей, поэтому мы решили ею заняться. В этой статье будут разобраны классические задачи на последовательности, одномерную и двумерную динамику, будет дано обоснование решениям и описаны разные подходы к их реализации. Весь приведённый в статье код написан на Java.
О чём вообще речь? Что такое динамическое программирование?
Метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи - чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом
на основе второго и третьего, и так далее (да, мы слышали про замкнутую формулу).
Хорошо, как это использовать?
Решение задачи динамическим программированием должно содержать следующее:
И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.
Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:
Вычислить n-й член последовательности, заданной формулами:
a 2n = a n + a n-1 ,
a 2n+1 = a n — a n-1 ,
a 0 = a 1 = 1.
Идея решения
Здесь нам даны и начальные состояния (a 0 = a 1 = 1), и зависимости. Единственная сложность, которая может возникнуть - понимание того, что 2n - условие чётности числа, а 2n+1 - нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.
Рекурсивное решение
Очевидная реализация состоит в написании следующего метода:
Private static int f(int n){ if(n==0 || n==1) return 1; // Проверка на начальное значение if(n%2==0){ //Проверка на чётность return f(n/2)+f(n/2-1); // Вычисляем по формуле для чётных индексов, // ссылаясь на предыдущие значения }else{ return f((n-1)/2)-f((n-1)/2-1); // Вычисляем по формуле для нечётных //индексов, ссылаясь на предыдущие значения } }
И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть - мемоизация (кеширование значений).
Рекурсивное решение с кэшированием значений
Идея мемоизации очень проста - единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу - все действия в ней выполняются за O(1) , что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево .
Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:
Private static HashMap
Не слишком сложно, согласитесь? Зато это избавляет от огромного числа операций. Платите вы за это лишним расходом памяти.
Последовательное вычисление
Теперь вернёмся к тому, с чего начали - рекурсия работает медленно. Не слишком медленно, чтобы это приносило действительные неприятности в настоящей жизни, но на соревнованиях по спортивному программированию каждая миллисекунда на счету.
Метод последовательного вычисления подходит, только если функция ссылается исключительно на элементы перед ней - это его основной, но не единственный минус. Наша задача этому условию удовлетворяет.
Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log 2 (N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.
Private static int f(int n){
if(n<2) return 1; //Может, нам и вычислять ничего не нужно?
int fs = int[n]; //Создаём массив для значений
fs=fs=1; //Задаём начальные состояния
for(int i=2; i Ещё одним минусом такого подхода является сравнительно большой расход памяти. Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем - сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали. Зависимости вычисляются следующим образом: LinkedList Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172. Теперь мы поочередно извлекаем индексы и вычисляем для них значения по формулам – гарантируется, что все необходимые значения уже будут вычислены. Хранить будем как раньше – в хэш-таблице. HashMap Все необходимые значения вычислены, осталось только написать Return values.get(n);
Конечно, такое решение гораздо более трудоёмкое, однако это того стоит. Для больше ясности разберём следующую задачу на одномерную динамику: На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю. На первую ступеньку можно попасть только одним образом - сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки - всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки - по одному маршруту на каждый маршрут до неё, со второй или с третьей - аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3) . Первые три ступеньки будем считать начальными состояниями. Здесь ничего хитрого нет. Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх. Int vars = new int;
vars=1;vars=2;vars=4;
for(int i=3; i Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно. С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё. В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Логика решения полностью идентична таковой в задаче про мячик и лестницу - только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1) . Итого F(x,y) = F(x-1, y)+F(x,y-1) . Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут - по прямой вниз или по прямой вправо. Ради всего святого, не нужно делать двумерную динамику через рекурсию. Уже было упомянуто, что рекурсия менее выгодна, чем цикл по быстродействию, так двумерная рекурсия ещё и читается ужасно. Это только на таком простом примере она смотрится легко и безобидно. Private static int f(int i, int j) {
if(i==1 || j==1) return 1;
return f(i-1, j)+f(i, j-1);
}
В заключение приведу ряд типичных задач на одномерную и двумерную динамику, разборы прилагаются. При переработке радиоактивных материалов образуются отходы двух видов - особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок. Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений. Каждый основной элемент делится на два - основной (заканчивается на B) и побочный (заканчивается на A). Побочные элементы превращаются в основные за одну итерацию (к последовательности, заканчивающейся на A, можно дописать только B). Это характерно для чисел Фибоначчи. Например, так: //Ввод числа N с клавиатуры
N+=2;
BigInteger fib = new BigInteger;
fib=fib=BigInteger.ONE;
for(int i=2; i Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую - с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую. Например, так: Int Imax;
//*ввод с клавиатуры числа ступенек*
DP = new int;
for(int i=0; i Имеется калькулятор, который выполняет три операции: Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231». Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки. Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1 . Следует помнить, что все индексы должны быть целыми. Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N) , где N - номер рассматриваемого элемента. Если i=N-1 , записываем в начало строки 1, если i=N/2 - двойку, иначе - тройку. В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути). Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол. Динамического программирования
1. Динамическое программирование. Основные понятия…………………2
2. Суть метода динамического программирования………………………..4
3. Пример решения задачи методом динамического программирования………………………………………………………...7 Список используемых источников……………………………………...11 1.
Динамическое программирование. Основные понятия.
Динамическое программирование (ДП)
в теории вычислительных систем - способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы. В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для применения в коммерческой деятельности при решении как линейных, так и нелинейных задач. Динамическое программирование является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами динамического программирования решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах динамического программирования эти зависимости могут иметь еще и нелинейный характер. Динамическое программирование можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения динамического программирования для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариантов, увеличивает достоинства этого комплекса методов. Вместе с тем динамическому программированию свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний. Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана. Динамическое программирование применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети; формирование последовательности развития коммерческой операции и т. д. Суть метода динамического программирования.
В основу метода динамического программирования положен принцип оптимальности
, сформулированный в 1957 г. американским математиком Ричардом Беллманом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения». Физическая сущность принципа оптимальности заключается в том, что ошибка выбора решения в данный момент не может быть исправлена в будущем. Рассматривается следующая общая задача. Имеется некоторая физическая система, в которой происходит какой-то процесс, состоящий из n
шагов. Эффективность процесса характеризуется некоторым показателем W
, который называют выигрышем
. Пусть общий выигрыш W
за все n
шагов процесса складывается из выигрышей на отдельных шагах где w i
- выигрыш на i
-м шаге. Если W
обладает таким свойством, то его называют аддитивным критерием
. Процесс, о котором идет речь, представляет собой управляемый процесс, т.е. имеется возможность выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге. Это решение называется шаговым управлением
. Совокупность всех шаговых управлений представляет собой управление процессом в целом. Обозначим его буквой U
, а шаговые управления - буквами . Тогда Шаговые управления в общем случае не числа, а, как правило, векторы, функции и т.п. В модели динамического программирования процесс на каждом шаге находится в одном из состояний s
множества состояний S
. Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s
0 - начальное и s w
- конечное. Итак, пусть каждому состоянию поставлено множество допустимых шаговых управлений , и каждому шаговому управлению , соответствует и заканчивается конечным состоянием. Для единообразия можно считать, что включает только одно состояние , оставляющее процесс в том же конечном состоянии. Следует отметить, что множества допустимых состояний и управлений конечны и U s
для различных s
не пересекаются. В общем виде задача динамического программирования формулируется следующим образом: найти такую траекторию процесса, при которой выигрыш (2.1)будет максимальным. То управление, при котором достигается максимальный выигрыш, называется оптимальным управлением
. Оно состоит из совокупности шаговых управлений Тот максимальный выигрыш, который достигается при этом управлении обозначим W max
: W max
= max U
{W
(u
)}. (2.5) Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем. Загрузку рюкзака можно представить себе как процесс, состоящий из n
шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса - присваивание переменной x i
значения 1 или 0. Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака - вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака). Следовательно, под состоянием перед i
-м шагом понимается величина при этом s
0 является начальным состоянием, которому соответствует величина b
- исходная грузоподъемность рюкзака. Управление на i
-м шаге означает присваивание двоичной переменной x i
значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления u i
, устанавливающего x i
= 1, определяется условием Шаговый выигрыш можно определить как . Поэтому Требуется найти оптимальное управление , при котором величина выигрыша (2.10) обращается в максимум. 3. Пример решения задачи методом динамического программирования.
Задание
. Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями. Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль p;(x) тыс. ден. ед. (i=1, 2 и 3) по следующим данным: Решение
. Составим математическую модель задачи. 1.Число шагов равно 3. 2.Пусть s - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге. 3. Управление на i-ом шаге (i=1,2,3) выберем x i - количество средств, инвестируемых в i- ое предприятие. 4. Выигрыш p i (x i) на i-ом шаге - это прибыль, которую приносит i-ое предприятие при инвестировании в него средств xi. Если через выигрыш в целом обозначить общую прибыль W, то W=p 1 (x 1)+ p 2 (x 2)+ p 3 (x 3). 5. Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед. Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и, следовательно, функция перехода в новое состояние имеет вид: f i (s, x) = s-x. 6.На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием: x 3 (s)=s, W 3 (s)=p 3 (s). 7.Согласно принципу оптимальности Беллмана, управление на каждом шаге нужно выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Основное функциональное уравнение примет вид W 2 (s) = max{p
2 (x) + W 3 (s -
x)} Проведем пошаговую оптимизацию, по результатам которой заполним таблицу. В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i=3 функциональное уравнение имеет вид x 3 (s)=s, W3(s)=p3(s), то две колонки таблицы, соответствующие i=3, заполняются автоматически по таблице исходных данных. На шаге i=2 основное функциональное уравнение имеет вид W 2 (s) = max{p 2 (x) + W 3 (s - x)} Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3. На шаге i=1 основное функциональное уравнение имеет вид W x (s) = max{ p x (x) + W 2 (s - x)} а состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу. Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет x 1 (s 1)=0 (s 1 =5), на втором шаге x 2 (s 2) =1 (s 2 =s 1 -x 1 =5) и на третьем шаге x 3 (s 3) =4 (s 3 =s 2 -x 2 =4). Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями. Таким образом, для получения наибольшей общей прибыли в размере 19,26 тыс. ден. ед., необходимо вложить 1 тыс. ден. ед. во второе предприятие и 4 тыс. ден. ед. в третье предприятие. Список используемых источников 1. Беллман Р., Динамическое программирование, пер. с англ., М., 1960 2. Болтянский В. Г.,Математические методы оптимального управления, М., 1966 Динамическое
программирование представляет собой
математический аппарат, позволяющий
быстро находить оптимальное решение в
случае, когда анализируемая ситуация
не содержит факторов неопределенности,
но имеется большое количество вариантов
поведения, приносящих различные
результаты, среди которых необходимо
выбрать наилучший. Динамическое
программирование подходит к решению
некоторого класса задач путем их
разложения на небольшие и менее сложные
задачи. В принципе, задачи такого рода
могут быть решены путем простого перебора
всех возможных вариантов и выбора среди
них наилучшего, однако часто такой
перебор весьма затруднителен. В таких
случаях процесс принятия оптимального
решения может быть разбит на шаги (этапы)
и исследован с помощью метода динамического
программирования. Решение
задач методами динамического
программирования проводится на основе
сформулированного Р. Э. Беллманом
принципа оптимальности: оптимальное
поведение обладает тем свойством, что
каким бы не было первоначальное поведение
системы и первоначальное решение,
последующее решение должно определять
оптимальное поведение относительно
состояния, полученного в результате
первоначального решения. Таким
образом, планирование каждого шага
должно проводиться с учетом общей
выгоды, получаемой по завершении всего
процесса, что и позволяет оптимизировать
конечный результат по выбранному
критерию. Вместе
с тем динамическое программирование
не является универсальным методом
решения. Практическая каждая задача,
решаемая этим методом, характеризуется
своими особенностями и требует проведения
поиска наиболее приемлемой совокупности
методов ее решения. Кроме того, большие
объемы и трудоемкость решения многошаговых
задач, имеющих множество состояний,
приводят к необходимости отбора задач
малой размерности либо использования
сжатой информации. Динамическое
программирование применяется для
решения таких задач, как: распределение
дефицитных капитальных вложений между
новыми направлениями их использования;
разработка правил управления спросом
или запасами; разработка принципов
календарного планирования производства
и выравнивания занятости в условиях
колеблющегося спроса на продукцию,
составления календарных планов текущего
и капитального ремонтов оборудования
и его замены; поиск кратчайших расстояний
на транспортной сети; формирования
последовательности развития коммерческой
операции и т. д. Пусть
процесс оптимизации разбит на n
шагов. На каждом шаге необходимо
определить два типа переменных –
переменную состояния S
и переменную управления X
.
Переменная
определяет, в каких состояниях может
оказаться система на данном k
-м
шаге. В зависимости от
на этом шаге можно применить некоторые
управления, которые характеризуются
переменной .
Применение управления
на k
-м
шаге приносит некоторый результат
и переводит систему в некоторое новое
состояние .
Для каждого возможного состояния на
k
-м
шаге среди всех возможных управлений
выбирается оптимальное управление
Всё
решение задачи разбивается на два этапа.
На первом этапе, который называют
условной
оптимизацией
,отыскивается
функция Беллмана и оптимальные управления
для всех возможных состояний на каждом
шаге, начиная с последнего. После
того, как функция Беллмана и соответствующие
оптимальные управления найдены для
всех шагов с n
-го
по первый, производится второй этап
решения задачи, который называется
безусловной
оптимизацией
. В
общем случае задача динамического
программирования формулируется следующим
образом: требуется определить такое
управление
Особенности
математической модели динамического
программирования заключаются в следующем: задача оптимизации
формулируется как конечный многошаговый
процесс управления; целевая
функция (выигрыш) является аддитивной
и равна сумме целевых функций каждого
шага: Условная
оптимизация.
Как уже отмечалось выше, на данном этапе
отыскиваются функция Беллмана и
оптимальное управление для всех возможных
состояний на каждом шаге, начиная с
последнего в соответствии с алгоритмом
обратной прогонки. На последнем n
-м
шаге найти оптимальное управление
Дальнейшее
вычисление производится согласно
рекуррентному соотношению, связывающему
функцию Беллмана на каждом шаге с этой
же функцией, но вычисленной на предыдущем
шаге: Этот
максимум (или минимум) определяется по
всем возможным для k
и S
значениям переменной управления X
. Безусловная
оптимизация.
После того, как функция Беллмана и
соответствующие оптимальные управления
найдены для всех шагов с n
-го
по первый (на первом шаге k
=1 состояние
системы равно ее начальному состоянию
Рассмотрим
примеры решения трех задач с использованием
динамического программирования,
содержание которых требует выбора
переменных состояния и управления. На уроке будет рассмотрено понятие динамического программирования и исторический аспект его появления. Рассмотрены задачи динамического программирования и некоторые примеры их решения Само понятие «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения другой задачи, «предшествующей» ей. Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом. Слово «программирование»
в контексте «динамическое программирование» на самом деле к классическому пониманию программирования (написанию кода на языке программирования) практически никакого отношения не имеет
. Слово «Программирование» имеет такой же смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому программы
будут использоваться в качестве оптимальной последовательности действий для получения решения задачи. В общем же для начала, неформальное определение понятия динамического программирования
может звучать так: Динамическое программирование
— это техника или метод, которая позволяет решать некоторые задачи комбинаторики, оптимизации и другие задачи, обладающие определенным свойством (свойством сооптимальности у подзадач). Задачи оптимизации
, как правило, связаны с задачей максимизации или минимизации той или иной целевой функции (например, максимизировать вероятность того, что система не сломается, максимизировать мат. ожидание получения прибыли и т.д.). Задачи комбинаторики
, как правило, отвечают на вопрос, сколько существует объектов, обладающих теми или иными свойствами, или сколько существует комбинаторных объектов, обладающих заданными свойствами. То есть, ДП решает не все задачи, а лишь некоторые, определенный класс подзадач. Но этот класс подзадачи используется во многих областях знаний: программирование, математика, лингвистика, статистика, теория игр, экономика, в компьютерных науках и т.п. Задачи, решаемые при помощи динамического программирования, должны обладать свойством сооптимальности
, о котором будет сказано в дальнейших уроках. Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы: Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач Более подробно неформальное объяснение рассматривается . Сначала рассмотрим задачи оптимизации (задачи 1-5): Пример:
Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А
в пункт Б
. Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо. Целевой функцией
здесь является расстояние от А
до Б
. Т.е. наша цель — минимизировать расстояние. А что является переменной выбора
? Для того, чтобы найти кратчайший путь, надо каждый раз принимать решения. Т.е. в каждой точке или на каждом перекрестке необходимо принимать решения: куда повернуть или ехать прямо. Важно:
Из этой задачи уже можно увидеть общую структуру задач, решаемых при помощи динамического программирования: в каждой задаче есть целевая функция и переменная выбора
. Пример:
Каждый год мы принимаем решение, ездить ли на старой машине еще год и понести при этом издержки на поддержку и обслуживание старой машины или же продать эту машину и купить новую (и понести при этом издержки на покупку). Целевая функция:
минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового). Переменная выбора:
каждый год принимать решение продать машину или оставить. Пример:
Игра на бирже, приобретение акций каких-либо компаний Переменная выбора:
то, какой портфель вложений будет: сколько акций и какой фирмы нам необходимо купить. Пример:
Есть завод, изготавливающий мебель. На заводе работает определенное количество работников, которые могут изготовить соответствующее кол-во определенной мебели (стулья, столы, шкафы и т.п.) Переменная выбора:
выбор того, сколько необходимо изготовить стульев или столов, чтобы хватило рабочей силы. Пример:
Участие в различных играх Переменная выбора здесь зависит от конкретной игры. Задачи 1 — 5 — это примеры задач оптимизации.
Комбинаторика:
Пример:
Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п. Пример:
Есть монеты разного достоинства, какими способами можно вернуть сдачу. Это краткое описание задач для динамического программирования, которые подробно будут рассмотрены позднее. Неформальное объяснение оптимальности подзадач ДП.
Рассмотрим неформальную
идею ДП. Итак, возьмем пример с заводом, изготавливающим мебель. Для достижения цели максимизации прибыли необходимо решить множество подзадач:
При большом количестве подзадач сложно понять, как решать такую задачу. Как правило, решить одну малую задачу проще, чем решить большую задачу
, состоящую из маленьких. Поэтому ДП предлагает следующее: Например, завод производит только стулья. У директора стоит задача получения максимальной прибыли с продажи стульев. Часто при постановке задачи кажущимся оптимальным решением является перебор всех возможных вариантов
. Однако, вследствии очень большого количества таких вариантов и, как результат, перегрузки памяти компьютера, такой способ не всегда приемлем. Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств? Дело в том, что: В основе динамического программирования лежит идея решения поставленной задачи путем деления ее на отдельные части (подзадачи, этапы), решение этих подзадач и последующего объединения этих решений в одно общее решение. Часто большинство из подзадач абсолютно одинаковы. При этом важно, что при решении более сложной задачи, мы не решаем заново маленькую подзадачу, а используем уже решенный ответ этой подзадачи.
Важно:
По этой причине разделение задачи на подзадачи и решение этих подзадач только один раз (!)
, сокращая этим количество общих вычислений — более оптимальный способ, который и заложен в динамическом программировании Когда мы решаем задачу с производными, множествами Ла-Гранжа и т.п., то мы работаем с непрерывными функциями. При решении же задач ДП мы будем работать в основном с дискретными функциями, поэтому говорить здесь о применении непрерывных функций неуместно. Рассмотрим вариант решения задачи с помощью динамического программирования. Пример:
Необходимо вычислить сумму n чисел: 1 + 2 + 3 + ... + n Попробуем применить к задаче идеи ДП и решить ее, разбивая на простые подзадачи. Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП. Рассмотрим еще один пример. Пример:
имеется лесенка из n ступенек, перед которой находится человек, который за 1
шаг умеет подниматься либо на следующую ступеньку, либо перепрыгивает через одну ступеньку. Вопрос: сколькими способами он может попасть на последнюю ступеньку? Рассмотрим самые простые варианты (подзадачи): Рассмотрим пример из i ступенек
Как мы можем попасть на i ступеньку: Например, как попасть на 4-ю ступеньку
: Т.о., общее количество способов
попасть на i ступеньку: Определим начальные значения
, с которых следует начинать решать задачу. Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности. Задание 1:
реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.
Дополните код:
var c:integer;
procedure getKolSposob(i,n: integer);
begin
writeln (i+n," ");
inc(c);
if ... then
getKolSposob(...,...)
end;
begin
c:=1;
getKolSposob(0,1);
end. Задание 2:
Создание стека индексов
Хорошо, математика - это красиво. А что с задачами, в которых не всё дано?
Идея решения
Реализация через рекурсию
private static int f(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
return f(n-1)+f(n-2)+f(n-3);
}
Там вверху ещё было написано про какую-то двумерную динамику?..
Идея решения
Реализация через рекурсию
Реализация через массив значений
int dp = new int;
for(int i=0; iОтлично, я всё понял. На чём мне проверить свои навыки?
Взрывоопасность
Решение
Реализация
Подъём по лестнице
Решение
Реализация
Калькулятор
Решение
Реализация
int N;
//Ввод с клавиатуры
int a = new int;
a= 0;
{
int min;
for(int i=2; iСамый дешёвый путь
Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.
- состояние, в которое процесс попадает из s i
в результате использования шагового управления u
. Пусть процесс находится в начальном состоянии s
0 . Выбор переводит процесс в состояние s
1 = σ(s
0 ,u
1), выбор - в состояние s
2 = σ(s
1 ,u
2) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар
(2.6)
(2.8)
(2.10)
s
i=3
i=2
i=1
x 3 (s)
W 3 (s)
x 2 (s)
W 2 (s)
x i (s)
W i (s)
4,27
4,27
7,64
7,64
10,25
10,97
15,93
15,93
16,12
19,26
19,26
s
x
s-x
p 2 (x)
W 3 (s-x)
p 2 (x)+W 3 (s-x)
W 2 (s)
4,27
4,27
4,27
3,33
3,33
7,64
7,64
7,64
3,33
4,27
7,6
4,87
4,87
10,25
10,25
10,97
3,33
7,64
10,97
4,87
4,27
9,14
5,26
5,26
15,93
15,93
15,93
3,33
10,25
13,58
4,87
7,64
12,51
5,26
4,27
9,53
7,34
7,34
16,12
16,12
19,26
3,33
15,93
19,26
4,87
10,25
15,12
5,26
7,64
12,9
7,34
4,27
11,61
9,49
9,49
s
x
s-x
p i (x)
W 2 (s-x)
p i (x)+W 2 (s-x)
Wi(s)
19,26
19,26
19,26
3,22
15,93
19,15
3,57
10,97
14,54
4,12
7,64
11,76
4,27
8,27
4,85
4,85
такое, чтобы результат, который достигается
за шаги сk
-го
по n
-й
оказался оптимальным. Числовая
характеристика этого результата
называется функцией Беллмана
и зависит от номера шага k
и состояния системы .
,
переводящее систему из начального
состояния
в
конечное состояние
,
при котором целевая функция
принимает наибольшее (наименьшее)
значение.
и значение функции Беллмана не сложно,
так как ,
где максимум берется по всем возможным
значениям
.
),
осуществляется второй этап решения
задачи. Находится оптимальное управление
на первом шаге
,
применение которого переведет систему
в состояние
,
зная которое можно, пользуясь результатами
условной оптимизации, найти оптимальное
управление на втором шаге, и так далее
до последнегоn
-го
шага.
Таким образом, американский математик и один из ведущих специалистов в области математики и вычислительной техники — Ричард Эрнст Беллман
— стал прородителем динамического программирования.
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.
Примеры, решаемых при помощи динамического программирования задач
Целевая функция:
максимизация средних
доходов, т.к. на бирже доход получается вероятностным путем, т.е. это статистический процесс, вероятностный.
Целевая функция
: максимизация прибыли.
Целевая функция:
максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.
Понятие динамического программирования
Формальная идея ДП
На графике это может выглядеть так:
По этой причине во многих задачах, но не во всех, применение аппарата математического анализа будет неприемлемым.Простой пример решения задач при помощи ДП
В чем состоит якобы «сложность» данной задачи: в том, что необходимо сразу взять большое количество чисел и получить ответ.
(В ДП всегда необходимо сначала определить начальные условия или условие)
F(1) = 1
F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
F(n) = F(n-1) + An
Итак, что мы сделали: определили порядок и вычленили подзадачи, затем решили каждую из них, опираясь на решение предыдущей.
Решение:
f(a i) = f(a i-1) + f(a i-2)
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи. 1
2
3
4
5
6
7
8
9
10
11
12
13
var
c:
integer
;
procedure
getKolSposob(i,
n:
integer
)
;
begin
writeln
(i+
n,
" "
)
;
inc(c)
;
if
...
then
getKolSposob(...,...
)
end
;
begin
c:
=
1
;
getKolSposob(0
,
1
)
;
end
.
Решение 15-го типа заданий ЕГЭ (Графы. Поиск количества путей).
