Задачи динамического программирования: Динамическое программирование. Классические задачи / Хабр

Всё, что вы хотели знать о динамическом программировании, но боялись спросить

Я был крайне удивлён, найдя мало статей про динамическое программирование (далее просто динамика) на хабре. Мне всегда казалось, что эта парадигма довольно сильно распространена, в том числе и за пределами олимпиад по программированию. Поэтому я постараюсь закрыть этот пробел своей статьёй.

# Весь код в статье написан на языке Python

Основы

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

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Чтобы успешно решить задачу динамикой нужно:
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.

Порядок пересчёта

Существует три порядка пересчёта:
1) Прямой порядок:
Состояния последовательно пересчитывается исходя из уже посчитанных.

2) Обратный порядок:

Обновляются все состояния, зависящие от текущего состояния.

3) Ленивая динамика:

Рекурсивная мемоизированная функция пересчёта динамики. Это что-то вроде поиска в глубину по ацикличному графу состояний, где рёбра — это зависимости между ними.

Элементарный пример: числа Фибоначчи. Состояние — номер числа.

Прямой порядок:

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 нажатий на такой клавиатуре.

Решение1) Состояние динамики: dp[n][m] — количество различных сообщений длины n, использующих m нажатий.
2) Начальное состояние: есть одно сообщение длины ноль, использующее ноль нажатий — пустое.
3) Формулы пересчёта: есть по восемь букв, для написания которых нужно одно, два и три нажатия, а так же две буквы требующие 4 нажатия.

Прямой пересчёт:

dp[n][m] = (dp[n - 1][m - 1] + dp[n - 1][m - 2] + dp[n - 1][m - 3]) * 8 + dp[n - 1][m - 4] * 2

Обратный пересчёт:

dp[n + 1][m + 1] += dp[n][m] * 8
dp[n + 1][m + 2] += dp[n][m] * 8
dp[n + 1][m + 3] += dp[n][m] * 8
dp[n + 1][m + 4] += dp[n][m] * 2

4) Порядок пересчёта:
Если писать прямым методом, то надо отдельно подумать о выходе за границу динамики, к примеру, когда мы обращаемся к dp[n - 1][m - 4], которого может не существовать при малых m. Для обхода этого можно или ставить проверки в пересчёте или записать туда нейтральные элементы (не изменяющие ответа).

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

5) Ответ — это сумма всех состояний.

UPD:

К сожалению, я допустил ошибку — задачу можно решить и одномерно, просто убрав из состояния длину сообщения n.

1) Состояние: dp[m] — количество различных собщений, которые можно набрать за m нажатий.

2) Начальное состояние: dp[0] = 1.

3) Формула пересчёта:

dp[m] = (dp[m - 1] + dp[m - 2] + dp[m - 3]) * 8 + dp[m - 4] * 2

4) Порядок: все три варианта можно использовать.
5) Ответ — это сумма всех состояний.

Пример №2: Конь

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

Решение1) Состояние динамики: dp[i][j] — количество способов добраться до (i, j).
2) Начальное значение: В клетку (1, 1) можно добраться одним способом — ничего не делать.
3) Формула пересчёта:
Для прямого порядка:

dp[i][j] = dp[i - 2][j - 1] + dp[i - 2][j + 1] + dp[i - 1][j - 2] + dp[i + 1][j - 2]

Для обратного порядка:

dp[i + 1][j + 2] += dp[i][j]
dp[i + 2][j + 1] += dp[i][j]
dp[i - 1][j + 2] += dp[i][j]
dp[i + 2][j - 1] += dp[i][j]

4) А теперь самое интересное в этой задаче: порядок. Здесь нельзя просто взять и пройтись по строкам или по столбцам. Потому что иначе мы будем обращаться к ещё не пересчитанным состояниям при прямом порядке, и будем брать ещё недоделанные состояния при обратном подходе.

Есть два пути:

1) Придумать хороший обход.

2) Запустить ленивую динамику, пусть сама разберётся.

Если лень думать — запускаем ленивую динамику, она отлично справится с задачей.

Если не лень, то можно придумать обход наподобие такого:

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

5) Ответ просто лежит в dp[n][m].

Динамика и матрица переходов

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

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

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

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

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

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

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

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

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

1) Состояние динамики: dp[n][last][less] — количество пилообразных последовательностей длины n, заканчивающихся на цифру last. Причём если less == 0, то последняя цифра меньше предпоследней, а если less == 1, значит больше.

2) Начальные значения:

for last in range(10):
    dp[2][last][0] = 9 - last
    dp[2][last][1] = last

3) Пересчёт динамики:

for prev in range(10):
    if prev > last:
        dp[n][last][0] += dp[n - 1][prev][1]
    if prev < last:
        dp[n][last][1] += dp[n - 1][pref][0]

4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for‘ов.
5) Ответ — это сумма dp[N][0..9][0..1].

Теперь надо придумать начальный вектор и матрицу перехода к нему. Вектор, кажется, придумывается быстро: все состояния, обозначающие длину последовательности 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[l:r]

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[l:l + dp_len / cnt] == s[l + (dp_len / cnt) * j:l + (dp_len / cnt) * (j + 1)]
        if good:  # Попробовать разделить на cnt одинаковых подстрок и сжать
            dp[l][r] = min(dp[l][r], len(str(cnt)) + 1 + dp[l][l + dp_len / cnt] + 1)

4) Порядок пересчёта: прямой по возрастанию длины подстроки или ленивая динамика.
5) Ответ лежит в d[0][len(s)].

Пример №5: Дубы

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

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

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

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

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

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

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

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

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

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

4) Порядок пересчёта: легче всего реализуется лениво — в виде поиска в глубину из корня.

5) Ответ — d[root][value[root] xor 1].

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

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

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

Задан взвешенный (веса рёбер неотрицательны) граф G размера N. Найти гамильтонов цикл (цикл, проходящий по всем вершинам без самопересечений) минимального веса.РешениеТак как мы ищем цикл, проходящий через все вершины, то можно выбрать за «начальную» вершину любую. Пусть это будет вершина с номером 0.

1) Состояние динамики: dp[mask][v] — путь минимального веса из вершины 0 в вершину v, проходящий по всем вершинам, лежащим в mask и только по ним.

2) Начальные значения: dp[1][0] = 0, все остальные состояния изначально — +inf.

3) Формула пересчёта: Если i-й бит в mask равен 1 и есть ребро из i в v, то:

dp[mask][v] = min(dp[mask][v], dp[mask - (1 << i)][i] + w[i][v])

Где w[i][v] — вес ребра из i в v.
4) Порядок пересчёта: самый простой и удобный способ — это написать ленивую динамику, но можно поизвращаться и написать перебор масок в порядке увеличения количества единичных битов в ней.
5) Ответ лежит в d[(1 << N) - 1][0].

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

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

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

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

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

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

Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1.РешениеЗдесь профиль — это один столбец. Хранить его удобно в виде двоичной маски: 0 — не замощенная клетка столбца, 1 — замощенная. То есть всего профилей .

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

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

Если в первом профиле на очередном месте стоит 0, то есть два варианта — или во втором 0 или 1.

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

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

После этого сохранить всё в массив can[mask][next_mask] — 1, если можно перейти, 0 — если нельзя.

1) Состояние динамики: dp[pos][mask] — количество полных замощений первых pos - 1 столбцов с профилем mask.

2) Начальное состояние: dp[0][0] = 1 — левая граница поля — прямая стенка.

3) Формула пересчёта:

dp[pos][mask] += dp[pos - 1][next_mask] * can[mask][next_mask]

4) Порядок обхода — в порядке увеличения pos.
5) Ответ лежит в dp[pos][0].

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

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

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

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

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

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

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

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

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

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

Память

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

Время

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

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

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

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

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

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

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

Решение №1:

1) Состояние динамики: dp[n][k] — количество разложений числа n на числа, меньшие или равные k. Параметр k нужен, чтобы брать всегда только большие числа, чем уже имеющиеся.
2) Начальные значения: dp[1][1] = 1, dp[1][i] = 0.
3) Формула пересчёта:

for last_summand in range(1, k + 1):
    dp[n][k] += dp[n - last_summand][last_summand]

4) Порядок: прямой, в порядке увеличения n.
5) Ответ — сумма dp[N][1..N].

Состояний: , переходов: . Асимптотика: .

Решение №2:

1) Поменяем состояние. Теперь dp[n][k] — это количество разложений числа n на k различных чисел. Казалось бы незачем, но сейчас будет понятно.
2) Начальные значения: dp[1][1] = 1, dp[1][i] = 0.
3) Формула пересчёта:

dp[n][k] = dp[n - k][k] + dp[n - k][k - 1]

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

• Все уже имеющиеся числа увеличить на 1.
• Все уже имеющиеся числа увеличить на 1. Добавить число 1 в разложение.

Чтобы понять, почему это так можно посмотреть на диаграммы Юнга:

Строки здесь обозначают слагаемые.

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

4) Порядок пересчёта: прямой, в порядке увеличения n.

Невооруженным взглядом кажется, что у этого решения асимптотика , ведь есть два измерения в состоянии и переходов. Но это не так, ведь второй параметр — k ограничен сверху не числом N, а формулой (сумма чисел от 1 до k меньше или равна разлагаемого числа). Из этой формулы видно, что количество состояний .

5) Ответ — это сумма dp[N][1..k_max].

Асимптотика: .

Заключение

Основным источником была голова, а туда информация попала с лекций в Летней Компьютерной Школе (для школьников), а также кружка Андрея Станкевича и спецкурса Михаила Дворкина (darnley).

Спасибо за внимание, надеюсь эта статья кому-нибудь пригодится! Хотя мне уже пригодилась — оказывается, написание статьи это хороший способ всё вспомнить.

Динамическое программирование на практике. / Хабр

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

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

Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении исходного результата. Для решения подзадач этот же алгоритм применяется рекурсивно. При этом для каждой подзадачи запоминается вычисленный ответ, и если на каком-то шаге подзадача встретилась второй раз, то вычисления для неё не производятся.
http://ru.wikipedia.org/wiki/Динамическое_программирование

Довольно хорошее и понятное объяснение, но давайте лучше возьмем пример. Думаю, самое простое, что приходит в голову, это числа Фибоначчи. Для нее заданы некоторые исходные данные – A[1]=1, A[2]=1, в после элемент A[i]=A[i-1]+A[i-2]. При этом A[i] часто называют состоянием, а некое отношение относительно предподсчитанных данных – переходом. В данном случае из A[i] есть 2 перехода – в A[i-1] и в A[i-2]. Количество переходов может меняться в зависимости от задачи.
Но ведь динамическое программирование не просто так используют. А именно потому, что оно позволяет иногда очень значительно сократить время решения какой-либо задачи, что иногда, при большим объемах входных данных, бывает очень критично. И я хочу показать одну такую задачу, которую встретил на Зональной Олимпиаде Школьников в этом году. Дословно условие не помню, но вот общий смысл:

Есть матрица чисел A размера NxM и число K. Задана первая ее строка – A[1,1]..A[1,M]. После этого для каждого элемента, стоящего ниже первой строки, значение определяется как сумма всех элементов в треугольнике выше него по модулю K. Требуется вывести последнюю строчку этой матрицы A[N,1]..A[N,M]. Ограничения: 1 ≤ N,M ≤ 2000; 2 ≤ K ≤ 10⁹.

Итак, чтобы узнать значение элементов в какой-либо строке, нам надо знать значения элементов во всех строках выше нее. Самое простое решение, которое приходит на ум, это для каждого элемента просто взять и пройтись по всем элементам в треугольнике выше него, считая сумму. Да, так можно сделать, когда время не критично или когда ограничения на N и M небольшие, т.к. такой алгоритм работает за асимптотику порядка O(N⁴) (если принимать N=M). Т.е. даже при N=M=100 это будет работать порядка 5-10 секунд (зависит от компьютера), я уже молчу про N=M=2000. Значит, нам нужно как-то это дело ускорять. А давайте сделаем вот как. У нас есть треугольник, который надо подсчитать. И у нас есть предподсчитанные треугольники для всех элементов выше него. Так давайте составим новый треугольник, используя уже рассчитанные! Смотрим рисунок:

Т.е. если нам нужно рассчитать треугольник с началом в A[i,j], тогда он будет считаться по формуле:
A[i,j]=(A[i-1,j]+2*A[i-1,j-1]+2*A[i-1,j+1]-2*A[i-2,j]) mod K. (где mod K — взять по модулю K)
Мы отнимаем треугольник A[i-2,j] т.к. это область пересечения двух треугольников A[i-1,j-1] и A[i-1,j+1] и в противном случае мы посчитали бы ее 2 раза. Кстати, подумайте сами, почему мы умножаем на 2 некоторые значения.
Общая идея у этой задачи вот такая. Попробуйте сами написать ее решение (в ней есть несколько нюансов, которые я предлагаю вам найти самим) и проверить ее с помощью обычного переборного алгоритма на разных тестах. Если что непонятно – обращайтесь, постараюсь помочь, хотя, надо признаться, сам я в этом деле далеко не профи и решить могу далеко не все задачи, но на кое-что способен 😉

7. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Шаг 3 (распределение средств в третьем и четвертом кварталах)

Пусть в конце второго квартала между предприятиями распределяется сумма в размере S2. Пусть предприятию П1 выделяется сумма в размере U3, а предприятию П2 – S2–U3. Тогда выручка предприятий к концу третьего кварта-

ла составит 1,5 U3+1,8 (S2–U3). Из этой суммы 20% будет выплачено акционерам, а 80% — распределено между предприятиями. Выплаты акционерам за третий и четвертый кварталы определяются следующим образом:

E3=Z3+ E4*=0,2 (1,5 U3+1,8 (S2–U3)) + E4*.

Выразим величину E3 через U3 и S2. Как показано выше, E4*=0,34 S3, где

S3 – сумма средств, распределяемых между предприятиями в начале четвертого квартала. Эта сумма составляет 80% от выручки предприятий в третьем кварта-

ле: S3=0,8 (1,5 U3+1,8 (S2–U3)). Таким образом, E4*=0,34 0,8 (1,5 U3+1,8 (S2–

-U3)) = 0,49 S2–0,08 U3.

Подставляя эту величину в уравнение для E3, получим:

E3= 0,2 (1,5 U3+1,8 (S2–U3)) + 0,49 S2–0,08 U3 = 0,85 S2–0,14 U3.

Видно, что максимальные выплаты акционерам обеспечиваются при ми-

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

чтобы не выделять средства предприятию П1: U 3*=0. Подставляя U3=0, получим выражение для условно оптимального значения критерия эффективности на третьем и четвертом шагах: E3*= 0,85 S2.

Шаг 2 (распределение средств во втором — четвертом кварталах)

Пусть в конце первого квартала между предприятиями распределяется сумма в размере S1. Пусть предприятию П1 выделяется сумма в размере U2, а предприятию П2 – сумма в размере S1–U2. Тогда выручка предприятий к концу

второго квартала составит 1,5 U2+2,2 (S1–U2). Из этой суммы 20% будет выплачено акционерам, а 80% — распределено между предприятиями. Выплаты акционерам за второй — четвертый кварталы определяются следующим образом:

E2=Z2+ E3*=0,2 (1,5 U2+2,2 (S1–U2)) + E3*.

Выполнив расчеты, аналогичные приведенным на шаге 3, выразим величину E2 через U2 и S1:

E2 = 0,2 (1,5 U2+2,2 (S1–U2)) + E3* = 0,2 (1,5 U2+2,2 (S1–U2)) + 0,85 S2 =

=0,2 (1,5 U2+2,2 (S1–U2)) + 0,85 0,8 (1,5 U2+2,2 (S1–U2)) =

=1,94 S1 – 0,62 U2.

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

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

Динамическое программирование очень похоже на рекурсию, при этом:

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

Классическая задача — числа Фибоначчи

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

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

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

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

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

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

F = [-1]*MAX_POSSIBLE_N

def fib(n):
    if n <= 1:
        return n
    if F[n] == -1:
        F[n] = fib(n-1) + fib(n-2)
    return F[n]

Приведенное решение корректно и эффективно. Но можно поступить ещё проще:

def fib(n):
    F = [-1]*(n+1)
    F[0] = 0
    F[1] = 1
    for i in range(2, n+1):
        F[i] = F[i - 1] + F[i - 2]
    return F[n]

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

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F[i] для i < n), затем, зная решения подзадач, нашли ответ.

Задача о кузнечике — количество способов

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

Обозначим количество маршрутов кузнечика, ведущих в точку с координатой n, как K[n]. Прежде всего заметим, что существует ровно один маршрут из точки 1 в точку 1 — он не содержит ни одного прыжка. В точку 2 можно прыгнуть единственным способом — из точки 1.

Как вычислить K[n]? В точку кузнечик может попасть двумя способами — из точки при помощи прыжка длиной 2 и из точки прыжком длины 1. То есть число способов попасть в точку n равно сумме числа способов попасть в точку (n-1) и (n-2), что позволяет выписать рекуррентное соотношение: K[n] = K[n-1] + K[n-2].

Можно заметить, что данная задача по сути свелась к числам Фибоначчи, поэтому мы не будем выписывать её решение.

Упражнение №1

Решите задачу о количестве способов достичь точки n из точки 1, если кузнечик умеет прыгать +1, +2 и +3.

Упражнение №2

Решите задачу о количестве способов достичь точки n из точки 1, если кузнечик умеет прыгать +1, +2 и *3.

Задача о кузнечике со стоимостями посещения точек

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость, различную для различных точек. Стоимость прыжка в точку i задается значением price[i] списка price. Необходимо найти минимальную стоимость маршрута кузнечика из точки 0 в точку n.

На этот раз нам необходимо модифицировать определение целевой функции. Пусть C[n] — минимальная стоимость пути из 1 в n.

Выведем рекуррентное соотношение для этой функции.Чтобы попасть в точку n мы должны попасть в неё последним прыжком из (n-1) или (n-2). Минимальные стоимости этих маршрутов будут равны С[n-1] и С[n-2] соответственно, к ним придется добавить значение price[n] за прыжок в клетку n. Но из двух клеток мы можем выбрать любую.

Нужно выбрать тот маршрут, который имеет наименьшую стоимость: C[n] = min(C[n-1], C[n-2]) + price[n]

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

Упражнение №3

Напишите функцию calculate_min_cost(n, price) вычисления наименьшей стоимость достижения клетки n из клетки 1

Восстановление наиболее выгодной траектории

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

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

Для восстановления ответа будем для каждой точки запоминать номер точки prev[i], из которой кузнечик попал в точку i, если он будет передвигаться по пути минимальной стоимости. То есть prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev — это массив предшественников). Как определить prev[i]? Если C[i-1] < C[i-2], то кузнечик попал в точку i из точки (i-1), поэтому prev[i] = i — 1, иначе prev[i] = i — 2.

Для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь не дойдет до начальной точки с номером 0. Номера всех вершин будем добавлять в список path. В конце в список path добавляется начальная вершина номер 1, которая не была обработана в основном цикле, а затем весь список path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).

Упражнение №4

Модифицируйте алгоритм вычисления значений целевой функции так, чтобы вычислить значения prev[i], и восстановите траекторию наименьшей стоимости из точки 1 в точку n.

Задача динамического программирования о поиске кратчайшего пути

Решение задачи динамического программирования о поиске кратчайшего пути

Постановка задачи

Представим граф, представляющий собой воображаемую карту дорог, вершинами которого являются точки пересечения дорог или перекрестки (A11, A21, A31, A12, A22, A31, A13, A23…), см. рис. 5.1.

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

Рис. 5.1. Граф для задачи поиска кратчайшего пути

Итак, наша цель:

1. определить путь минимальной длины;
2. определить минимальное расстояние от дома до работы.

Введем условные дополнения:

• ехать можно только в одну сторону — слева направо (например, из точки A21 можно двигаться только в точки A31 и A32)
• расстояние между точками или перекрестками укажем в таблицах:

Как решить задачу без использования методов ДП?

Наивное решение

Наивным решением может быть метод перебора.

Граф имеет структуру — порядок слева направо.

• взять 1-й путь и найти его длину d1
• взять 2-й путь и найти его длину d2
• …
• взять k-й путь и найти его длину dk

После этого определить минимальный путь посредством процедуры argmin (di), i=1...k

Т.е. решить такую задачу можно перебором.

Минус:
Посчитаем количество путей (из каждой вершины) — получим 18 путей.
Это не так мало, задача ведь простая.

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

Такие алгоритмы считаются не эффективными.

Другой вариант:
Можно воспользоваться так называемыми алгоритмами на графах, например, алгоритмом Дейкстра. О них поговорим на другой лекции.

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

Составление порядка решения

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

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

Рис. 5.2. Количество уровней перекрестков, которые надо пересечь, доехав до работы

Получилось 4 уровня перекрестков от Дома до Работы.

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

Предположим, что мы находимся на последнем уровне перекрестков от Работы.
На последнем уровне перекрестков минимальная длина пути из каждого перекрестка до работы известна (из таблицы) — это 4 и 3.

Зная минимальную длину пути из этого уровня перекрестков до Работы, можно ли найти минимальную дину пути из следующего уровня (A21, A22, A23) до Работы? — да можно. Например, из точки А21 нужно посмотреть всего два варианта: А21 -> A31 и A21 -> A32. Затем выбрать минимальный из них, воспользовавшись процедурой argmin.

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

И так и продолжим, пока не найдем минимальную длину пути от Дома до Работы.

Словесный алгоритм мы разработали. Теперь приступим к решению.

1 этап: определению целевой функции и порядка решения:

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

F_{3,j (j)=1,2}2,j (j)=1,2,3 1,j(j)=1,2,3 Дом

2 этап: Определение начального условия:

F3,1 — минимальная длина пути из перекрестка A₃₁ до Работы = 4
F3,2 — минимальная длина пути из перекрестка A₃₂ до Работы = 3

F3,1 = 4
F3,2 = 3

3-й этап: определение рекурсивной функции перехода от, например, F_{2,j (j)=1,2,3} до F_3,j

F2,2 — это второй уровень, состоящий из перекрестков А₂₁, А₂₂, А₂₃

Рассмотрим перекресток А₂₂, из которого есть два пути:

1. А₂₂ А₃₁, а из него мы отправимся до работы минимальным маршрутом, который уже рассчитан — это F_3,1; получаем 3 + 4;
2. и А₂₂ А₃₂, а из него мы отправимся до работы минимальным маршрутом, который ужже рассчитан — это F_3,2; получаем 3 + 3;

Затем необходимо выбрать минимальный из них, используя функцию argmin : 6 , т.е. нам подходит А₃₂

Итак, получаем по одной ветви второго уровня перекрестков:
F2,2 = min[A22 -> A31 -> Работа; A22 -> A32 -> Работа] = min[3 + 4; 3 + 3] = 6 (А_3,2)

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

F2,1 = min[A21 -> A31 -> Работа; A21 -> A32 -> Работа] = min(3 + 4; 2 + 3) = 5 (А₃₂)

Рассчитываем последнюю оставшуюся ветвь второго уровня:

F2,3 = min(1 + 4; 3 + 3) = 5 (А₃₁)

Рассматриваем третий уровень перекрестков:

F1,1 (перекресток A₁₁) = min[A11 -> A21 -> F_2,1;A11 -> A22 -> F_2,2;A11 -> A23 -> F_2,3] = min[2 + 5;1 + 6;1 + 5] = 6 (A₂₃) (А₃₁)

F1,2 (перекресток A₁₂) = min[1 + 5;2 + 6;1 + 5] = 6 (A₂₃) (А₂₁), можно взять любой минмимум из двух

F1,3 (перекресток A₁₃)= min[2 + 5;3 + 6;2 + 5] = 7 (A₂₃) (А₂₁), можно взять любой минмимум из двух

Осталось найти цель — из Дома:

FДом = min[1 -> A11 -> F11; 2 -> A12 -> F12; 3 -> A13 -> F13] = min[1 + 6;2 + 6;3 + 7] = 7 (A₁₁)

Результат:

Длина минимального пути из Дома до Работы = 7
Восстановим минимальный путь: A11 -> A23 -> A31 - > Работа

Сложность решения: решая задачу с перебором, приходилось умножать (3 * 3 * 2), а в данной задаче нам необходимо складывать. Т.е. мы получаем вместо экспоненциальной функции эффективное полеомиальное решения.

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

новейших вопросов «динамического программирования» — qaru

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

.Словарь

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

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

.

c — приближение к динамическому программированию

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

Загрузка…

2. Авторизоваться
   зарегистрироваться

3. текущее сообщество
   

.

No related posts.