Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

Многие задачи связаны с минимизацией или максимизацией целевого значения: найти кратчайший путь, получить наибольшую прибыль и т. д. Такие задачи называются задачами оптимизации . Когда решением является последовательность вариантов, мы часто используем стратегию ветвей и границ . Ее цель состоит в том, чтобы выиграть время за счет быстрого обнаружения и отбрасывания плохих вариантов. Чтобы понять, каким образом они ищутся, мы сначала должны разобраться в понятиях «верхняя граница» и «нижняя граница».

Границы обозначают диапазон значения. Верхняя граница устанавливает предел того, каким высоким оно может быть. Нижняя граница — это наименьшее значение, на которое стоит надеяться; она гарантирует, что любое значение либо равно ей, либо ее превышает.

Мы порой легко находим решения, близкие к оптимальным: короткий путь — но, возможно, не самый короткий; большая прибыль — но, возможно, не максимальная. Они дают границы оптимального решения. К примеру, любой короткий маршрут из одной точки в другую никогда не будет короче расстояния между ними по прямой. Следовательно, расстояние по прямой является нижней границей самого короткого пути.

В задаче о жадном грабителе и рюкзаке (см. раздел «Эвристические алгоритмы» ) прибыль, полученная посредством 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 ( n 2). Однако мы можем быстро получить верхние и нижние границы оптимальной прибыли при помощи функций powdered_knapsack и greedy_knapsack. Давайте попробуем это сделать на примере задачи о рюкзаке (табл. 3.3).

Рисунок справа иллюстрирует ситуацию перед началом заполнения рюкзака. В первом поле находятся неупакованные предметы, которые нам предстоит рассмотреть. Второе поле представляет свободное место в рюкзаке и предметы, которые уже уложены. Выполнение функции greedy_knapsack дает прибыль 39, а powdered_knapsack — 52,66. Это означает, что оптимальная прибыль находится где-то посередине. Как мы знаем из раздела «Разделяй и властвуй», эта задача с n предметами делится на две подзадачи с n — 1 предметами. Первая подзадача подразумевает, что предмет A был взят, вторая — что он не был взят:

Мы вычисляем верхнюю и нижнюю границы для этих двух подзадач. Каждая имеет нижнюю границу, равную 48: теперь мы знаем, что оптимальное решение находится между 48 и 52. Давайте рассмотрим подзадачу справа, поскольку у нее более интересные границы: