Алгоритмы - Разработка и применение - 2016 год

Аппроксимации с произвольной точностью: задача о рюкзаке - Аппроксимирующие алгоритмы

Когда к вам обращаются за помощью люди, столкнувшиеся с NP-сложной задачей оптимизации, они часто надеются получить алгоритм, способный выдать решение в пределах, скажем, 1 % от оптимума — или по крайней мере в относительно небольшом диапазоне от оптимума. С этой точки зрения аппроксимирующие алгоритмы, рассматривавшиеся ранее, были довольно слабыми: решения с множителем 2 для минимума задач выбора центров и вершинного покрытия (то есть превышение оптимума может достигать 100 %). С алгоритмом покрытия множества из раздела 10.3 дело обстоит еще хуже: его стоимость даже не лежит в пределах фиксированного постоянного множителя от возможного минимума!

В основе этого состояния дел лежит важный факт: все NP-полные задачи, как вам известно, эквивалентны в отношении разрешимости с полиномиальным временем; но в предположении Р ≠ NPони существенно различаются по возможности эффективной аппроксимации их решений. В некоторых случаях ограничения аппроксимируемости могут быть доказаны. Например, если P ≠ NP, то гарантия, предоставляемая алгоритмом выбора центров, является лучшей из возможных среди всех алгоритмов с полиномиальным временем. Аналогичным образом гарантия, предоставляемая алгоритмом покрытия множества, как бы плохо она ни выглядела, очень близка к лучшей из возможных (если только не окажется, что P = NP). Для других задач — например, задачи о вершинном покрытии — приведенный нами аппроксимирующий алгоритм является лучшим из известных, но вопрос о том, не существуют ли алгоритмы с полиномиальным временем, обладающий лучшими гарантиями, остается открытым. В этой книге тема нижних границ аппроксимируемости не рассматривается; хотя некоторые нижние границы такого типа доказываются не так уж сложно (например, как в задаче о выборе центров), доказательства во многих случаях перегружаются огромным количеством технических подробностей.

Задача

В этом разделе рассматривается NP-полная задача, для которой возможно построение алгоритма с полиномиальным временем, обеспечивающим очень сильную аппроксимацию. Мы рассмотрим слегка обобщенную версию задачи о рюкзаке (или задачи о сумме подмножеств). Допустим, имеется n предметов, которые нужно уложить в рюкзак. Каждый предмет i = 1, ..., n обладает двумя целочисленными параметрами: весом w_i и значением v_i. Для заданной емкости рюкзака Wтребуется найти подмножество S предметов, обладающее максимальным значением, при условии, что общий вес подмножества не превышает W. Другими словами, требуется максимизировать при условии

На какую точность аппроксимации можно рассчитывать? Наш алгоритм получает на входе веса и значения, определяющие задачу, а также дополнительный параметр є (требуемая точность). Он находит подмножество S, суммарный вес которого не превышает W, с суммарным значением уступающим максимально возможному не более чем на (1 + є). Алгоритм выполняется за полиномиальное время для любого фиксированного выбора є > 0; при этом зависимость от е не является полиномиальной. Назовем этот алгоритм схемой аппроксимации с полиномиальным временем.

Возникает вопрос: возможно ли, чтобы такой сильный аппроксимирующий алгоритм выполнялся за полиномиальное время, когда задача о рюкзаке является NP-сложной? Ведь с целочисленными значениями при достаточном приближении к оптимальному значению мы должны достичь самого оптимума! Загвоздка кроется в неполиномиальной зависимости от желаемой точности: для любого фиксированного выбора є — например, є = 0,5, є = 0,2 или даже є = 0,01 — алгоритм выполняется за полиномиальное время, но при замене е все меньшими и меньшими значениями время выполнения возрастает. К тому времени, когда е станет достаточно малым для гарантированного достижения оптимума, алгоритм уже не будет алгоритмом с полиномиальным временем.

Разработка алгоритма

В разделе 6.4 рассматривались алгоритмы для задачи о сумме подмножеств — частного случая задачи о рюкзаке, в котором v_i = w_i для всех элементов i. Для этого частного случая был предложен алгоритм динамического программирования, выполнявшийся за время O(nW) при условии, что веса являются целыми числами. Алгоритм естественным образом расширяется на более общую задачу о рюкзаке (см. конец раздела 6.4). Алгоритм, приведенный в разделе 6.4, хорошо работает для малых весов (даже если значения велики). Также возможно определить алгоритм динамического программирования для случая с малыми значениями (даже при больших весах). В конце раздела приводится алгоритм динамического программирования для этого случая, выполняемый за время O(n²V*), где v* = max_iv_i. Учтите, что этот алгоритм не выполняется за полиномиальное время: он только псевдополиномиален из-за зависимости от размера значений v_i. Так как NР-полнота этой задачи была доказана в главе 8, не стоит рассчитывать, что нам удастся найти алгоритм с полиномиальным временем.

Алгоритмы с псевдополиномиальной зависимостью от значений часто могут использоваться для разработки схем аппроксимации с полиномиальным временем, и разработанный нами алгоритм очень наглядно демонстрирует эту базовую стратегию. В частности, мы используем алгоритм динамического программирования с временем выполнения O(n²V*) для разработки схемы аппроксимации с полиномиальным временем: если значения являются малыми целыми числами, то значение v* мало, а задача уже может быть решена за полиномиальное время. С другой стороны, если значения велики, то нам не обязательно работать с ними в точном виде, так как нас интересует только аппроксимированно-оптимальное решение. Мы используем параметр округления b (значение которого будет задано позднее) и будем рассматривать значения, округленные до целого, кратного b. Алгоритм динамического программирования будет использоваться для решения задачи с округленными значениями. А точнее, для каждого элемента i за его округленное значение принимается Обратите внимание: округленное и исходное значения достаточно близки друг к другу.

(11.34) Для каждого элемента i выполняется

Что нам дает округление? Если значения были изначально большими, то меньше они не станут. Однако все округленные значения представляют собой целые числа, кратные общему параметру b, поэтому вместо решения задачи с округленными значениями можно сменить “единицы измерения”; мы разделим все значения на b и получим эквивалентную задачу Пусть для i = 1, ..., n.

(11.35) Задача о рюкзаке со значениями и масштабированная версия задачи со значениями имеют одинаковое множество оптимальных решении, оптимальные решения отличаются точно множителем b, а масштабированные значения являются целочисленными.

Теперь все готово к представлению аппроксимирующего алгоритма. Будем считать, что все элементы имеют вес, не превышающий W (так как элементы с весом w_i > W заведомо не входят в решение и поэтому могут быть удалены). Также для простоты будем считать, что є^-1 является целым числом.

Анализ алгоритма

Для начала отметим, что найденное решение по меньшей мере является действительным; то есть Это следует из того, что мы округляли только значения, но не веса. Именно по этой причине нам понадобится новый алгоритм динамического программирования, описанный в конце этого раздела.

(11.36) Общий вес множества элементов S, возвращаемого алгоритмом, не превышает W, то есть

Далее мы докажем, что этот алгоритм выполняется за полиномиальное время.

(11.37) Алгоритм Knapsack-Approx выполняется за полиномиальное время для любого фиксированного є > 0.

Доказательство. Присваивание b и округление очевидно могут быть выполнены за полиномиальное время. Основные затраты времени в этом алгоритме связаны с решением округленной задачи средствами динамического программирования. Вспомните, что для задач с целыми значениями используемый нами алгоритм динамического программирования выполняется за время O(n²v*), где v* = max_iv_i.

Теперь мы применим этот алгоритм к экземпляру, в котором каждый элемент i имеет вес w_i и значение Чтобы определить время выполнения, необходимо определить Элемент j с максимальным значением v_j = max_iv_i также имеет максимальное значение в округленной задаче, так что Следовательно, общее время выполнения алгоритма составляет O(n³є^-1). Обратите внимание: для любого фиксированного є > 0 это полиномиальное время, как и было заявлено; но зависимость от требуемой точности є не полиномиальна, так как время выполнения включает є^-1 вместо log є^-1. ■

Остается решить ключевой вопрос: насколько хорошее решение дает этот алгоритм? Утверждение (11.34) показывает, что используемые значения близки к реальным значениям v_i, а это подсказывает, что полученное решение не может быть далеко от оптимального.

(11.38) Если S — решение, найденное алгоритмом Knapsack-Approx, и S* — любое другое решение, удовлетворяющее то

Доказательство. Пусть S* — любое множество, удовлетворяющее Наш алгоритм находит оптимальное решение со значениями так что мы знаем, что

Округленные значения и реальные значения v. достаточно близки согласно (11.34), поэтому мы получаем цепочку неравенств

Она показывает, что значение решения, полученного нами, максимум на nb меньше максимально возможного значения. Мы хотели получить относительную погрешность, показывающую, что полученное значение максимум в (1 + є) раз меньше возможного максимума, поэтому сейчас нужно сравнить nb со значением

Пусть j — элемент с наибольшим значением; в соответствии с нашим выбором b имеем Из нашего предположения о том, что каждый элемент сам по себе помещается в рюкзак (w_i≤ W для всех i), следует Наконец, приведенная выше цепочка неравенств означает, что а следовательно, Отсюда следует для є ≤ 1, и в конечном итоге

Новый алгоритм динамического программирования для задачи о рюкзаке

Чтобы решить задачу методом динамического программирования, необходимо определить полиномиальное множество задач. Алгоритм динамического программирования, определенный ранее в ходе анализа задачи о рюкзаке, использует подзадачи в форме OPT(i, w): подзадача нахождения максимального значения любого решения с использованием подмножества элементов 1, ..., i и рюкзака с весом w. При больших весах это множество задач будет большим. Нам нужно множество подзадач, которые бы хорошо работали при достаточно малых значениях; это наводит на мысль, что следует использовать подзадачи, связанные со значениями, а не с весами. Эти подзадачи будут определяться следующим образом: подзадача определяется i и целевым значением V, а — наименьший вес W, при котором можно получить решение с использованием подмножества элементов {1, ..., i} со значением не менее V. Подзадачи будут создаваться для всех i = 0, ..., n и значений Если v* обозначает max_i v_i, то мы видим, что наибольшее V, которое может быть получено в подзадаче, равно Следовательно, в предположении о том, что все значения целочисленны, всего будет не более O(n²v*) подзадач. Ни одна из этих подзадач не совпадает в точности с исходным экземпляром задачи о рюкзаке, но если мы располагаем значениями всех подзадач для то значение исходной задачи можно легко получить: это наибольшее значение V, для которого

Получить рекуррентное отношение для решения этих подзадач нетрудно. По аналогии с алгоритмом динамического программирования для задачи о суммировании подмножеств мы рассматриваем случаи в зависимости от того, включается последний элемент п в оптимальное решение О или нет:

♦ Если n ∉ O, то