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

Динамическое программирование это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.
Чтобы успешно решить задачу динамикой нужно: 1) Состояние динамики: параметр(ы), однозначно задающие подзадачу. 2) Значения начальных состояний. 3) Переходы между состояниями: формула пересчёта. 4) Порядок пересчёта. 5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.
Порядок пересчёта
Существует три порядка пересчёта: 1) Прямой порядок: Состояния последовательно пересчитывается исходя из уже посчитанных. 2) Обратный порядок: Обновляются все состояния, зависящие от текущего состояния. 3) Ленивая динамика: Рекурсивная [ Cкачайте файл, чтобы посмотреть ссылку ] функция пересчёта динамики. Это что-то вроде [ Cкачайте файл, чтобы посмотреть ссылку ] по ацикличному графу состояний, где рёбра это зависимости между ними. Элементарный пример: [ Cкачайте файл, чтобы посмотреть ссылку ]. Состояние номер числа. Прямой порядок:
fib[1] = 1 # Начальные значения
fib[2] = 1 # Начальные значения
for i in range(3, n + 1):
fib[i] = fib[i - 1] + fib[i - 2] # Пересчёт состояния i
Обратный порядок:
fib[1] = 1 # Начальные значения
for i in range(1, n):
fib[i + 1] += fib[i] # Обновление состояния i + 1
fib[i + 2] += fib[i] # Обновление состояния i + 2
Ленивая динамика:
def get_fib(i):
if (i <= 2): # Начальные значения
return 1
if (fib[i] != -1): # Ленивость
return fib[i]
fib[i] = get_fib(i - 1) + get_fib(i - 2) # Пересчёт
return fib[i]
Все три варианта имеют права на жизнь. Каждый из них имеет свою область применения, хотя часто пересекающуюся с другими.
Многомерная динамика
Пример одномерной динамики приведён выше, в «порядке пересчёта», так что я сразу начну с многомерной. Она отличается от одномерной, как вы уже наверно догадались, количеством измерений, то есть количеством параметров в состоянии. Классификация по этому признаку обычно строится по схеме «один-два-много» и не особо принципиальна, на самом деле. Многомерная динамика не сильно отличается от одномерной, в чём вы можете убедиться взглянув на пару примеров:
Пример №1: Количество СМСок
Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так: Требуется подсчитать, сколько различных текстовых сообщений множно написать используя не более k нажатий на такой клавиатуре.
Решение

Пример №2: Конь
Шахматный конь стоит в клетке (1, 1) на доске размера N x M. Требуется подсчитать количество способов добраться до клетки (N, M) передвигаясь четырьмя типами шагов:
Решение

Динамика и матрица переходов
Если никогда не умножали матрицы, но хотите понять этот заголовок, то стоит прочитать хотя бы [ Cкачайте файл, чтобы посмотреть ссылку ]. Допустим, есть задача, которую мы уже решили динамическим программированием, например, извечные числа Фибоначчи. Давайте немного переформулируем её. Пусть у нас есть вектор , из которого мы хотим получить вектор . Чуть-чуть раскроем формулы: . Можно заметить, что из вектора можно получить вектор путем умножения на какую-то матрицу, ведь в итоговом векторе фигурируют только сложенные переменные из первого вектора. Эту матрицу легко вывести, вот она: . Назовём её матрицей перехода. Это значит, что если взять вектор и умножить его на матрицу перехода n - 1 раз, то получим вектор , в котором лежит fib[n] ответ на задачу. А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: . Это хорошо тем, что теперь можно применить [ Cкачайте файл, чтобы посмотреть ссылку ], который работает за . Итого мы сумели посчитать N-ое число Фибоначчи за логарифм арифметических операций. А теперь пример посерьёзнее:
Пример №3: Пилообразная последовательность
Обозначим пилообразную последовательность длины N как последовательность, у которой для каждого не крайнего элемента выполняется условие: он или меньше обоих своих соседей или больше. Требуется посчитать количество пилообразных последовательностей из цифр длины N. Выглядит это как-то так:
Решение

Динамика по подотрезкам
Это класс динамики, в котором состояние это границы подотрезка какого-нибудь массива. Суть в том, чтобы подсчитать ответы для подзадач, основывающихся на всех возможных подотрезках нашего массива. Обычно перебираются они в порядке увеличения длины, и пересчёт основывается, соответственно на более коротких отрезках.
Пример №4: Запаковка строки
Вот [ Cкачайте файл, чтобы посмотреть ссылку ]. Я вкратце его перескажу: Определим сжатую строку: 1) Строка состоящая только из букв это сжатая строка. Разжимается она в саму себя. 2) Строка, являющаяся конкатенацией двух сжатых строк A и B. Разжимается она в конкатенацию разжатых строк A и B. 3) Строка D(X), где D целое число, большее 1, а X сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X. Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC”. Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.
Решение

Пример №5: [ Cкачайте файл, чтобы посмотреть ссылку ]

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

Динамика по подмножествам
В динамике по подмножествам обычно в состояние входит маска заданного множества. Перебираются чаще всего в порядке увеличения количества единиц в этой маске и пересчитываются, соответственно, из состояний, меньших по включению. Обычно используется ленивая динамика, чтобы специально не думать о порядке обхода, который иногда бывает не совсем тривиальным.
Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера
Задан взвешенный (веса рёбер неотрицательны) граф G размера N. Найти [ Cкачайте файл, чтобы посмотреть ссылку ] (цикл, проходящий по всем вершинам без самопересечений) минимального веса.
Решение

Динамика по профилю
Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур. Эти задачи можно решить полным перебором за , где a количество вариантов замощения одной клетки. Динамика по профилю же оптимизирует время по одной из размерностей до линейной, оставив от себя в экспоненте только коэффициент. Получится что-то такое: . Профиль это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики. Почти всегда состояние это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can[mask][next_mask] можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти больше.
Пример №8: Замощение доминошками
Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1.
Решение

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

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

Память
Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода ленивая динамика.
Время
Иногда бывает так, что можно улучшить асимптотическое время, используя какую-нибудь структуру данных. К примеру, в [ Cкачайте файл, чтобы посмотреть ссылку ] можно воспользоваться [ Cкачайте файл, чтобы посмотреть ссылку ] для изменения асимптотического времени.
Замена состояния
В решениях динамикой обязательно фигурирует состояние параметры, однозначно задающие подзадачу, но это состояние не обязательно одно единственное. Иногда можно придумать другие параметры и получить с этого выгоду в виде снижения асимптотического времени или памяти.
Пример №9: Разложение числа
Требуется найти количество разложений числа N на различные слагаемые. Например, если N = 7, то таких разложений 5:
7
3 + 4
2 + 5
1 + 7
1 + 2 + 4

Два решения с различными состояниями

Заключение
Основным источником была голова, а туда информация попала с лекций в [ Cкачайте файл, чтобы посмотреть ссылку ] (для школьников), а также кружка Андрея Станкевича и спецкурса Михаила Дворкина ([ Cкачайте файл, чтобы посмотреть ссылку ]).
Рисунок 27Рисунок 22Рисунок 20Рисунок 18Рисунок 14Рисунок 11Рисунок 7Рисунок 5Рисунок 2Рисунок 1gђ Заголовок 4gђ Заголовок 515

Приложенные файлы

  • doc 15907324
    Размер файла: 140 kB Загрузок: 0

Добавить комментарий