Динамическое программирование для начинающих. Всё, что вы хотели знать о динамическом программировании, но боялись спросить

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Классической задачей на последовательности является следующая.

Последовательность Фибоначчи F n задается формулами: F 1 = 1, F 2 = 1,
F n = F n - 1 + F n - 2 при n > 1. Необходимо найти F n по номеру n .

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

Int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); }
Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n , пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

Int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

F = 1; F = 1; for (i = 2; i < n; i++) F[i] = F + F;
Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F 3), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F i для i < n ), затем, зная решения подзадач, нашли ответ (F n = F n - 1 + F n - 2 , F n - 1 и F n - 2 уже найдены).

Одномерное динамическое программирование

Чтобы лучше понять суть динамического программирования, сначала более формально определим понятия задачи и подзадачи.

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n 1 , n 2 , ..., n k . То есть мы можем говорить о функции T (n 1 , n 2 , ..., n k ), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T (i 1 , i 2 , ..., i k ) при i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

Следующая задача одномерного динамического программирования встречается в различных вариациях.

При n < 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли K n - 1 , K n - 2 — число таких последовательностей длины n - 1 и n - 2.

Посмотрим, какой может быть последовательность длины n . Если последний ее символ равен 0, то первые n - 1 — любая правильная последовательность длины
n - 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего K n - 1 . Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n - 2 символа — любая правильная последовательность длины n - 2, число таких последовательностей равно K n - 2 .

Таким образом, K 1 = 2, K 2 = 3, K n = K n - 1 + K n - 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

Двумерное динамическое программирование

Классической задачей двумерного динамического программирования является задача о маршрутах на прямоугольном поле.
В разных формулировках необходимо посчитать число маршрутов или найти маршрут, который является лучшим в некотором смысле.

Приведем пару формулировок таких задач:

Задача 2. n *m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n *m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

Для всех таких задач характерным является то, что каждый отдельный маршрут не может пройти два или более раз по одной и той же клетке.

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i ,j ) можно прийти только сверху или слева, то есть из клеток с координатами (i - 1, j ) и (i , j - 1):

Таким образом, для клетки (i , j ) число маршрутов A[i][j] будет равно
A[j] + A[i], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A необходимо поместить число 1.

В задаче 3 в клетку с координатами (i , j ) мы можем попасть из клеток с координатами
(i - 1, j), (i , j - 1) и (i - 1, j - 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[j], W[i],
W. Чтобы найти минимальный вес для (i , j ), необходимо выбрать минимальный из весов W[j], W[i], W и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[j], W[i], W) + A[i][j];

Данная задача осложнена тем, что необходимо найти не только минимальный вес, но и сам маршрут. Поэтому в другой массив мы дополнительно для каждой клетки будем записывать, с какой стороны в нее надо попасть.

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.

После прохождения всего массива необходимо будет проследить сам маршрут из последней клетки, следуя по стрелкам в обратную сторону.

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i . Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k - 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k - 1. Если
A[i] < A[k], то k -ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k - 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 <= i < k .

Здесь максимум из пустого множества будем считать равным 0. В этом случае текущий элемент станет единственным в выбранной последовательности, а не будет продолжением одной из предыдущих. После заполнения массива L длина наибольшей возрастающей подпоследовательности будет равна максимальному элементу L.

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L = 1, а перед ним нет ни одного — N = 0. Далее,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

Меньше A = 5 только элемент A = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
L = L + 1 = 2, N = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

Еще одной классической задачей динамического программирования является задача о палиндромах.

Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.

Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n . Будем рассматривать возможные подстроки данной строки с i -го по j -ый символ, обозначим их через S (i , j ). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S (i , j ).

Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S (i , i )) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S (i , i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

Пусть теперь нам дана подстрока S (i , j ). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S (i , j - 1) или S (i + 1, j ) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i], L[j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S (i + 1, j - 1):
L[i][j] = L + 2.

Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S (i , i ) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S (4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L — 2.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L = L + 2. В остальных подстроках первая и последняя буквы различны.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

Если же в задаче необходимо вывести не длину, а сам палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован (на рисунке для наглядности вместо числовых значений, кодирующих переходы, нарисованы соответствующие стрелки).

Суть метода динамического программирования………………………..4

Пример решения задачи методом динамического программирования………………………………………………………...7

Список используемых источников……………………………………...11

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

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

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.

Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы. В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для применения в коммерческой деятельности при решении как линейных, так и нелинейных задач.

Динамическое программирование является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами динамического программирования решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах динамического программирования эти зависимости могут иметь еще и нелинейный характер. Динамическое программирование можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения динамического программирования для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариантов, увеличивает достоинства этого комплекса методов.

Вместе с тем динамическому программированию свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний.

Для процессов с непрерывным временем динамическое программирование рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.

Динамическое программирование применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети; формирование последовательности развития коммерческой операции и т. д.

), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

Метод динамического программирования сверху - это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.

История

Словосочетание «динамическое программирование» впервые было использовано в -х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE . Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

Слово «программирование» в словосочетании «динамическое программирование» в действительности к "традиционному" программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Идея динамического программирования

Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру; прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь.

Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

Разбиение задачи на подзадачи меньшего размера.
Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм .
Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , и - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то посчитается ещё два раза, так как для вычисления будут нужны опять и . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.

Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование . Можно проделывать и дальнейшие оптимизации - например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.

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

перекрывающиеся подзадачи;
оптимальная подструктура;
возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Perl), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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

Классические задачи динамического программирования

Литература

Беллман Р. Динамическое программирование. - М.: Изд-во иностранной литературы, 1960.
Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. - 2-е изд. - М .: Вильямс, 2005. - 1296 с. - ISBN 5-8459-0857-4
Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms = Algorithms. - 1-е изд. - McGraw-Hill Science/Engineering/Math, 2006. - С. 336. - ISBN 0073523402
Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9 .
Bertele U., Brioshi F. Nonserial dynamic programming. - N.Y.: Academic Press, 1972. - 235 pp.
Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19.
Щербина О. А. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22. - c.21-36.
Габасов Р., Кириллова Ф. М. Основы динамического программирования. - Мн.: Изд-во БГУ, 1975. - 262 с.

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое "Динамическое программирование" в других словарях:

динамическое программирование - — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] динамическое программирование Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные … Справочник технического переводчика

Динамическое программирование - раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.… … Экономико-математический словарь

Раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления. В Д. п. для управляемых процессов среди всевозможных управлений ищется то, к рое доставляет экстремальное (наименьшее или наибольшее) значение… … Математическая энциклопедия

Раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления (См. Оптимальное управление). В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет… … Большая советская энциклопедия

динамическое программирование - dinaminis programavimas statusas T sritis automatika atitikmenys: angl. dynamic programming vok. dynamische Programmierung, f rus. динамическое программирование, n pranc. programmation dynamique, f … Automatikos terminų žodynas

Раздел математич. программирования, изучающий многошаговые процессы поиска оптим. решения сложных задач. Применяется при составлении программ решения таких задач оптимизации, для к рых процесс поиска решения можно представить в виде нек рой… … Большой энциклопедический политехнический словарь

Последовательности

Классической задачей на последовательности является следующая.

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

Одномерное динамическое программирование

Следующая задача одномерного динамического программирования встречается в различных вариациях.

Двумерное динамическое программирование

Приведем пару формулировок таких задач:

W[i][j] = min(W[j], W[i], W) + A[i][j];

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Еще одной классической задачей динамического программирования является задача о палиндромах.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

В рассмотренных выше моделях управленческих задач не учитывался время. Это так называемые одноэтапные модели, которые позволяют анализировать статические, не зависящие от времени процессы, допустим, когда изменениями исследуемого процесса во времени можно пренебречь. Управленческое решение по такого моделирования имеет смысл или в условиях стабильности системы, или на короткий промежуток в будущем.

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

Динамическое программирование - это математический аппарат, с помощью которого решаются многошаговые задачи оптимального управления. В таком программировании для управления процессом среди множества всех допустимых решений ищут оптимальное в смысле определенного критерия, то есть такое решение, которое дает экстремальное (больше или меньше) значения целевой функции - некоторой числовой характеристики процесса. Во многостепенность понимают или многоступенчатую структуру процесса, или распределение управления на ряд последовательных этапов, соответствующих, как правило, различным моментам времени. Таким образом, слово "программирование" означает принятие управленческих решений, а слово "динамическое" указывает на существенное значение времени и порядка выполнения операций в процессах и методах, которые рассматриваются.

В задачи динамического программирования относятся задачи календарного планирования, распределения инвестиций, управление запасами, текущего и капитального ремонта, выбора методов проведения рекламы и тому подобное.

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

Рассмотрим общую постановку задачи этого программирования. Пусть исследуется некоторый экономический процесс, имеющий п последовательных этапов. На каждом 7-м этапе процесс может быть в разных состояниях бы, каждый из которых характеризуется конечным множеством параметров. С каждым этапом задачи связано принятие определенного управленческого решения хи, которое переводит систему из одного состояния в другое. Предполагается, что состояние si системы в конце 7-го этапа определяется только предыдущим состоянием si_1 и управлением хи на 7-м этапе и не зависит от предыдущих состояний и управлений. Тогда состояние si системы записывается в виде зависимости

Si = ф (в, _!, Хи), i = 1, П.

Эффективность всего процесса управления может быть представлена как сумма эффективностей управленческих решений отдельных этапов, то есть

При названных условиях задача динамического программирования формулируется так: определить такую допустимую последовательность управленческих решений X = {x1, x2, хп}, которая переводит систему из начального состояния 50 в завершающий состояние sn и при которой достигается максимальная эффективность управления.

Планируя многоэтапный процесс управления, в задачах динамического программирования необходимо на каждом этапе выбирать управленческое решение с учетом его последствий на тех этапах, которые еще впереди. Только на последнем этапе можно принять управленческое решение, которое даст максимальный эффект, поскольку следующий шаг для него не существует. Поэтому задачи динамического программирования решаются с конца.

Максимум целевой функции на заключительном п-м этапе равна

^ п-О = шах / п ^ п-и хп).

Соответственно, на (п - 1) -етапи имеем

г * п-1 (5п-2) = ШaХ ((fn-1 (sn-2, хп-1) + г * п ^ п-1)).

Учитывая эту закономерность, для произвольного k-этапа можем записать рекуррентную зависимость

г * (пятый-1) = Шахи (Л (ик-1, хк) + г * + 1)).

Такая рекуррентная зависимость представляет собой математическую запись принципа оптимальности Беллмана.

Определив по рекуррентными зависимостями условно-оптимальный эффект на начальном этапе, проводят безусловную оптимизацию управления в "обратном" направлении, в результате чего находят последовательность управленческих решений, обеспечивает максимальную эффективность системы в целом.

Основные особенности метода динамического программирования

1. Идея и метод динамического программирования больше приспособлены к дискретных задач, которыми в большинстве являются задачи управления.

2. Метод динамического программирования можно применять при любом способа задания целевой функции и с любой допустимой множеством состояний и управлений. Этого преимущества лишены классические методы оптимизации и другие вычислительные методы математического программирования.

3. Вычислительные схемы метода динамического программирования в дискретном случае связанные с переборкой оптимальных значений показателя эффективности и управления на к-м шаге для всех возможных значений переменной состояния, но объем расчетов при этом значительно меньше, чем при прямом переборки вариантов. Это связано с тем, что на этапе условной оптимизации неудачные варианты сразу отбрасываются, а сохраняются лишь условно оптимальные на данном этапе.

4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных состояний sk и их количества п. Фактически здесь на каждом шагу решается не одна задача, а множество однотипных задач для различных состояний sk и различных к (1 <к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

Выводы

1. Появление нелинейных моделей связана с необходимостью учитывать и проявлять нелинейные закономерности, которые влияют на принятие оптимального решения. Такие закономерности включаются в ограничения задачи и целевую функцию.

2. По характеру функций и ограничений, которыми описываются задачи нелинейного программирования, их можно классифицировать следующим образом: классические задачи оптимизации; задачи с нелинейной целевой функцией и линейными ограничениями; задачи выпуклого, квадратичного, сепарабельного программирования.

3. В отличие от задач линейного программирования, для решения нелинейных задач не существует универсального метода. В каждом конкретном случае необходимо выбирать лучший метод.

4. Динамическое программирование - это математический аппарат, с помощью которого решаются многошаговые задачи оптимального управления. Во многостепенность понимают или многоступенчатую структуру процесса, или распределения управления на ряд последовательных этапов, соответствующих, как правило, различным моментам времени.

5. В задачи динамического программирования относятся задачи календарного планирования, распределения инвестиций, управление запасами, текущего и капитального ремонта, выбора методов проведения рекламы и тому подобное. Особенность всех задач динамического программирования заключается в том, что на каждом этапе можно учитывать предыдущие изменения и управлять ходом событий, оценивая при этом качество такого управления.

6. Решение задач динамического программирования базируется на принципе оптимальности Беллмана. В процессе оптимизации управления методом динамического программирования многошаговый процесс выполняется дважды. Первый раз - от конца к началу, в результате чего находят условно оптимальные управления. Второй - от начала до конца, в результате чего находят оптимальное управление процессом в целом.