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

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

Определите:

1) размах вариации;

2) средний размер вклада;

3) среднее линейное отклонение;

4) дисперсию;

5) среднее квадратическое отклонение;

6) коэффициент вариации вкладов.

Решение:

Данный ряд распределения содержит открытые интервалы. В таких рядах условно принимается величина интервала первой группы равна величине интервала последующей, а величина интервала последней группы равна величине интервала предыдущей.

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

1) Определим размах вариации как разность между наибольшим и наименьшим значением признака:

Размах вариации размера вклада равен 1000 рублей.

2) Средний размер вклада определим по формуле средней арифметической взвешенной.

Предварительно определим дискретную величину признака в каждом интервале. Для этого по формуле средней арифметической простой найдём середины интервалов.

Среднее значение первого интервала будет равно:

второго - 500 и т. д.

Занесём результаты вычислений в таблицу:

Размер вклада, руб.	Число вкладчиков, f	Середина интервала, х	xf
200-400	32	300	9600
400-600	56	500	28000
600-800	120	700	84000
800-1000	104	900	93600
1000-1200	88	1100	96800
Итого	400	-	312000

Средний размер вклада в Сбербанке города будет равен 780 рублей:

3) Среднее линейное отклонение есть средняя арифметическая из абсолютных отклонений отдельных значений признака от общей средней:

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

1. Вычисляется средняя арифметическая взвешенная, как показано в п. 2).

2. Определяются абсолютные отклонения вариант от средней:

3. Полученные отклонения умножаются на частоты:

4. Находится сумма взвешенных отклонений без учёта знака:

5. Сумма взвешенных отклонений делится на сумму частот:

Удобно пользоваться таблицей расчётных данных:

Размер вклада, руб.	Число вкладчиков, f	Середина интервала, х
200-400	32	300	-480	480	15360
400-600	56	500	-280	280	15680
600-800	120	700	-80	80	9600
800-1000	104	900	120	120	12480
1000-1200	88	1100	320	320	28160
Итого	400	-	-	-	81280

Среднее линейное отклонение размера вклада клиентов Сбербанка составляет 203,2 рубля.

4) Дисперсия - это средняя арифметическая квадратов отклонений каждого значения признака от средней арифметической.

Расчёт дисперсии в интервальных рядах распределения производится по формуле:

Порядок расчёта дисперсии в этом случае следующий:

1. Определяют среднюю арифметическую взвешенную, как показано в п. 2).

2. Находят отклонения вариант от средней:

3. Возводят в квадрат отклонения каждой варианты от средней:

4. Умножают квадраты отклонений на веса (частоты):

5. Суммируют полученные произведения:

6. Полученная сумма делится на сумму весов (частот):

Расчёты оформим в таблицу:

Размер вклада, руб.	Число вкладчиков, f	Середина интервала, х
200-400	32	300	-480	230400	7372800
400-600	56	500	-280	78400	4390400
600-800	120	700	-80	6400	768000
800-1000	104	900	120	14400	1497600
1000-1200	88	1100	320	102400	9011200
Итого	400	-	-	-	23040000

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

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

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

Размах вариации представляет собой разность максимального и минимального значений признака: R = Xmax – Xmin . Недостатком данного показателя является то, что он оценивает только границы варьирования признака и не отражает его колеблемость внутри этих границ.

Дисперсия лишена этого недостатка. Она рассчитывается как средний квадрат отклонений значений признака от их средней величины:

Упрощенный способ расчета дисперсии осуществляется с помощью следующих формул (простой и взвешенной):

Примеры применения данных формул представлены в задачах 1 и 2.

Широко распространенным на практике показателем является среднее квадратическое отклонение :

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

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

Формула для расчета коэффициента вариации.

Примеры решения задач по теме «Показатели вариации в статистике»

Задача 1 . При изучении влияния рекламы на размер среднемесячного вклада в банках района обследовано 2 банка. Получены следующие результаты:

Определить:
1) для каждого банка: а) средний размер вклада за месяц; б) дисперсию вклада;
2) средний размер вклада за месяц для двух банков вместе;
3) Дисперсию вклада для 2-х банков, зависящую от рекламы;
4) Дисперсию вклада для 2-х банков, зависящую от всех факторов, кроме рекламы;
5) Общую дисперсию используя правило сложения;
6) Коэффициент детерминации;
7) Корреляционное отношение.

Решение

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

Средний размер вклада найдем по формуле средней арифметической взвешенной:

29 000/50 = 580 руб.

Дисперсию вклада найдем по формуле:

23 400/50 = 468

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

2) Найдем средний размер вклада для двух банков вместе. Хср =(580×50+542,8×50)/100 = 561,4 руб.

3) Дисперсию вклада, для двух банков, зависящую от рекламы найдем по формуле: σ 2 =pq (формула дисперсии альтернативного признака). Здесь р=0,5 – доля факторов, зависящих от рекламы; q=1-0,5, тогда σ 2 =0,5*0,5=0,25.

4) Поскольку доля остальных факторов равна 0,5, то дисперсия вклада для двух банков, зависящая от всех факторов кроме рекламы тоже 0,25.

5) Определим общую дисперсию, используя правило сложения.

= (468*50+636,16*50)/100=552,08

= [(580-561,4)250+(542,8-561,4)250] / 100= 34 596/ 100=345,96

σ 2 = σ 2 факт + σ 2 ост = 552,08+345,96 = 898,04

6) Коэффициент детерминации η 2 = σ 2 факт / σ 2 = 345,96/898,04 = 0,39 = 39% - размер вклада на 39% зависит от рекламы.

7) Эмпирическое корреляционное отношение η = √η 2 = √0,39 = 0,62 – связь достаточно тесная.

Задача 2 . Имеется группировка предприятий по величине товарной продукции:

Определить: 1) дисперсию величины товарной продукции; 2) среднее квадратическое отклонение; 3) коэффициент вариации.

Решение

1) По условию представлен интервальный ряд распределения. Его необходимо выразить дискретно, то есть найти середину интервала (х"). В группах закрытых интервалов середину найдем по простой средней арифметической. В группах с верхней границей - как разность между этой верхней границей и половиной размера следующего за ним интервала (200-(400-200):2=100).

В группах с нижней границей – суммой этой нижней границы и половины размера предыдущего интервала (800+(800-600):2=900).

Расчет средней величины товарной продукции делаем по формуле:

Хср = k×((Σ((х"-a):k)×f):Σf)+a. Здесь а=500 - размер варианта при наибольшей частоте, k=600-400=200 - размер интервала при наибольшей частоте. Результат поместим в таблицу:

Итак, средняя величина товарной продукции за изучаемый период в целом равна Хср = (-5:37)×200+500=472,97 тыс. руб.

2) Дисперсию найдем по следующей формуле:

σ 2 = (33/37)*2002-(472,97-500)2 = 35 675,67-730,62 = 34 945,05

3) среднее квадратическое отклонение: σ = ±√σ 2 = ±√34 945,05 ≈ ±186,94 тыс. руб.

4) коэффициент вариации: V = (σ /Хср)*100 = (186,94 / 472,97)*100 = 39,52%

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

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

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

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

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

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

Средняя выработка отражает общее свойство всей совокупности.

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

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

Существуют различные средние:

средняя арифметическая;

средняя геометрическая;

средняя гармоническая;

средняя квадратическая;

средняя хронологическая.

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

Средняя арифметическая

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

Отдельные значения признака называют вариантами и обозначают через х (); число единиц совокупности обозначают через n, среднее значение признака - через. Следовательно, средняя арифметическая простая равна:

По данным дискретного ряда распределения видно, что одни и те же значения признака (варианты) повторяются несколько раз. Так, варианта х встречается в совокупности 2 раза, а варианта х-16 раз и т.д.

Число одинаковых значений признака в рядах распределения называется частотой или весом и обозначается символом n.

Вычислим среднюю заработную плату одного рабочего в руб.:

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

Полученная формула называется средней арифметической взвешенной.

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

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

Основные свойства средней арифметической.

Средняя арифметическая обладает рядом свойств:

1. От уменьшения или увеличения частот каждого значения признака х в п раз величина средней арифметической не изменится.

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

• 2. Общий множитель индивидуальных значений признака может быть вынесен за знак средней:
• 3. Средняя суммы (разности) двух или нескольких величин равна сумме (разности) их средних:
• 4. Если х = с, где с - постоянная величина, то.
• 5. Сумма отклонений значений признака Х от средней арифметической х равна нулю:

Средняя гармоническая

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

Характеристиками вариационных рядов, наряду со средними, являются мода и медиана.

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

Для интервальных рядов распределения с равными интервалами мода определяется по формуле:

где - начальное значение интервала, содержащего моду;

Величина модального интервала;

Частота модального интервала;

Частота интервала, предшествующего модальному;

Частота интервала, следующего за модальным.

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

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

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

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

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

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

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

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

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

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

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

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

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