Во время решения задачи иногда приходится выполнять одни и те же вычисления многократно[41]. Динамическое программирование позволяет идентифицировать повторяющиеся подзадачи, чтобы можно было выполнить каждую всего один раз. Общепринятый метод, предназначенный для этого, основан на запоминании и имеет «говорящее» название.
Мемоизация Фибоначчи
Помните алгоритм вычисления чисел Фибоначчи? Его дерево рекурсивных вызовов (см. рис. 3.3) показывает, что fib(3) вычисляется многократно. Мы можем это исправить, сохраняя результаты по мере их вычисления и делая новые вызовы fib только для тех вычислений, результатов которых еще нет в памяти (рис. 3.14). Этот прием
Рис. 3.14. Дерево рекурсивных вызовов для dfib. Зеленые прямоугольники обозначают вызовы, не выполняемые повторно
многократного использования промежуточных результатов называется мемоизацией. Он повышает производительность функции fib:
Мемоизация предметов в рюкзаке
Очевидно, что в дереве рекурсивных вызовов для задачи о рюкзаке (см. рис. 3.13) имеются многократно повторяемые вызовы. Применение того же самого приема, который мы использовали для функции Фибоначчи, позволяет избежать этих повторных вызовов и в итоге уменьшить объем вычислений (рис. 3.15).
Рис. 3.15. Рекурсивное решение задачи о рюкзаке при помощи мемоизации
Динамическое программирование позволяет добиться от чрезвычайно медленного программного кода приемлемого быстродействия. Тщательно анализируйте свои алгоритмы, чтобы убедиться, что в них нет повторных вычислений. Как мы увидим далее, иногда перекрывающиеся подзадачи могут порождать проблемы.
Лучшая сделка снизу вверх
Дерево рекурсии для функции trade (см. рис. 3.12) не имеет повторных вызовов, и все равно делает повторные вычисления. Он просматривает вход, чтобы найти максимальное и минимальное значения. Затем входные данные разбиваются на две части, и рекурсивные вызовы анализируют их снова, чтобы найти максимум и минимум в каждой половине[42]. Нам нужен другой принцип, для того чтобы избежать этих повторных проходов.
До сих пор мы использовали нисходящий подход, где объем входных данных постепенно уменьшается, пока не будут достигнуты базовые случаи. Но мы также можем пойти снизу вверх: сначала вычислить базовые случаи, а затем раз за разом собирать их, пока не получим общий результат. Давайте решим задачу о лучшей сделке (см. раздел «Полный перебор» ) таким способом.
Пусть P(n) — это цена в n-й день, а B(n) — лучший день для покупки при продаже в n-й день. Если мы продаем в первый день, то купить у нас получится только тогда же, других вариантов нет, поэтому B(1) = 1. Но если мы продаем во второй день, B(2) может равняться 1 либо 2:
• P(2) <P(1)! B(2) = 2 (купить и продать в день 2);
• P(2) ≥ P(1)! B(2) = 1 (купить в день 1, продать в день 2).
День с самой низкой ценой перед днем 3, но не в день 3 — это B(2). Потому для B(3):
• P(3) < цена в день B(2) —>B(3) = 3.
• P(3) ≥ цена в день B(2) —>B(3) = B(2).
Обратите внимание, что день с самой низкой ценой перед днем 4 будет B(3). Фактически для каждого n день с самой низкой ценой перед днем n — B(n — 1). Мы можем это использовать, чтобы выразить B(n) через B(n — 1):
Когда у нас есть все пары [n, B(n)] для для каждого дня n, решением является пара, которая дает самую высокую прибыль. Следующий алгоритм решает задачу, вычисляя все значения B снизу вверх:
function trade_dp(P)
····B[1] ← 1
····sell_day ← 1
····best_profit ← 0
····for each n from 2 to P.length
········if P[n] < P[B[n-1]]
············B[n] ← n
········else
············B[n] ← B[n-1]
········profit ← P[n] — P[B[n]]
········if profit > best_profit
············sell_day ← n
············best_profit ← profit
····return (sell_day, B[sell_day])
Алгоритм выполняет фиксированное число простых операций для каждого элемента входного списка, следовательно, он имеет сложность O(n). Это огромный рывок в производительности по сравнению со сложностью предыдущего алгоритма O(n log n) — и совершенно несравнимо со сложностью O(n2) метода полного перебора. Этот алгоритм также имеет пространственную сложность O(n), поскольку вспомогательный вектор B содержит столько же элементов, что и входные данные. Из приложения IV вы узнаете, как сэкономить память за счет создания алгоритма с пространственной сложностью O(1).
3.8. Ветви и границы
Многие задачи связаны с минимизацией или максимизацией целевого значения: найти кратчайший путь, получить наибольшую прибыль и т. д. Такие задачи называются задачами оптимизации. Когда решением является последовательность вариантов, мы часто используем стратегию ветвей и границ. Ее цель состоит в том, чтобы выиграть время за счет быстрого обнаружения и отбрасывания плохих вариантов. Чтобы понять, каким образом они ищутся, мы сначала должны разобраться в понятиях «верхняя граница» и «нижняя граница».
Верхние и нижние границы
Границы обозначают диапазон значения. Верхняя граница устанавливает предел того, каким высоким оно может быть. Нижняя граница — это наименьшее значение, на которое стоит надеяться; она гарантирует, что любое значение либо равно ей, либо ее превышает.
Мы порой легко находим решения, близкие к оптимальным: короткий путь — но, возможно, не самый короткий; большая прибыль — но, возможно, не максимальная. Они дают границы оптимального решения. К примеру, любой короткий маршрут из одной точки в другую никогда не будет короче расстояния между ними по прямой. Следовательно, расстояние по прямой является нижней границей самого короткого пути.
В задаче о жадном грабителе и рюкзаке (см. раздел «Эвристические алгоритмы» ) прибыль, полученная посредством greedy_knapsack, является нижней границей оптимальной прибыли (она может быть или не быть близкой к оптимальной прибыли). Теперь представим версию задачи о рюкзаке, в которой вместо предметов у нас сыпучие материалы, и мы можем насыпать их в рюкзак, сколько поместится. Эта версия задачи решается «жадным» способом: просто продолжайте насыпать материалы с самым высоким соотношением стоимости и веса:
function powdered_knapsack(items, max_weight)
····bag_weight ← 0
····bag_items ← List.new
····items ← sort_by_value_weight_ratio(items)
····for each i in items
········weight ← min(max_weight — bag_weight,
·····················i.weight)
········bag_weight ← bag_weight + weight
········value ← weight * i.value_weight_ratio
········bagged_value ← bagged_value + value
········bag_items.append(item, weight)
····return bag_items, bag_value
Добавление ограничения неделимости предметов только уменьшит максимально возможную прибыль, потому что нам придется менять последнюю уложенную в рюкзак вещь на что-то подешевле. Это означает, что powdered_knapsack дает верхнюю границу оптимальной прибыли с неделимыми предметами[43].
Ветви и границы в задаче о рюкзаке
Мы уже убедились, что поиск оптимальной прибыли в задаче о рюкзаке требует дорогих вычислений O(n2). Однако мы можем быстро получить верхние и нижние границы оптимальной прибыли при помощи функций powdered_knapsack и greedy_knapsack. Давайте попробуем это сделать на примере задачи о рюкзаке (табл. 3.3).
Таблица 3.3. Верхняя и нижняя границы в задаче о рюкзакеПредмет Стоимость Вес Соотношение стоимости и веса Макс. вместимость A 20 5 4,00 B 19 4 4,75 C 16 2 8,00 10 D 14 5 2,80 E 13 3 4,33 F 9 2 4,50
Рисунок справа иллюстрирует ситуацию перед началом заполнения рюкзака. В первом поле находятся неупакованные предметы, которые нам предстоит рассмотреть. Второе поле представляет свободное место в рюкзаке и предметы, которые уже уложены. Выполнение функции greedy_knapsack дает прибыль 39, а powdered_knapsack — 52,66. Это означает, что оптимальная прибыль находится где-то посередине. Как мы знаем из раздела «Разделяй и властвуй», эта задача с n предметами делится на две подзадачи с n — 1 предметами. Первая подзадача подразумевает, что предмет A был взят, вторая — что он не был взят:
Мы вычисляем верхнюю и нижнюю границы для этих двух подзадач. Каждая имеет нижнюю границу, равную 48: теперь мы знаем, что оптимальное решение находится между 48 и 52. Давайте рассмотрим подзадачу справа, поскольку у нее более интересные границы:
Крайняя левая подзадача имеет самую многообещающую верхнюю границу. Давайте продолжим наш анализ и выполним разбиение этой подзадачи:
Теперь мы можем сделать важные выводы. Выделенная цветом подзадача имеет нижнюю границу 49, которая равна ее верхней границе. Это означает, что оптимальная прибыль здесь должна равняться строго 49. Кроме того, обратите внимание, что 49 больше верхних границ во всех других ветвях, которые были проанализированы. Никакая другая ветвь не даст большую прибыль, чем 49, а значит, мы можем исключить их все из дальнейшего поиска.
Рациональное использование верхних и нижних границ позволило нам найти оптимальную прибыль, выполнив совсем немного вычислений. Мы динамически адаптировали наше пространство поиска по мере анализа возможностей.
Вот общие принципы работы метода ветвей и границ:
1) разделить задачу на подзадачи;
2) найти верхние и нижние границы каждой подзадачи;
3) сравнить границы подзадач всех ветвей;
4) выбрать самую многообещающую задачу и вернуться к шагу 1.
Если вы помните, стратегия поиска с возвратом (см. соответствующий раздел) тоже позволяет найти решение без обследования каждого возможного варианта. В случае поиска с возвратом мы исключаем пути, изучив каждый из них так далеко, как это возможно, и останавливаемся, когда нас устраивает решение. В случае же с методом ветвей и границ мы заранее определяем бесперспективные пути и не тратим впустую энергию на их обследование.
Подведем итоги
