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

От вокзала Алматы-2 до MEGA Alma-Ata 8,7 километра по прямой. Сколько есть маршрутов по улицам, на которых каждый следующий перекрёсток ближе к MEGA, чем предыдущий? Никаких петель и шагов назад. Ответ — 1 515 185 802 420 673. Перебирать такие маршруты по миллиарду в секунду пришлось бы семнадцать с половиной суток, а сцена ниже находит это число за миллисекунды и не перечисляет ни одного маршрута. Она заполняет таблицу: для каждого перекрёстка — сколько маршрутов ведёт от него к цели, начиная с ближайших к цели. Ставьте старт и финиш где угодно и переключайте, что значит «ближе».

Пока идёт счёт, точки загораются кругами вокруг финиша: цвет точки — сколько цифр в числе маршрутов от неё. Когда таблица дошла до старта, на карте остаётся «река» — толщина улицы показывает, какая доля всех маршрутов по ней проходит. Нажмите «Рекорд карты»: между двумя перекрёстками у противоположных краёв карты, в 14,6 километра друг от друга, маршрутов 484 908 221 365 218 608 639 281 781 018. Тридцать цифр. Перебор занял бы больше тысячи возрастов Вселенной.

А теперь поставьте старт на площади Республики, а финиш у Центрального стадиона. Маршрутов ноль: где-то по пути придётся отойти от стадиона, иначе не обойти квартал. Таблица не ошиблась — она честно сосчитала, что таких маршрутов нет. Переключите правило на «ближе по дорогам», и маршрутов станет 36: по этому правилу кратчайший путь годится всегда.

Идея

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

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

Состояния и переходы вместе образуют граф подзадач. На карте он виден буквально: перекрёстки — вершины, а каждая улица превращается в стрелку от дальнего конца к ближнему. Раз по стрелке расстояние до цели строго уменьшается, вернуться по стрелкам туда, где уже были, нельзя: в графе нет циклов. Именно это и разрешает заполнять таблицу — по возрастанию расстояния, в топологическом порядке. Режим «Перекрёсток» в сцене показывает переход на любом месте: зелёные соседи ближе к финишу, и число перекрёстка — сумма их чисел.

Дерево вызовов схлопывается в таблицу

Ту же мысль можно записать рекурсией — и сразу увидеть, почему без таблицы нельзя. Возьмём задачу поменьше: сколькими способами автомат может выдать N тенге монетами по 1, 2 и 5 тенге, выбрасывая их по одной? Порядок здесь важен: 2 + 5 и 5 + 2 — разные выдачи. Если первой вышла монета c, остаётся выдать N − c, поэтому

а слагаемые с отрицательным аргументом просто пропускаются. f(0) = 1: выдано всё, и это ровно один способ — ничего больше не выдавать. Ниже — все вызовы этой рекурсии. Ширина прямоугольника равна его ответу, поэтому одинаковые подзадачи выглядят одинаково и внутри устроены одинаково.

Без памяти дерево для 7 тенге — 62 вызова, хотя разных вопросов всего восемь: от f(0) до f(7). Нижняя строка показывает, сколько раз считался каждый: f(1) — 15 раз, f(0) — 26. Это не случайные числа. Вызов f(k) появляется в дереве каждый раз, когда первые монеты в сумме дали N − k, а это можно сделать f(N − k) способами. Значит, повторы растут так же быстро, как сами ответы, а ответы растут как степень: каждый следующий тенге умножает их примерно в 1,7 раза. Для 25 тенге и всех восьми монет — от 1 до 200 тенге — дерево состоит из 968 752 вызовов.

Включите «с памятью»: первое вычисление f(k) попадает в таблицу, остальные вызовы берут ответ из неё, и от дерева остаётся цепочка из N + 1 вычислений. Как это устроено в коде, какие нужны ключи и где подвохи — в статье о мемоизации; здесь важнее другое. Посмотрите, в каком порядке заполняется нижняя строка: 0, 1, 2, … — от маленьких сумм к большим, хотя рекурсия начинала сверху. Рекурсия с памятью сама нашла порядок, в котором каждая подзадача готова раньше, чем понадобится. Если этот порядок известен заранее, рекурсия не нужна вовсе: цикл от нуля вверх заполняет ту же таблицу. Это таблица снизу вверх — второй способ записать ту же динамику.

Почему таблица права

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

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

Как придумать динамику: пять вопросов

Любая динамика отвечает на пять вопросов. Пройдём их на той же задаче, но со всеми монетами, которые бывают в кошельке, — 1, 2, 5, 10, 20, 50, 100 и 200 тенге, — и на сумме 1000 тенге.

1. Состояние. Что нужно знать, чтобы решить остаток? Сколько ещё осталось выдать, s. Какие монеты уже вышли, неважно.
2. Переход. Как ответ собирается из меньших? Перебираем, какая монета выйдет следующей: f(s) — сумма f(s − c) по монетам c ≤ s.
3. База. Где ответ известен сразу? f(0) = 1.
4. Порядок. В каком порядке заполнять, чтобы слагаемые были готовы? По возрастанию s: каждый переход уменьшает сумму.
5. Ответ. Какая клетка таблицы — ответ на вопрос? f(1000).

Получается число из 233 цифр — столько разных последовательностей монет дают 1000 тенге. Но обычно спрашивают не о последовательностях, а о наборах: сколько есть разных горстей монет на 1000 тенге, если порядок неважен. Тут состояния «сколько осталось» мало, потому что по нему нельзя отличить 2 + 5 от 5 + 2. Нужно запомнить ещё, какие монеты разрешены дальше: договоримся выдавать монеты от больших к меньшим, и тогда состояние — пара «сколько осталось, самая крупная разрешённая монета». Подробный разбор этой ловушки — в главе курса о динамике. А третий вопрос — сколько монет нужно как минимум — живёт на том же графе, что и первый, только вместо суммы по переходам берётся минимум, и ответ — длина кратчайшего пути от 1000 до нуля.

Из таблицы видно главное: вопрос задаёт состояние, а не наоборот. Если два разных положения нужно различать, чтобы ответить правильно, они должны быть разными состояниями. Если различать не нужно, лишние подробности только раздувают таблицу. Для минимума монет, кстати, таблица не обязательна: у монет тенге жадный способ «сначала самую крупную» всегда даёт наименьшее число. Но так повезло не всем наборам номиналов: при монетах 1, 3 и 4 жадность платит 6 как 4 + 1 + 1, а можно 3 + 3. Где жадность права, а где нет, — в статье о жадных алгоритмах.

Код

Сцена из начала статьи. Ключ — квадрат расстояния до цели по прямой (целое число, поэтому сравнения точные) или расстояние по дорогам, которое считает алгоритм Дейкстры. Сама динамика — одна функция, и ей всё равно, какой ключ: отсортировать перекрёстки и пройти их по порядку.

Последние строки — один проход, который отвечает сразу для всех стартов: таблица для цели MEGA знает число маршрутов от каждого из 7909 перекрёстков. Больше всего их от перекрёстка в 11,4 километра — 23-значное число. Рекорд карты из сцены найден так же: проход для каждого перекрёстка в роли цели, 7909 проходов, около 45 секунд на Python на компьютере автора.

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

968 752 вызова против 26: с памятью каждый из 26 вопросов, от f(0) до f(25), решается один раз. Но 1000 тенге программа считает уже таблицей, и не зря: попробуйте orders_memo(500). Первый вызов спускается за orders_memo(499), тот за orders_memo(498), на каждый уровень приходится ещё кадр выражения-генератора, и Python останавливается с RecursionError. Таблице снизу вверх глубина стека не нужна.

Ловушка: число не помещается

Посмотрите на последние строки вывода программы о маршрутах:

  79,359,907,956,934,457,242,215 (23 digits)
  in int64: 2,014,951,835,966,190,183

В 64-битное целое помещаются числа до 9 223 372 036 854 775 807, это 19 цифр. Сложение сверх предела в Go не ошибка: число молча «заворачивается» по модулю 2⁶⁴, и вместо 23-значного ответа получается 19-значный, на вид совершенно правдоподобный. Ничто не подскажет, что он неверен. Python этой беды не знает: его целые растут сколько нужно. В Go для таких ответов есть math/big — так и написан листинг. На олимпиадах поступают иначе: просят ответ по модулю, обычно 10⁹ + 7. Тогда в каждой клетке хранят остаток, сумма двух остатков меньше 2,1 миллиарда и помещается даже в 32-битное целое со знаком, а складывать остатки можно в любой момент — остаток суммы равен остатку суммы остатков.

Сколько это стоит

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

• Маршруты по городу. Состояний — V перекрёстков, переходов — по числу улиц, всего O(E). Плюс сортировка по ключу, O(V log V). На Алматы это 7909 перекрёстков и 10 423 сложения — по одному на каждый участок улицы.
• Монеты. Состояний N + 1, переходов из каждого — k номиналов: O(N·k). Для наборов состояний в k раз больше, но из каждого всего два перехода, и снова O(N·k).

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

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

Рекурсия без памяти дорожает почти втрое на каждые два тенге — та самая степень 1,7 из дерева вызовов. Две другие линии лежат внизу и почти не растут: к сорока тенге это сотые доли миллисекунды. Таблица быстрее рекурсии с памятью в полтора-два раза на Python и ещё заметнее на Go: ей не нужны ни вызовы функций, ни словарь.

Где динамика не работает

Нет порядка. Если подзадачи зависят друг от друга по кругу, таблицу не заполнить. Иногда помогает добавить в состояние счётчик, который растёт с каждым шагом, как у Беллмана — Форда. Иногда порядок удаётся находить по ходу счёта: так работает алгоритм Дейкстры, который каждый раз достаёт из кучи ближайшую вершину, — её ответ уже окончательный.

Слишком много состояний. Чтобы объехать все точки маршрута по одному разу, в состояние нужно положить множество уже посещённых точек, а множеств 2ⁿ. Для пятнадцати точек это ещё терпимо — динамика по маскам, — для сотни уже нет. Бывает и тоньше: в задаче о рюкзаке состояний столько, сколько граммов во вместимости, и таблица растёт вместе с числами во входе, а не только с их количеством.

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

Где работает

Связь. Протокол маршрутизации RIP, описанный в RFC 1058 в 1988 году, основан на алгоритме Беллмана — Форда: маршрутизаторы обмениваются таблицами расстояний, и каждый строит свою по таблицам соседей — переход динамики, разнесённый по сети. Алгоритм Витерби (1967) восстанавливает переданную последовательность по искажённому шумом сигналу, перебирая не все последовательности, а лучшие пути к каждому состоянию кодера; им декодируют свёрточные коды в сотовой, спутниковой и космической связи. Подробнее — в статье об алгоритме Витерби.

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

Биология и картинки. Выравнивание генов и белков — Нидлман — Вунш и Смит — Уотерман. Сжатие фотографии по ширине без искажения главного — seam carving, кратчайший путь сверху вниз через пиксели.

Стихи, кролики и министр

Одно из самых старых правил в духе динамики записали знатоки стихосложения. В санскритской метрике слоги бывают краткие и долгие, долгий длится вдвое дольше. Сколько разных ритмов длиной n кратких долей можно составить? Последний слог либо краткий, и тогда перед ним ритм длины n − 1, либо долгий, и перед ним ритм длины n − 2. Значит, число ритмов длины n — сумма двух предыдущих: тот же вопрос «каким был последний шаг», с которого начинается любой переход. Так считал Вираханка около 700 года; его собственный текст утерян, но правило сохранилось в цитате у комментатора Гопалы (около 1135 года). Около 1150 года Хемачандра записал: сумма последнего и предпоследнего даёт число следующего размера. Получаются числа 1, 2, 3, 5, 8, 13, 21… — те самые, что Леонардо Пизанский, Фибоначчи, в 1202 году вывел в «Книге абака» из задачи о размножении кроликов.

Название появилось в 1950-е. Ричард Беллман, математик корпорации RAND, занимался многошаговыми процессами принятия решений — управлением запасами, производством, ракетами, — где каждое решение меняет условия для следующего. В 1954 году он изложил теорию в докладе на летней конференции математиков, а в 1957 году выпустил книгу «Dynamic Programming», где сформулировал принцип оптимальности. Слово «программирование» тогда значило составление планов, а не работу на компьютере. Почему Беллман выбрал именно такое название и при чём тут министр обороны, рассказано в главе курса.

Задачи

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