Динамическое программирование
Материал из Википедии — свободной энциклопедии
Динамическое программирование (ДП) — это вычислительный метод для эффективного решения задач с пересекающимися подзадачами. Возникло и сформировалось в 1950 — 1953 гг. благодаря работам Р. Беллмана.
[править] Идея динамического программирования
Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении исходного результата. Для решения подзадач этот же алгоритм применяется рекурсивно. При этом для каждой подзадачи запоминается вычисленный ответ, и если на каком-то шаге встретилась подзадача второй раз, то вычисления для нее не производятся. За счет большого количества пересекающихся подзадач это значительно уменьшает время работы.
Если множество подзадач имеет простую структуру и имеется некоторый параметр p, который уменьшается при разбиении на подзадачи, то можно применять динамическое программирования, не используя рекурсию: для этого в начале нужно вычислить ответ для всех подзадач с наименьшим p, затем для всех подзадач со вторым по величине p и.т.д. пока не вычислим ответ для исходной задачи.
Известны сериальное динамическое программирование, включенное во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах. Отметим, что обычное ДП является частным случаем несериального ДП (НСДП), когда граф взаимосвязей переменных - просто путь. НСДП [2, 3], являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причем эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объем вычислений на каждом этапе может сохраняться в разумных пределах.
[править] Классические задачи динамического программирования
- Задача о выборе траектории
- Задача последовательного принятия решения
- Задача об использовании рабочей силы
- Задача управления запасами
- Задача о ранце
- Задача поиска кратчайшего пути в сети
1. Беллман Р. Динамическое программирование. - М.: Издательство иностранной литературы, 1960.
2. Bertele U., Brioshi F. Nonserial dynamic programming. - N.Y.: Academic Press, 1972. – 235 pp.
3. Щербина О.А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19.
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
