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

Словосочетание «динамическое программирование» впервые было использовано в 1940;х годах американским математиком Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение. В основе метода динамического программирования лежит принцип оптимальности: каково бы ни было состояние системы (S) в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. [1] В 1950;х годах понятие «динамическое программирование» определяло раздел прикладной математики под названием «исследование операций». Круг исследуемых задач был достаточно четко обозначен. Это методы поиска оптимальных (наилучших) решений в задачах управления системами, но с одной, если так можно выразиться, особенностью. Как изменение самой системы во времени, так и процесс управления системой допускал разбивку по времени на этапы (шаги). Отсюда и термин «динамическое» — изменяющееся во времени. Но так можно представить (описать) практически любую систему управления. Особенность динамического программирования заключалась в том, что допускалась разбивка процесса на фиксированные промежутки времени и в целом оптимальное решение задачи как бы складывалось из оптимальных решений на каждом из промежутков (этапе, шаге). Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

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

В ходе дальнейшего развития, но уже не раздела прикладной математики, а информатики в целом с понятием «динамическое программирование» произошла некая трансформация. Оно очерчивает вполне определенный метод проектирования алгоритмов, который не ограничивается только задачами оптимизации. Естественно, этот метод не универсален, он работоспособен для вполне определенного класса задач. В идее разбивки задачи на подзадачи и компоновки решения задачи из решений подзадач нет ничего нового — это универсальный метод. Смысл (суть) заложен в интерпретации терминов «разбивка» и «компоновка». Задача должна допускать разбивку на подзадачи того же вида (типа) так, чтобы её решение как бы складывалось, компоновалось из решений подзадач. Другими словами, должны быть выведены (определены) функциональные зависимости (рекуррентные соотношения) между решениями подзадач. Тогда, начиная, например, с небольших задач, мы постепенно получаем решения все больших задач и наконец, доходим до решения исходной задачи. Особенность динамического программирования как метода заключается и в том, что каждая подзадача решается только один раз. Результат её решения запоминается и затем, при решении следующих подзадач, используется как данное. Итак, два ключевых момента: «связь» и «запоминание».

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

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