Оптимизация метода динамического программирования.

Краткое содержание лекции

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

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

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

Формальная формулировка задачи динамического программирования

n Дано:

u множество состояний

t в том числе начальное и конечное

u множество возможных переходов из одного состояния в другое

t с каждым переходом связывается числовой параметр

• интерпретируется как затраты, выгода, расстояние, время и т.п.

n Найти:

u оптимальную последовательность переходов (путь) из начального состояния в конечное

t максимум или минимум суммы числовых параметров

t предполагается, что хотя бы один путь из начального состояния в конечное существует

Пример. Найти оптимальный путь от узла 0 к узлу 18.

Принцип оптимальности Беллмана

n Если вершины A и B лежат на оптимальном пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B.

n Следствие

u Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A

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

Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования

История

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

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

Рис. Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру; прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь.

Рис. Граф подзадач (ребро означает, что одна задача зависит от решения другой) для чисел Фибоначчи (граф — ациклический).

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

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

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

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

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

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Примером является вычисление последовательности Фибоначчи, F ₃ = F ₂ + F ₁ и F ₄ = F ₃ + F ₂ – даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F ₂ дважды. Если продолжать дальше и посчитать F ₅, то F ₂ посчитается ещё два раза, так как для вычисления F ₅ будут нужны опять F ₃ и F ₄. В результате простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

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

• перекрывающиеся подзадачи;
• оптимальная подструктура;
• возможность запоминания решения часто встречающихся подзадач.

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

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

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

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

Классические задачи динамического программирования

• Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
• Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную неубывающую подпоследовательность.
• Задача о редакционном расстоянии (Расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
• Задача о вычислении чисел Фибоначчи
• Задача о порядке перемножения матриц: даны матрицы A ₁,..., A_n, требуется минимизировать количество скалярных операций для их перемножения.
• Задача о выборе траектории
• Задача последовательного принятия решения
• Задача об использовании рабочей силы
• Задача управления запасами
• Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
• Алгоритм Флойда-Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
• Алгоритм Беллмана – Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
• Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

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

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

2. Свести решение задачи для данного набора параметров к решению аналогичных подзадач для других наборов параметров (как правило, с меньшими значениями). Если задача несложная, то полезно бывает выписать явное рекуррентное соотношение, задающее значение функции для данного набора параметров.

3. Задать начальные значения функции, то есть те наборы аргументов, при которых задача тривиальна и можно явно указать значение функции.

4. Создать массив (или другую структуру данных) для хранения значений функции. Как правило, если функция зависит от одного целочисленного параметра, то используется одномерный массив, для функции от двух целочисленных параметров – двумерный массив и т. д.

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

Примеры задач, решаемых при помощи динамического программирования. Числа Фибоначчи

Определение. Последовательность Фибоначчи определяется следующим образом:

F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-2

Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci). Сам Фибоначчи упоминал эти числа в связи с такой задачей: " Человек посадил пару кроликов в загон, окруженный со всех сторон стеной. Сколько пар кроликов за год может произвести на свет эта пара, если известно, что каждый месяц, начиная со второго, каждая пара кроликов производит на свет одну пару? ". Решением этой задачи и будут числа последовательности, называемой теперь в его честь. Впрочем, описанная Фибоначчи ситуация – больше игра разума, чем реальная природа. Индийские математики Гопала и Хемачандра упоминали числа этой последовательности в связи с количеством ритмических рисунков, образующихся в результате чередования долгих и кратких слогов в стихах или сильных и слабых долей в музыке. Число таких рисунков, имеющих в целом n долей, равно F_n.

Интересен пример растения – тысячелистника, у которого число стеблей (а значит и цветков) всегда есть число Фибоначчи. Причина этого проста: будучи изначально с единственным стеблем, этот стебель затем делится на два, затем от главного стебля ответвляется ещё один, затем первые два стебля снова разветвляются, затем все стебли, кроме двух последних, разветвляются, и так далее, что и даёт в результате числа Фибоначчи. У многих цветов число лепестков является тем или иным числом Фибоначчи. Также в ботанике известно явление ''филлотаксиса''. В качестве примера можно привести расположение семечек подсолнуха: если посмотреть сверху на их расположение, то можно увидеть одновременно две серии спиралей (как бы наложенных друг на друга): одни закручены по часовой стрелке, другие – против. Оказывается, что число этих спиралей примерно совпадает с двумя последовательными числами Фибоначчи: 34 и 55 или 89 и 144. Аналогичные факты верны и для некоторых других цветов, а также для сосновых шишек, брокколи, ананасов, и т.д. Для многих растений (по некоторым данным, для 90% из них) верен и такой интересный факт. Рассмотрим какой-нибудь лист, и будем спускаться от него вниз до тех пор, пока не достигнем листа, расположенного на стебле точно так же (т.е. направленного точно в ту же сторону). Попутно будем считать все листья, попадавшиеся нам (т.е. расположенные по высоте между стартовым листом и конечным), но расположенными по-другому. Нумеруя их, мы будем постепенно совершать витки вокруг стебля (поскольку листья расположены на стебле по спирали). В зависимости от того, совершать витки по часовой стрелке или против, будет получаться разное число витков. Но оказывается, что число витков, совершённых нами по часовой стрелке, число витков, совершённых против часовой стрелки, и число встреченных листьев образуют 3 последовательных числа Фибоначчи. Числа Фибоначчи обладают множеством интересных математических свойств, некоторые из них:

· Соотношение Кассини: F_n+1F_n-1 – F_n² = (-1)ⁿ

· Правило " сложения": F_n+k = F_kF_n+1 + F_k-1F_n

· Из предыдущего равенства при k = n вытекает: F_2n = F_n(F_n+1 + F_n-1)

· Из предыдущего равенства по индукции можно получить, что F_nk всегда кратно F_n.

· Верно и обратное к предыдущему утверждение: если F_m кратно F_n, то m кратно n.

· НОД-равенство: gcd(F_m, F_n) = F_{gcd(m, n)}

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

Теорема Цекендорфа утверждает, что любое натуральное число n можно представить единственным образом в виде суммы чисел Фибоначчи:

N = F_k1 + F_k2 + … + F_kr, где k₁ ³ k₂ + 2, k₂ ³ k₃ + 2, ….

Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, причём ни в каком числе не могут идти две единицы подряд. Существует формула, называемая по имени французского математика Бине (Binet):

, следовательно

Нетрудно доказать матричное равенство:

Но тогда, обозначая

получаем: .

Таким образом, для нахождения n-го числа Фибоначчи надо возвести матрицу P в степень n. Так как возведение матрицы в n-ую степень можно осуществить за O(logn), получается, что n-ое число Фибоначчи можно легко вычислить за O(logn).

Рассмотрим последовательность Фибоначчи F_i по некоторому модулю p. Тогда она является периодичной, причём период начинается с F₁ = 1. Рассмотрим p² + 1 пар чисел Фибоначчи, взятых по модулю p: . Поскольку по модулю p может быть только p² различных пар, то среди этой последовательности найдётся как минимум две одинаковые пары. Это уже означает, что последовательность периодична. Выберем теперь среди всех таких одинаковых пар две одинаковые пары с наименьшими номерами. Пусть это пары с некоторыми номерами (F_a, F_a+1) и (F_b, F_b+1). Докажем, что a = 1. Действительно, в противном случае для них найдутся предыдущие пары (F_a-1, F_a) и (F_b-1, F_b), которые, по свойству чисел Фибоначчи, также будут равны друг другу. Однако это противоречит тому, что мы выбрали совпадающие пары с наименьшими номерами, что и требовалось доказать.

Задача. Вычислить N -ое число в последовательности Фибоначчи: 1, 1, 2, 3, 5, 8,...

Формат входных данных Одно число 0 < N < 47.

Формат выходных данных Одно число – N -ый член последовательности.

Решение

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

Самый очевидный способ “решения” задачи состоит в написании рекурсивной функции. При этом где-то в середине четвертого десятка программа “подвешивает” самый быстрый компьютер. Попробуем разобраться, почему так происходит? Для вычисления F(40) мы сперва вычисляем F(39) и F(38). Причем F(38) мы считаем “по новой”, “забывая”, что уже вычислили его, когда считали F(39). То есть наша основная ошибка в том, что значение функции при одном и том же значении аргумента считается много раз. Для исключения повторного счета следует хранить значения функции. Сначала массив заполняется значениями, которые заведомо не могут быть значениями функции. При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат. На этом уже можно остановиться, но можно еще более упростить решение, убрав рекурсию вообще. Для этого необходимо сменить нисходящую логику рассуждения на восходящую. В этой задаче такой переход очевиден и описывается простым циклом.

Примеры задач, решаемых при помощи динамического программирования. Черепашка

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

Формат входных данных Первая строка – N – размер доски. Далее следует N строк, каждая из которых содержит N целых чисел, представляющих доску.

Формат выходных данных Одно число – максимальная сумма.

Решение

Эта задача является классикой динамического программирования. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция F(X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение.

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

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

Примеры задач, решаемых при помощи динамического программирования. Подпалиндром

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

Формат входных данных Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.

Формат выходных данных В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.

Решение

Будем искать палиндромы для подстроки с i -го символа по j -ый включительно, то есть писать функцию F(I, J). Хотелось бы, что она возвращала сам палиндром, но это невозможно из-за нехватки памяти. Ограничимся одной длиной. Размещаем граничные случаи: F(I, I) = 1 и F(I, J) = 0, если I > J. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпалиндрома – тогда F (I, J) = F (I + 1, J). Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция K), тогда F(I, J) = 2 + F (I + 1, K – 1). Надо предусмотреть еще случай I = K, а затем отсекать рекурсию известным способом.

Примеры задач, решаемых при помощи динамического программирования. Наибольшая общая подпоследовательность. (НОП, Longest Common Subsequence, LCS)

Рассмотрим последовательность чисел a₁, a₂, …, a_n. Рассмотрим теперь еще одну последовательность b₁, b₂, …, b_m. Требуется найти длину самой длинной подпоследовательности последовательности {a_i}, которая одновременно является и подпоследовательностью последовательности {b_i}. Такую последовательность называют наибольшей общей подследовательностью (НОП). Например, для последовательностей 1, 2, 3, 4, 5 и 2, 7, 3, 2, 5 НОП является подпоследовательность 2, 3, 5, состоящая из трёх членов.