Размещено на http://www.allbest.ru/

Федеральное государственное автономное образовательное учреждение высшего образования

«Санкт-Петербургский политехнический университет Петра Великого»

Высшая инженерная школа

Реферат

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

по дисциплине «Структуры и алгоритмы компьютерной обработки данных»

Выполнил С.Н. Дроздов

Руководитель В.Г. Пак

Санкт-Петербург 2016



Содержание

• Введение
• 1. Понятие динамического программирования
• 2. Идея динамического программирования
• 3. Краткий обзор задач динамического программирования
• 4. Реализация на примере задачи о вычислении чисел Фибоначчи
• 5. Реализация на примере задачи нахождения наибольшей общей последовательности
• 6. Эксперименты для определения вычислительной сложности
• Выводы
• Список литературы


Введение

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

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

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

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

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



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

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

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

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

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

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

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

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

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

1. Разбиение задачи на подзадачи меньшего размера.

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

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

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

F(3) = F(2) + F(1) и F(4) = F(3) + F(2)

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

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

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

· перекрывающиеся подзадачи;

· оптимальная подструктура;

· возможность запоминания решения часто встречающихся подзадач.

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

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

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

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

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

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

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



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

Методом динамического программирования решается очень много задач. Вот краткий их перечень:

· Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.

· Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.

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

· Задача о вычислении чисел Фибоначчи

· Задача о порядке перемножения матриц: даны матрицы A_1, …, A_n, требуется минимизировать количество скалярных операций для их перемножения.

· Задача о выборе траектории

· Задача последовательного принятия решения

· Задача об использовании рабочей силы

· Задача управления запасами

· Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

· Алгоритм Флойда -- Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

· Алгоритм Беллмана -- Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

· Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

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

В 1202 г. появилась на свет знаменитая «Книга абака» Леонардо Пизанского (более известного под прозвищем Фибоначчи - сын Боначчи), крупнейшего европейского математика эпохи Средневековья. Этот объемный труд стал настоящей энциклопедией математических знаний того времени и сыграл важную роль в их распространении в странах Западной Европы в следующие несколько столетий. Наиболее известной по сей день остается, конечно же, задача о размножении кроликов, впервые появившаяся в «Liber abaci». Спрашивается, сколько пар кроликов родится за год от одной пары, если кролики начинают приносить потомство со второго месяца и каждая пара через месяц производит на свет еще одну пару? Ее решение привело Фибоначчи к открытию едва ли ни самой знаменитой числовой последовательности 1, 1, 2, 3, 5, 8, 13, ... , названной впоследствии его именем и породившей множество исследований

Числа Фибоначчи являются элементами числовой последовательности, где каждое последующее число образуется посредством суммирования двух предыдущих, например: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…. Как правило, записывается такая последовательность формулой:

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



F(n) = F(n-1) + F(n-2).

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

F(4)=F(3)+F(2) и F(3)=F(2)+F(1)

следует, что для вычисления F(4) значение F(2) приходится вычислять дважды.

Найдем сложность рекурсивного алгоритма вычисления значения n-го числа Фибоначчи.

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

Здесь с₁ и с₂ количество операций для проверки условия и сложения двух чисел.

Будем искать решение в виде T(n) = xⁿ, при n > 1. Это позволяет переписать уравнение в виде

xⁿ = x^n-1 + x^n-2+c₂

Разделим на xⁿ и, переходя к пределу при с учетом того, что , находим



1 = x^-1 + x^-2

Разрешая уравнение относительно x, получаем два решения . Поскольку все члены последовательности неотрицательны, то следует рассмотреть только положительный корень. Решение можно записать в виде T(n) = xⁿ, при n > 1, откуда следует, что T(n) = O(xⁿ). Полученный результат говорит о том, что данный алгоритм не является эффективным.

Проведем разбор решения поставленной задачи с использованием динамического программирования. Пусть исходная задача T - это вычисление n-го элемента ряда Фибоначчи. В качестве последовательности подзадач Ti выберем последовательность задач F(i), которые сводятся к вычислению i-го члена ряда. Тогда T1 и T2 нам известны (T1 = T2 = 1), а Tn - это как раз поставленная выше задача. Каждая задача Ti легко может решаться через предшествующие ей задачи: Ti = Ti-1 + Ti-2 (для i=3..n). Поэтому последовательно вычисляя значение Ti мы линейным алгоритмом найдем и последний искомый элемент Tn.

T(n) = c₂(n-1) + c₁ = O(n),

где с₁ - количество действий для выполнения алгоритма, с₂ - количество шагов для каждой итерации цикла.

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

Автоматизируем вычисление чисел Фибоначчи с помощью языка программирования С++.

Реализуем для сравнения скорости работы оба способа вычисления - рекурсивный и динамическим программированием. Коды программы представлены на рисунках 1 и 2.

Рис. 1. Рекурсивный способ

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

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



Рис. 3. Выполнение программы.

Рис. 4. Выполнение программы.

Результаты тестирования представлены в параграфе 6.

динамический программирование вычислительный автоматизация



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

Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) -- задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y.

Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.

Существуют разные подходы при решении данной задачи, например, полный перебор.

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

Решим задачу методом динамического программирования.

Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n₁, n₂), где n₁, n₂ -- длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m₁, m₂), меньших заданной. Тогда задача (n₁, n₂) сводится к меньшим подзадачам следующим образом:

		A	B	C	B
	0	0	0	0	0
D	0	< 0	< 0	< 0	< 0
C	0	< 0	< 0	? 1	< 1
B	0	< 0	? 1	< 1	? 2
A	0	? 1	< 1	< 1	^ 2

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

:

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

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

Очевидно, что время работы алгоритма будет Время работы алгоритма будет O(n₁*n₂).

Алгоритм поиска реализуем на языке программирования С++ и проведем эксперименты.

Рис. 5. Реализация алгоритма.

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



Рис. 6. Выполнение программы.

Рис. 7. Выполнение программы.

Результаты тестирования представлены в параграфе 6.



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

В главе 4 было доказано, что решать задачу по поиску n-го числа Фибоначчи эффективнее методом динамического программирования. Проведем несколько экспериментов.

Рис 6.1. Работа программы

Результаты представлены в таблице и на графике.

Таб. 6.1. Таблица результатов вычисления числа Фибоначчи.



Рис. 6.2. График результатов вычисления числа Фибоначчи.

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

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

Размер последовательности	5	10	15	20	25
Время поиска, мс	5583	10063	12655	18751	22734



Выводы

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

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

· Задача имеет перекрывающиеся подзадачи, т. е. при рекурсивном решении мы многократно выходим на одни и те же подзадачи.

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



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

1. Р. Беллман «Динамическое программирование». Изд-во иностранной литературы, 1690.

2. Р. Беллман, С. Дрейфус «Прикладные задачи динамического программирования». М., Наука. Главная редакция Физико-математической литературы, 1965.

3. С М. Окулов, О. А. Пестов «Динамическое программирование». Москва БИНОМ. Лаборатория знаний 2012.

4. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972.

5. Х. Абельсон, Д. Д. Сассман «Структура и интерпретация компьютерных программ», Добросвет, 2006.

Размещено на Allbest.ru

...