Динамическое программирование (обзор с примерами программных реализаций) - Реферат

«Этот подход дает нам возможность ставить и рассматривать такие задачи, которые не поддаются плодотворному изучению любыми другими методами». Выяснилось, что для решения многих задач оптимизации, включающих большое число переменных и ограничений в виде неравенства, классический аппарат математики оказался непригодным. И в результате пришла идея разбивать задачу большой размерности на подзадачи, включающих всего по несколько переменных, и последующего решения общей задачи по частям.Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах американским математиком Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В основе метода динамического программирования лежит принцип оптимальности: каково бы ни было состояние системы (S) в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. Как изменение самой системы во времени, так и процесс управления системой допускал разбивку по времени на этапы (шаги). Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага. Подзадачи решаются делением их на подзадачи еще меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же).Вот краткий их перечень: · Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность. · Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность. · Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую. · Задача о порядке перемножения матриц: даны матрицы A_1, …, A_n, требуется минимизировать количество скалярных операций для их перемножения.Этот объемный труд стал настоящей энциклопедией математических знаний того времени и сыграл важную роль в их распространении в странах Западной Европы в следующие несколько столетий. Спрашивается, сколько пар кроликов родится за год от одной пары, если кролики начинают приносить потомство со второго месяца и каждая пара через месяц производит на свет еще одну пару? Ее решение привело Фибоначчи к открытию едва ли ни самой знаменитой числовой последовательности 1, 1, 2, 3, 5, 8, 13, ... Как правило, записывается такая последовательность формулой: Очевидно, что данная задача имеет рекурсивное решение благодаря рекуррентной записи для вычисления элемента: F(n) = F(n-1) F(n-2). Пусть T(n) - количество операций, необходимых для вычисления n-го числа Фибоначчи, тогда в соответствии с алгоритмом для T(n) можно записать следующие соотношенияЧасто задача определяется как поиск всех наибольших подпоследовательностей. Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество ее элементов (возможно пустое). Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Существуют разные подходы при решении данной задачи, например, полный перебор.В главе 4 было доказано, что решать задачу по поиску n-го числа Фибоначчи эффективнее методом динамического программирования. Проведем несколько экспериментов. Результаты представлены в таблице и на графике. По результатам, представленным выше хорошо видно, что время вычисления с помощью динамического програ

Содержание

Введение

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

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

3. Краткий обзор задач динамического программирования

4. Реализация на примере задачи о вычислении чисел Фибоначчи

5. Реализация на примере задачи нахождения наибольшей общей последовательности

6. Эксперименты для определения вычислительной сложности

Выводы

Список литературы

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

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

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

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

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