В этом параграфе мы реализуем разные алгоритмы динамического программирования и увидим, как они решают задачи, которые не поддавались решению с использованием «жадных» алгоритмов и подхода «Разделяй и властвуй». Вы увидите, как сложную задачу можно разбить на подзадачи, сохранить их решения и на основе этого построить общий ответ. На примере подсчёта путей и кратчайших маршрутов вы научитесь проектировать алгоритмы с повторным использованием вычислений.
В итоге вы узнаете, как одна идея позволяет автоматически исправлять орфографические ошибки и при этом находить разницу между двумя вариантами одного и того же текста.
Ключевые вопросы параграфа
- В чём суть динамического программирования и как оно отличается от других стратегий?
- Как выделить подзадачи и сформулировать рекуррентное соотношение?
- Как реализовать и оптимизировать алгоритм, чтобы он работал быстро и экономно?
Алгоритмы динамического программирования
Динамическое программирование на практике применяется в большом числе случаев. Оно подходит и для поиска похожих страниц в интернете, и для предсказывания генов в последовательностях ДНК.
Основная идея
Количество путей
Для понимания идеи, которая используется в подходе динамического программирования, предлагаем вам попробовать решить следующую головоломку.
Интерактивная головоломка «Количество путей».
В нижеприведённой сети есть множество путей ведущих от к , — например: и . Каково общее количество путей?
Так как мы начинаем с , существует уникальный способ добраться до . Давайте запишем:
Для и также существует просто один путь.
Так как существует только один путь к и только один к , количество путей к составляет ( и ).
Аналогичным образом для достижения необходимо прийти либо к , либо к . Существует только один путь до и два пути до . Так количество путей, которые ведут к , составляет (, и ).
Количество путей, заканчивающихся на , равно , так как к можно прийти только от .
До есть два пути, до — три пути, до — один. Выходит, что путей до существует .
Динамическое программирование
Рассмотрим наше решение головоломки «Количество путей» и изложим основные идеи динамического программирования. Для узла — будет количеством путей от стартового узла к узлу . Несомненно, . Это называется базовый случай. Соответствующее значение для всех других узлов можно найти с помощью рекуррентного соотношения:
где предшественник — это узел, связанный ребром с .
Многие алгоритмы динамического программирования используют одну схему:
— Вместо того, чтобы решать изначальную задачу, алгоритм решает несколько подзадач такого же типа.
— Алгоритм вычисляет решение для каждой подзадачи с помощью рекуррентного соотношения, в которое входят решения более мелких подзадач.
— Алгоритм сохраняет решения подзадач и таким образом избегает перевычисления.
Ориентированный ациклический граф: кратчайший путь
Теперь рассмотрим взвешенный граф, в котором у каждого ребра обозначена длина . Длина пути в таком графе определяется суммой длины рёбер.
Например, длина пути составляет . Какова минимальная длина пути от до ?
Так как каждый путь от до проходит через , или перед тем, как прийти к ,
где — минимальная длина пути от до . Расстояния до , и можно найти с помощью похожих рекуррентных соотношений:
Приведём рекуррентные соотношения для и :
Наконец, базовый случай — это . С его помощью можно найти расстояние до всех узлов сети, включая наш узел . Для этого нужно использовать вышеприведённые рекуррентные соотношения, которые можно записать в компактной форме:
Для модельной ситуации удобно записывать результаты по мере того, как мы выполняем вычисления, прямо на изображении. Мы получаем следующие результаты.
Остановитесь и подумайте:
Минимальная длина пути от до составляет . Можете понять, как находится путь такой длины?
В алгоритме динамического программирования для этого выполняется бэктрекинг («поиск с возвратом») решений, которые привели к оптимальному результату. В особенности отметим один из трёх выборов, который приводит нас к значению .
Исходя из этого, мы можем заключить, что последнее ребро оптимального пути — это . Аналогично,
так мы приходим от к . Таким образом, путь от до длиной составляет
У вышеприведённой сети есть удобное свойство. Оно заключается в том, что мы можем определять порядок её узлов, что обеспечивает следующее: каждый узел идет после всех предшествующих — то есть узлы, которые указывают на текущий узел (например, , и предшествуют ). Сети с таким свойством называются ориентированные ациклические графы. Мы увидим, что многие алгоритмы динамического программирования используют ориентированные ациклические графы — явно или неявно.
Проектирование алгоритмов динамического программирования
Теперь, когда вы познакомились с несколькими алгоритмами динамического программирования, подведём итог и повторим основные шаги для проектирования таких алгоритмов.
-
Определить подпроблемы. Первый и самый важный шаг — это идентифицировать подпроблемы и записать рекуррентное соотношение (с базовым случаем). Как правило, это делается через анализ структуры оптимального решения или через оптимизацию решения, использующего исчерпывающий поиск.
-
Спроектировать рекурсивный алгоритм. Сделать из рекуррентного соотношения рекурсивный алгоритм:
- сохранить решение каждой подзадачи в таблице;
- перед решением подзадачи проверить, нет ли уже в таблице её решения (мемоизация).
-
Спроектировать итерационный алгоритм. Сделать из рекурсивного алгоритма итерационный алгоритм:
- инициализировать таблицу;
- продвигаться от мелких подзадач к большим.
-
Оценить время выполнения. Доказать верхнее ограничение времени выполнения. Обычно произведение количества подпроблем и времени, необходимого для решения подзадачи, предоставляет верхнее ограничение времени выполнения.
-
Обнаружить решение. Обнаружить оптимальное решение, используя бэктрекинг рекуррентного соотношения.
-
Экономить место. Использовать обычную структуру таблицы, чтобы проверить, можно ли сэкономить место по сравнению с более прямым решением.
Что дальше
Теперь вы знаете, как работает динамическое программирование, — от базовых случаев и рекурсии до оптимизированных решений с таблицами и перебором подзадач. Вы познакомились с идеей сохранения промежуточных результатов, научились вычислять количество путей в графе и находить кратчайшие маршруты. Этот подход ляжет в основу всех задач этой главы.
Далее — задача «Размен-2». Вы увидите, как динамическое программирование позволяет находить минимальное количество монет, даже когда жадный алгоритм не справляется.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.