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

Суть метода динамического программирования………………………..4

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

Список используемых источников……………………………………...11

1. Динамическое программирование. Основные понятия.

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

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

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

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

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

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

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

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

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Классической задачей на последовательности является следующая.

Последовательность Фибоначчи F n задается формулами: F 1 = 1, F 2 = 1,
F n = F n - 1 + F n - 2 при n > 1. Необходимо найти F n по номеру n .

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

Int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); }
Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n , пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

Int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

F = 1; F = 1; for (i = 2; i < n; i++) F[i] = F + F;
Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F 3), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F i для i < n ), затем, зная решения подзадач, нашли ответ (F n = F n - 1 + F n - 2 , F n - 1 и F n - 2 уже найдены).

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

Чтобы лучше понять суть динамического программирования, сначала более формально определим понятия задачи и подзадачи.

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n 1 , n 2 , ..., n k . То есть мы можем говорить о функции T (n 1 , n 2 , ..., n k ), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T (i 1 , i 2 , ..., i k ) при i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

Следующая задача одномерного динамического программирования встречается в различных вариациях.

При n < 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли K n - 1 , K n - 2 — число таких последовательностей длины n - 1 и n - 2.

Посмотрим, какой может быть последовательность длины n . Если последний ее символ равен 0, то первые n - 1 — любая правильная последовательность длины
n - 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего K n - 1 . Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n - 2 символа — любая правильная последовательность длины n - 2, число таких последовательностей равно K n - 2 .

Таким образом, K 1 = 2, K 2 = 3, K n = K n - 1 + K n - 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

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

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

Приведем пару формулировок таких задач:

Задача 2. n *m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n *m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

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

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i ,j ) можно прийти только сверху или слева, то есть из клеток с координатами (i - 1, j ) и (i , j - 1):

Таким образом, для клетки (i , j ) число маршрутов A[i][j] будет равно
A[j] + A[i], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A необходимо поместить число 1.

В задаче 3 в клетку с координатами (i , j ) мы можем попасть из клеток с координатами
(i - 1, j), (i , j - 1) и (i - 1, j - 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[j], W[i],
W. Чтобы найти минимальный вес для (i , j ), необходимо выбрать минимальный из весов W[j], W[i], W и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[j], W[i], W) + A[i][j];

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

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.

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

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i . Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k - 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k - 1. Если
A[i] < A[k], то k -ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k - 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 <= i < k .

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

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L = 1, а перед ним нет ни одного — N = 0. Далее,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

Меньше A = 5 только элемент A = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
L = L + 1 = 2, N = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

Еще одной классической задачей динамического программирования является задача о палиндромах.

Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.

Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n . Будем рассматривать возможные подстроки данной строки с i -го по j -ый символ, обозначим их через S (i , j ). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S (i , j ).

Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S (i , i )) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S (i , i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

Пусть теперь нам дана подстрока S (i , j ). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S (i , j - 1) или S (i + 1, j ) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i], L[j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S (i + 1, j - 1):
L[i][j] = L + 2.

Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S (i , i ) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S (4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L — 2.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L = L + 2. В остальных подстроках первая и последняя буквы различны.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

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

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

Происхождение термина

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

Алгоритм (метод) решения многоэтапных задач

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

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

Метод сверху и метод снизу

Несмотря то что при расчете на отдельном этапе решения задачи используются параметры процесса на текущий момент, результат оптимизации на предыдущем этапе влияет на расчеты последующих этапов для достижения наилучшего результата в целом. Динамическое программирование называет такой принцип решения методом оптимальности, который определяет, что оптимальная стратегия решения задачи вне зависимости от начальных решений и условий должна последующими решениями на всех этапах составить оптимальную стратегию относительно первоначального состояния. Как видим, процесс решения задачи представляет собой непрерывную оптимизацию результата на каждом отдельном этапе от первого до последнего. Такой метод называется методом программирования сверху. На рисунке схематически показан алгоритм решения сверху вниз. Но существует класс многошаговых задач, в которых максимальный эффект на последнем этапе уже известен, например, мы уже приехали из пункта А в пункт Б и теперь хотим узнать, правильно мы ехали на каждом предыдущем этапе или можно было что-то сделать более оптимально. Возникает рекурсивная последовательность этапов, т. е. мы идем как бы «от обратного». Этот метод решения получил название "метод программирования снизу".

Практическое применение

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

Поиск оптимального пути

С помощью динамической оптимизации возможно решение широкого класса задач по нахождению или оптимизации кратчайшего пути и других задач, в которых «классический» метод перебора возможных вариантов решения приводит к увеличению времени расчета, а иногда вообще неприемлем. Классическая задача динамического программирования - это задача о рюкзаке: дано некоторое количество предметов с определенной массой и стоимостью, и необходимо выбрать набор предметов с максимальной стоимостью и массой, не превосходящий объем рюкзака. Классический перебор всех вариантов в поисках оптимального решения займет значительное время, а с помощью динамических методов задача решается в приемлемые сроки. Задачи поиска кратчайшего пути для транспортной логистики являются основными, и динамические методы решения оптимально подходят для их решения. Наиболее простым примером такой задачи является построение кратчайшего маршрута автомобильным GPS-навигатором.

Производство

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

Научная сфера

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

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

Это значит, что если взять вектор и умножить его на матрицу перехода n - 1 раз, то получим вектор , в котором лежит fib[n] - ответ на задачу.

А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .

Это хорошо тем, что теперь можно применить метод быстрого возведения в степень , который работает за . Итого мы сумели посчитать N -ое число Фибоначчи за логарифм арифметических операций.

А теперь пример посерьёзнее:

Пример №3: Пилообразная последовательность

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

Решение

Для начала решение без матрицы перехода:

1) Состояние динамики: dp[n] - количество пилообразных последовательностей длины n , заканчивающихся на цифру last . Причём если less == 0 , то последняя цифра меньше предпоследней, а если less == 1 , значит больше.
2) Начальные значения:
for last in range(10): dp = 9 - last dp = last 3) Пересчёт динамики:
for prev in range(10): if prev > last: dp[n] += dp if prev < last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Ответ - это сумма dp[N] .

Теперь надо придумать начальный вектор и матрицу перехода к нему. Вектор, кажется, придумывается быстро: все состояния, обозначающие длину последовательности N . Ну а матрица перехода выводится, смотря на формулы пересчёта.

Вектор и матрица перехода

Динамика по подотрезкам

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

Пример №4: Запаковка строки

Вот Развернутое условие . Я вкратце его перескажу:

Определим сжатую строку:
1) Строка состоящая только из букв - это сжатая строка. Разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B . Разжимается она в конкатенацию разжатых строк A и B .
3) Строка D(X) , где D - целое число, большее 1 , а X - сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X .
Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC” .

Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.

Решение

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

1) Состояние динамики: d[l][r] - сжатая строка минимальной длины, разжимающаяся в строку s
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.

Dp_len = r - l dp[l][r] = dp_len # Первый вариант сжатия - просто строка. for i in range(l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Попробовать разделить на две сжатые подстроки for cnt in range(2, dp_len): if (dp_len % cnt == 0): # Если не делится, то нет смысла пытаться разделить good = True for j in range(1, (dp_len / cnt) + 1): # Проверка на то, что все cnt подстрок одинаковы good &= s == s if good: # Попробовать разделить на cnt одинаковых подстрок и сжать dp[l][r] = min(dp[l][r], len(str(cnt)) + 1 + dp[l] + 1) 4) Порядок пересчёта: прямой по возрастанию длины подстроки или ленивая динамика.
5) Ответ лежит в d .

Пример №5:

Динамика по поддеревьям

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

Пример №6: Логическое дерево

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

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

Решение

1) Состояние динамики: d[v][x] - количество операций, требуемых для получения значения x в вершине v . Если это невозможно, то значение состояния - +inf .
2) Начальные значения: для листьев, очевидно, что своё значение можно получить за ноль изменений, изменить же значение невозможно, то есть возможно, но только за +inf операций.
3) Формула пересчёта:
Если в этой вершине уже значение x , то ноль. Если нет, то есть два варианта: изменить в текущей вершине операцию или нет. Для обоих нужно найти оптимальный вариант и выбрать наилучший.

Если операция «И» и нужно получить «0», то ответ это минимум из значений d[i] , где i - сын v .
Если операция «И» и нужно получить «1», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «0», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «1», то ответ это минимум из значений d[i] , где i - сын v .

4) Порядок пересчёта: легче всего реализуется лениво - в виде поиска в глубину из корня.
5) Ответ - d xor 1] .

Динамика по подмножествам

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

Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера

Задан взвешенный (веса рёбер неотрицательны) граф G размера N . Найти гамильтонов цикл (цикл, проходящий по всем вершинам без самопересечений) минимального веса.

Решение

Так как мы ищем цикл, проходящий через все вершины, то можно выбрать за «начальную» вершину любую. Пусть это будет вершина с номером 0 .

1) Состояние динамики: dp[v] - путь минимального веса из вершины 0 в вершину v , проходящий по всем вершинам, лежащим в mask и только по ним.
2) Начальные значения: dp = 0 , все остальные состояния изначально - +inf .
3) Формула пересчёта: Если i -й бит в mask равен 1 и есть ребро из i в v , то:
dp[v] = min(dp[v], dp[i] + w[i][v]) Где w[i][v] - вес ребра из i в v .
4) Порядок пересчёта: самый простой и удобный способ - это написать ленивую динамику, но можно поизвращаться и написать перебор масок в порядке увеличения количества единичных битов в ней.
5) Ответ лежит в d[(1 << N) - 1] .

Динамика по профилю

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

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

Профиль - это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.

Почти всегда состояние - это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can - можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти - больше.

Пример №8: Замощение доминошками

Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1 .

Решение

Здесь профиль - это один столбец. Хранить его удобно в виде двоичной маски: 0 - не замощенная клетка столбца, 1 - замощенная. То есть всего профилей .

0) Предподсчёт (опционально): перебрать все пары профилей и проверить, что из одного можно перейти в другой. В этой задаче это проверяется так:

Если в первом профиле на очередном месте стоит 1 , значит во втором обязательно должен стоять 0 , так как мы не сможем замостить эту клетку никакой фигуркой.

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

Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):

После этого сохранить всё в массив can - 1 , если можно перейти, 0 - если нельзя.
1) Состояние динамики: dp - количество полных замощений первых pos - 1 столбцов с профилем mask .
2) Начальное состояние: dp = 1 - левая граница поля - прямая стенка.
3) Формула пересчёта:
dp += dp * can
4) Порядок обхода - в порядке увеличения pos .
5) Ответ лежит в dp.

Полученная асимптотика - .

Динамика по изломанному профилю

Это очень сильная оптимизация динамики по профилю. Здесь профиль - это не только маска, но ещё и место излома. Выглядит это так:

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

Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):

Восстановление ответа

Иногда бывает, что просто знать какую-то характеристику лучшего ответа недостаточно. Например, в задаче «Запаковка строки» (пример №4) мы в итоге получаем только длину самой короткой сжатой строки, но, скорее всего, нам нужна не её длина, а сама строка. В таком случае надо восстановить ответ.

В каждой задаче свой способ восстановления ответа, но самые распространенные:

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

Небольшие оптимизации

Память

Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода - ленивая динамика.

Время

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

Замена состояния

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

Пример №9: Разложение числа

Требуется найти количество разложений числа N на различные слагаемые. Например, если N = 7 , то таких разложений 5:

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

Раздел Динамическое программирование представлен следующими калькуляторами:

1. Задача распределения инвестиций . Для реконструкции и модернизации производства на четырех предприятиях выделены денежные средства С = 80 ден. ед. По каждому предприятию известен возможный прирост f i (х) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы.

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

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

Рассмотрим общее описание задачи динамического программирования .
Пусть многошаговый процесс принятия решений разбивается на n шагов. Обозначим через ε 0 – начальное состояние системы, через ε 1 , ε 2 , … ε n – состояния системы после первого, второго, n -го шага. В общем случае состояние ε k – вектор (ε k 1 , …, ε k s ).
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) u k = (u k 1 , ..., u k r ), принимаемых на каждом шаге k и переводящих систему из состояния ε k -1 = (ε k- 1 1 , …, ε k -1 s ) в состояние ε k = (ε k 1 , …, ε k s ).
В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Например, выпуск продукции любым предприятием – управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т. д. Совокупность решений, принимаемых в начале года, планируемого периода, по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т. д. является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов. Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т. е. по периодам времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.
Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т. д.). Под этапом обычно понимают хозяйственный год.
Обычно на управление на каждом шаге u k накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Предполагая, что показатель эффективности k -го шага процесса зависит от начального состояния на этом шаге k -1 и от управления на этом шаге u k , получим целевую функцию всего многошагового процесса в виде:
.

Сформулируем теперь задачу динамического программирования : «Определить совокупность допустимых управлений (u 1 , …, u n ), переводящих систему из начального состояния ε 0 в конечное состояние ε n и максимизирующих или минимизирующих показатель эффективности F ».
Управление, при котором достигается максимум (минимум) функции F называется оптимальным управлением u * = (u 1* ,…, u n *).
Если переменные управления u k принимают дискретные значения, то модель ДП называется дискретной . Если переменные u k изменяются непрерывно, то модель ДП называется непрерывной .
В зависимости от числа параметров состояния s и числа управляющих переменных r различают одномерные и многомерные задачи ДП.
Число шагов в задаче может быть конечным или бесконечным .

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

1. задача о планировании строительства объектов.