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

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

Содержание

Содержание 1
Введение 2
1.Понятие динамического программирования 3
2.Идея динамического программирования 5
3.Краткий обзор задач динамического программирования 7
4.Реализация на примере задачи о вычислении чисел Фибоначчи 8
Выводы 11
Список литературы 12

Введение

«Этот подход дает нам возможность ставить и рассматривать такие задачи, которые не поддаются плодотворному изучению любыми другими методами». [1] Р. Э. Беллман

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

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

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

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

2.