Понять интуицию, лежащую в основе техники, которая решает миниатюрные зависимые задачи, чтобы окончательно объяснить рассматриваемую проблему.

Что такое динамическое программирование?

Это метод решения особого типа проблем, которые можно разбить на множество зависимых подзадач. Под зависимостью я подразумеваю, что для решения одной подзадачи вам нужен ответ на другие подзадачи. Это отличает динамическое программирование (dp) от других методов, таких как разделяй и властвуй, где мы обычно создаем независимые подзадачи. Одно из наиболее интуитивно понятных объяснений dp определяет его как ориентированный граф, где узлы являются подзадачами, а ребра между двумя узлами обозначают зависимость одной проблемы от другой.

Чтобы привести один пример, мы должны найти возможный короткий путь от S до D (см. Рис. 1). Присмотритесь, вы можете пройти к D через B или C, поэтому, по логике, кратчайший путь должен проходить через один из них. Чтобы сформулировать это, давайте определим dist (x) = кратчайшее расстояние от S до любого узла «x». Нам нужно найти dist (D), которое также можно записать как,

Таким же образом dist (B) можно записать через A, а dist (C) через S. Решая каждую из них, мы получаем dist (D), то есть предполагаемое решение. Подводя итог, мы ищем проблемы, которые могут быть разбиты на зависимые подзадачи, и они становятся кандидатами на применение DP.

Возможные подходы

Вообще говоря, есть два способа решить проблемы dp:

  1. Нисходящий подход: здесь мы применяем рекурсивную технику для детализации всех зависимых подзадач, необходимых для решения основной проблемы. Здесь мы начинаем с вершины, то есть с последней проблемы, но чтобы ее найти, мы должны решить все подзадачи, поэтому спустимся вниз, чтобы решить их все. После их объединения у нас есть окончательное решение. Например, в последнем разделе мы начали с dist (D), то есть с основной проблемы, и решили dist (B), dist (C), dist (A) и т. Д., Чтобы найти ее.
  2. Подход снизу вверх: здесь мы начинаем с базового случая, то есть с наименьшей возможной подзадачи, и продолжаем двигаться вперед, пока не решим последнюю проблему. Например, если бы мы начали с S, затем перешли к C, A, а затем дальше, пока не достигли D, это был бы подход снизу вверх.

Что с габаритами?

Мы определили подзадачи и их зависимости, другие важные объекты в dp - это зависимые элементы или переменные. Количество этих переменных определяет масштаб проблемы. Если проблема зависит от 1 переменной, это проблема 1D dp, аналогично в случае 2 переменных - проблема 2D dp. Давайте рассмотрим примеры для каждого,

1-мерная задача DP

Предположим, мы хотим найти число фибоначчи в определенном индексе последовательности. Итак, fib (n) = n-й элемент в последовательности Фибоначчи. Так как же нам решить эту проблему с помощью dp? Давайте сначала попытаемся определить подзадачи, есть ли какая-либо зависимость fib (n) от любого из предшественников, таких как fib (n-1), fib (n-2)… fib (0)? Конечно, согласно определению, fib (n) = fib (n-1) + fib (n-2). То же самое происходит с fib (n-1) и fib (n-2) до тех пор, пока мы не дойдем до базовых случаев fib (0) = 0 или fib (1) = 1. Чтобы сформулировать,

Очевидно, что мы используем подход сверху вниз (мы также можем использовать восходящий поток), а зависимая переменная равна только 1, то есть «n», который является порядковым номером. Используя это, мы можем решить проблему Фибоначчи. Давайте закодируем это,

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

Здесь мы хотим решить для fib (5), который вызывается один раз, но другие подзадачи имеют различные вызовы, такие как fib (4) - 1, fib (3) - 2, fib (2) - 3, fib (1). - 5, fib (0) - 3. Совершенно не интуитивно решать одни и те же проблемы несколько раз, и мы можем справиться с этим, если сохраним решение проблемы, а в следующий раз, когда оно будет вызвано, просто передать сохраненный ответ. Это называется мемоизацией. Изменяя предыдущий код, чтобы сделать его более оптимальным,

2-мерная задача DP

У этого типа проблем есть две зависимые переменные. Давайте возьмем пример расстояния редактирования. В этой задаче нам даны две строки, и мы должны найти меру различия между двумя строками. Это вычисляется путем размещения (визуально) одной строки поверх другой и попытки найти лучшую точку соответствия, чтобы, применяя минимальные изменения, мы могли преобразовать одну строку в другую. Отсюда и название «расстояние редактирования». Поддерживаемые изменения: вставка, удаление и замена. Поскольку одна из основных задач требует поиска наилучшей точки подгонки, одна и та же пара струн с разным выравниванием или подгонкой даст разное расстояние редактирования. Например,

Рассмотрим «снежный» и «солнечный», на рисунке выше показаны два возможных варианта. Теперь, как рассчитывается стоимость или расстояние редактирования? Возьмите выравнивание по левому краю, нам нужно выполнить 3 редактирования (следовательно, стоимость = 3), чтобы преобразовать снежный в солнечный, а именно: (1) вставить U в индексе 1, (2) заменить O на N в индексе 3 и (3) удалить W в индексе 4.

Теперь давайте посмотрим, можем ли мы применить dp для решения этой проблемы, для этого нам нужно определить зависимые подзадачи. Наша основная проблема - найти расстояние редактирования между двумя строками x [1..m] (длиной m) и y [1… n] (длиной n). Что, если мы попытаемся решить проблему для некоторого префикса x, то есть x [1… i] и y, то есть y [1… j]? Можем ли мы использовать это для решения следующей проблемы? Возьмем предыдущий пример. Если мы знаем расстояние редактирования для «sno» и «sun», можем ли мы использовать это для решения для «snow» и «sunn»? Взяв последний символ этих строк, то есть 'w' и 'n', формально мы можем выполнить только три операции: (1) либо удалить 'w' (2) вставить 'n', либо (3) сопоставить 'o' с ' w ', и в этом случае они могут быть одинаковыми или разными (что приводит к замене), здесь они разные. В общем, мы можем выполнять эти операции с любой парой x [i] и y [j]. В случае (1) мы удаляем x [i], и нам нужно найти оставшиеся x [1 ... i-1] и y [1 ... j], для (2) мы вставляем y [i], и мы решаем относительно x [1… i] и y [1… j-1] или (3) мы решаем относительно x [1… i-1] и y [1… j-1]. Отлично! Во всех этих случаях нам просто нужно решить меньшую проблему и продолжать добавлять стоимость возможных операций редактирования, давайте пока оставим их все равными 1. Наши формулы теперь становятся,

Поскольку проблема имеет 2 измерения - индекс каждой строки - нам необходимо поддерживать 2-мерную таблицу для хранения всех обработанных расстояний редактирования.

Здесь ячейка (i, j) определяет расстояние редактирования, необходимое для преобразования строки_1 до индекса i в строку_2 до индекса j. Наша цель - найти значение в ячейке (m, n). Кроме того, поскольку расстояние редактирования в (i, j) требует значения 3 разных ячеек, нам нужно пройти по таблице таким образом, чтобы, когда мы находимся в (i, j), мы уже решили для (i-1, j ), (i, j-1) и (i-1, j-1). Наконец, определение базового случая, когда либо i = 0, либо j = 0, поэтому (0, 5) означает преобразование пустой строки в строку длиной 5, что составляет просто 5 вставок, следовательно, стоимость равна 5, то же самое для (5,0) . Чтобы учесть это, мы добавляем дополнительные столбец и строку в таблицу с этими значениями по умолчанию. Следовательно, псевдокод:

Давайте закодируем это,

Решая проблему для "экспоненты" и "полинома", наша таблица преобразуется в

Таким образом, окончательное расстояние редактирования между двумя струнами равно 6.

Заключение

Мы просто коснулись поверхности техники и попытались решить несколько классических задач. Самая важная и, возможно, самая сложная часть в dp - это правильно определить под-проблемы, этот процесс иногда требует большого количества истреблений. Идея поста заключалась в том, чтобы предоставить читателям краткое введение и интуитивное понимание логики определения размеров и подзадач. Сделав это, мы в основном решили проблему, осталось только объединить подзадачи в красивую формулировку, а все остальное идеально рассыпается на части. SS

Ссылка

[1] Алгоритмы, книга Христоса Пападимитриу, Санджоя Дасгупты и Умеша Вазирани.

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

Ваше здоровье.