В этом параграфе мы реализуем разные алгоритмы динамического программирования и увидим, как они решают задачи, которые не поддавались решению с использованием «жадных» алгоритмов и подхода «разделяй и властвуй». Динамическое программирование на практике применяется в большом числе случаев. Оно подходит и для поиска похожих страниц в интернете, и для предсказывания генов в последовательностях ДНК.
В итоге вы узнаете, как одна идея позволяет автоматически исправлять орфографические ошибки и при этом находить разницу между двумя вариантами одного и того же текста.
Основная идея
Количество путей
Для понимания идеи, которая используется в подходе динамического программирования, предлагаем вам попробовать решить следующую головоломку.
Интерактивная головоломка «Количество путей». В нижеприведённой сети есть множество путей ведущих от $s$ к $t$, — например: $s \to b \to e \to t$ и $s \to a \to c \to d \to t$. Каково общее количество путей?
Так как мы начинаем с $s$, существует уникальный способ добраться до $s$. Давайте запишем:
Для $a$ и $b$ также существует просто один путь.
Так как существует только один путь к $a$ и только один к $b$, количество путей к $c$ составляет $1+1=2$ ($s \to a \to c$ и $s \to b \to c$).
Аналогичным образом для достижения $d$ необходимо прийти либо к $a$, либо к $c$. Существует только один путь до $a$ и два пути до $c$. Так количество путей, которые ведут к $d$, составляет $1+2=3$ ($s\to a \to d$, $s\to a \to c \to d$ и $s\to b \to c \to d$).
Количество путей, заканчивающихся на $e$, равно $1$, так как к $e$ можно прийти только от $b$.
До $c$ есть два пути, до $d$ — три пути, до $e$ — один. Выходит, что путей до $t$ существует $2+3+1=6$.
Динамическое программирование
Рассмотрим наше решение головоломки «Количество путей» и изложим основные идеи динамического программирования. Для узла $v$ — $paths(v)$ будет количеством путей от стартового узла $s$ к узлу $v$. Несомненно, $paths(s)=1$. Это называется базовый случай. Соответствующее значение для всех других узлов можно найти с помощью рекуррентного соотношения:
$$ paths(v)= \sum_{\text{все предшествующие $w$ от $v$}} paths(w) , $$ где предшественник $v$ — это узел, связанный ребром с $v$.
Многие алгоритмы динамического программирования используют одну схему:
— Вместо того, чтобы решать изначальную задачу, алгоритм решает несколько подзадач такого же типа.
— Алгоритм вычисляет решение для каждой подзадачи с помощью рекуррентного соотношения, в которое входят решения более мелких подзадач.
— Алгоритм сохраняет решения подзадач и таким образом избегает перевычисления.
Ориентированный ациклический граф: кратчайший путь
Теперь рассмотрим взвешенный граф, в котором у каждого ребра $e$ обозначена длина $length(e)$. Длина пути в таком графе определяется суммой длины рёбер.
Например, длина пути $s \to b \to e \to t$ составляет $5+7+4=16$. Какова минимальная длина пути от $s$ до $t$?
Так как каждый путь от $s$ до $t$ проходит через $c$, $d$ или $e$ перед тем, как прийти к $t$,
где $length(v)$ — минимальная длина пути от $s$ до $v$. Расстояния до $c$, $d$ и $e$ можно найти с помощью похожих рекуррентных соотношений:
Приведём рекуррентные соотношения для $a$ и $b$:
Наконец, базовый случай — это $length(s)=0$. С его помощью можно найти расстояние до всех узлов сети, включая наш узел $t$. Для этого нужно использовать вышеприведённые рекуррентные соотношения, которые можно записать в компактной форме: $$ length(v)= \min_{\text{все предшествующие $w$ от $v$}} {length(w) + length(w, v) }. $$
Для модельной ситуации удобно записывать результаты по мере того, как мы выполняем вычисления, прямо на изображении. Мы получаем следующие результаты.
💡 Остановитесь и подумайте:
Минимальная длина пути от $s$ до $t$ составляет $12$. Можете понять, как находится путь такой длины?
В алгоритме динамического программирования для этого выполняется бэктрекинг («поиск с возвратом») решений, которые привели к оптимальному результату. В особенности отметим один из трёх выборов, который приводит нас к значению $length(t)$.
Исходя из этого, мы можем заключить, что последнее ребро оптимального пути — это $c \to t$. Аналогично,
так мы приходим от $b$ к $c$. Таким образом, путь от $s$ до $t$ длиной $12$ составляет $$ s \to b \to c \to t . $$
У вышеприведённой сети есть удобное свойство. Оно заключается в том, что мы можем определять порядок её узлов, что обеспечивает следующее: каждый узел идет после всех предшествующих — то есть узлы, которые указывают на текущий узел (например, $c$, $d$ и $e$ предшествуют $t$). Сети с таким свойством называются ориентированные ациклические графы. Мы увидим, что многие алгоритмы динамического программирования используют ориентированные ациклические графы — явно или неявно.
Проектирование алгоритмов динамического программирования
Теперь, когда вы познакомились с несколькими алгоритмами динамического программирования, подведём итог и повторим основные шаги для проектирования таких алгоритмов.
— Определить подпроблемы. Первый и самый важный шаг — это идентифицировать подпроблемы и записать рекуррентное соотношение (с базовым случаем). Как правило, это делается через анализ структуры оптимального решения или через оптимизацию решения, использующего исчерпывающий поиск.
— Спроектировать рекурсивный алгоритм. Сделать из рекуррентного соотношения рекурсивный алгоритм: — сохранить решение каждой подзадачи в таблице; — перед решением подзадачи проверить, нет ли уже в таблице её решения (мемоизация).
— Спроектировать итерационный алгоритм. Сделать из рекурсивного алгоритма итерационный алгоритм: — инициализировать таблицу; — продвигаться от мелких подзадач к большим.
— Оценить время выполнения. Доказать верхнее ограничение времени выполнения. Обычно произведение количества подпроблем и времени, необходимого для решения подзадачи, предоставляет верхнее ограничение времени выполнения.
— Обнаружить решение. Обнаружить оптимальное решение, используя бэктрекинг рекуррентного соотношения.
— Экономить место. Использовать обычную структуру таблицы, чтобы проверить, можно ли сэкономить место по сравнению с более прямым решением.