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

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

Ключевые вопросы параграфа

  • В чём суть динамического программирования и как оно отличается от других стратегий?
  • Как выделить подзадачи и сформулировать рекуррентное соотношение?
  • Как реализовать и оптимизировать алгоритм, чтобы он работал быстро и экономно?

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

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

Основная идея

Количество путей

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

Интерактивная головоломка «Количество путей».

В нижеприведённой сети есть множество путей ведущих от к , — например: и . Каково общее количество путей?

algosy

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

algosy

Для и также существует просто один путь.

algosy

Так как существует только один путь к и только один к , количество путей к составляет ( и ).

algosy

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

algosy

Количество путей, заканчивающихся на , равно , так как к можно прийти только от .

algosy

До есть два пути, до — три пути, до — один. Выходит, что путей до существует .

algosy

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

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

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

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

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

Ориентированный ациклический граф: кратчайший путь

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

algosy

Например, длина пути составляет . Какова минимальная длина пути от до ?

Так как каждый путь от до проходит через , или перед тем, как прийти к ,

где — минимальная длина пути от до . Расстояния до , и можно найти с помощью похожих рекуррентных соотношений:

Приведём рекуррентные соотношения для и :

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

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

algosy

Остановитесь и подумайте:
Минимальная длина пути от до составляет . Можете понять, как находится путь такой длины?

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

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

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

У вышеприведённой сети есть удобное свойство. Оно заключается в том, что мы можем определять порядок её узлов, что обеспечивает следующее: каждый узел идет после всех предшествующих — то есть узлы, которые указывают на текущий узел (например, , и предшествуют ). Сети с таким свойством называются ориентированные ациклические графы. Мы увидим, что многие алгоритмы динамического программирования используют ориентированные ациклические графы — явно или неявно.

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

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

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

  2. Спроектировать рекурсивный алгоритм. Сделать из рекуррентного соотношения рекурсивный алгоритм:

    • сохранить решение каждой подзадачи в таблице;
    • перед решением подзадачи проверить, нет ли уже в таблице её решения (мемоизация).
  3. Спроектировать итерационный алгоритм. Сделать из рекурсивного алгоритма итерационный алгоритм:

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

  5. Обнаружить решение. Обнаружить оптимальное решение, используя бэктрекинг рекуррентного соотношения.

  6. Экономить место. Использовать обычную структуру таблицы, чтобы проверить, можно ли сэкономить место по сравнению с более прямым решением.

Что дальше

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

Далее — задача «Размен-2». Вы увидите, как динамическое программирование позволяет находить минимальное количество монет, даже когда жадный алгоритм не справляется.

А пока вы не ушли дальше — закрепите материал на практике:

  • Отметьте, что урок прочитан, при помощи кнопки ниже.
  • Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Чтобы добавить в заметки выделенный текст, нажмите Ctrl + E
Предыдущий параграф7.7. Чему вы научились
Следующий параграф8.2. Задача «Размен 2»