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