Динамическое программирование оптимальное управление примеры. Суть методов динамического программирования. Самый дешёвый путь

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

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

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X . Переменная определяет, в каких состояниях может оказаться система на данном k -м шаге. В зависимости от на этом шаге можно применить некоторые управления, которые характеризуются переменной . Применение управления на k -м шаге приносит некоторый результат и переводит систему в некоторое новое состояние . Для каждого возможного состояния на k -м шаге среди всех возможных управлений выбирается оптимальное управление такое, чтобы результат, который достигается за шаги сk -го по n -й оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана и зависит от номера шага k и состояния системы .

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

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

В общем случае задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состоянияв конечное состояние, при котором целевая функция
принимает наибольшее (наименьшее) значение.

Особенности математической модели динамического программирования заключаются в следующем:

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

целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

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

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

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X .

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n -го по первый (на первом шаге k =1 состояние системы равно ее начальному состоянию ), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге, применение которого переведет систему в состояние
, зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнегоn -го шага.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Суть метода

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

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

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

Задача динамического программирования оптимизации. Автором этого метода Р. Беллманом был сформулирован принцип оптимальности: каким бы ни являлось начальное состояние на каждом из шагов и решение, определенное на этом шаге, все следующие выбираются оптимальными по отношению к тому состоянию, которое принимает система в конце шага.

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

Построение алгоритма задачи

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

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

Применение метода

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

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

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

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

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

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

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

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

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

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

Рассмотрим общую постановку задачи этого программирования. Пусть исследуется некоторый экономический процесс, имеющий п последовательных этапов. На каждом 7-м этапе процесс может быть в разных состояниях бы, каждый из которых характеризуется конечным множеством параметров. С каждым этапом задачи связано принятие определенного управленческого решения хи, которое переводит систему из одного состояния в другое. Предполагается, что состояние si системы в конце 7-го этапа определяется только предыдущим состоянием si_1 и управлением хи на 7-м этапе и не зависит от предыдущих состояний и управлений. Тогда состояние si системы записывается в виде зависимости

Si = ф (в, _!, Хи), i = 1, П.

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

При названных условиях задача динамического программирования формулируется так: определить такую допустимую последовательность управленческих решений X = {x1, x2, хп}, которая переводит систему из начального состояния 50 в завершающий состояние sn и при которой достигается максимальная эффективность управления.

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

Максимум целевой функции на заключительном п-м этапе равна

^ п-О = шах / п ^ п-и хп).

Соответственно, на (п - 1) -етапи имеем

г * п-1 (5п-2) = ШaХ ((fn-1 (sn-2, хп-1) + г * п ^ п-1)).

Учитывая эту закономерность, для произвольного k-этапа можем записать рекуррентную зависимость

г * (пятый-1) = Шахи (Л (ик-1, хк) + г * + 1)).

Такая рекуррентная зависимость представляет собой математическую запись принципа оптимальности Беллмана.

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

Основные особенности метода динамического программирования

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

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

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

4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных состояний sk и их количества п. Фактически здесь на каждом шагу решается не одна задача, а множество однотипных задач для различных состояний sk и различных к (1 <к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

Выводы

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

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

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

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

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

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

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

Это значит, что если взять вектор и умножить его на матрицу перехода 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