Алгоритмы - построение и анализ (1021735), страница 245
Текст из файла (страница 245)
Поскольку список Ьз создается на основе списка Ь; ы мы должны гарантировать, что повторное сокращение не вносит слишком большой неточности. Скоро станет понятно, что процедура АРРкОх БОВзет Бим возвращает корректную аппроксимацию, если она существует. Часть Чй. Избранные темы 1180 В качестве примера рассмотрим экземпляр задачи, где Я = (104, 102, 201, 101), Ф = 308 и е = 0.40.
Параметр 6 равен е/8 = 0.05. В процедуре Аггиох Бывает Бим вычисляются приведенные ниже значения (слева от которых указаны номера соответствующих строк): ~о = (О) Строка 2: Ь1 — — (О, 104), Ь| = (О, 104), Ь1 = (0,104), Строка 4: Строка 5: Строка 6: Ьг = (0,102,104,206), Ьг = (О, 102,206), Ьг = (О, 102, 206), Строка 4: Строка 5: Строка 6: Ьз = (О 102,201,206,303,407), Ьз = (0,102 201 303 407) Ьз = (0,102,201,303), Строка 4: Строка 5: Строка 6: Ь4 = (0,101,102,201,203,302,303,404), Ь4 = (0,101,201,302,404) > Ь4 = (О, 101) 201, 302) .
Строка 4: Строка 5: Строка 6: Алгоритм возвращает значение з' = 302, которое приближает оптимальное ре- шение 307 = 104+ 102+ 101 в пределах погрешности е = 40%; фактически погрешность составляет 2М. Теорема 35.8. Процедура Арркох Бивзвт Бом является схемой аппроксимации с полностью полиномиальным временем выполнения, позволяющей решить зада- чу о сумме подмножеств.
Доказательство. В результате сокращения списка Ь; в строке 5 и удаления из этого списка всех элементов, превышающих значение 1, поддерживается свойство, что каждый элемент списка Ь; также является элементом списка Р,. Поэтому значение г', которое возвращается в строке 8, на самом деле является суммой некоторого подмножества множества Я. Обозначим оптимальное решение задачи о сумме подмножества у' е Р„. Далее, из строки 6 известно, что г' < у'. Согласно неравенству (35Л ), нужно показать, что у'/з' < 1+с. Необходимо также показать, что время работы этого алгоритма выражается полиномиальной функцией и от 1/е, и от размера входных данных.
Глава 35. Приближенные алгоритмы 1181 Воспользовавшись индукцией по 1, можно показать, что для каждого не превышающего 1 элемента у из списка Р, существует элемент я Е Ц, такой что у . (з(у (1+ е/2п)' (35.24) (см. упражнение 35.5-2). Неравенство (35.24) должно выполняться для у' е Р„, поэтому существует элемент я Е Ь„, удовлетворяющий неравенству (1 + е/2п) и, следовательно, ( 2п) (35.25) Поскольку существует элемент х Е Ь„, удовлетворяющий неравенству (35.25), это неравенство должно быть справедливым для элемента з', который имеет самое большое значение в списке Ь„, т.е.
(35.26) Осталось показать, что у'/г' < 1+ е. Для этого покажем, что (1+ е/2п)" < < 1+ е. Согласно (3.13), 1пп„(1+ е/2п)" = е'7з. Поскольку можно показать, что (35.27) функция (1+ в/2п)" по мере увеличения п возрастает до своего предела е'7з, и справедлива цепочка неравенств (1+ — ) <е < я (е)з (в соответствии с (3.12)) (с учетом (35.23)). (35.28) ~ (1+е Объединение неравенств (35.26) и (35.28) завершает анализ коэффициента аппроксимации. Чтобы показать, что процедура Арркох Бивзнт Зим — зто схема аппроксимации с полностью полиномиальным временем выполнения, оценим границу длины списка Ц.
После сокращения последовательные элементы з и х' в списке Ц должны удовлетворять соотношению г'/з > 1 + а/2п. Другими словами, они должны отличаться не менее чем в 1+а/2п раз. Поэтому каждый список содержит Часть Ч1!. Избранные темы 1182 значение О, возможно, значение 1 и до ~1об1~,7з„ 1~ дополнительных значений. Количество элементов в каждом списке Ц не превышает 1пт 1ок1+ /з„1+ 2 =... + 2 < 1п(1+ е/2п) 2п (1 + е/2п) 1п ~ 4п1пг < — +2 Я (в соответствии с (3.1б)) (с учетом (35.23)). Упражнения 35.5-!. Докажите уравнение (35.21).
Затем покажите, что после выполнения строки 5 процедуры ЕХЛСт ЗОВЗВт БОМ список Ь; является отсортированным и содержит все элементы списка Р;, значения юторых не превышают 8. 35.5-2. Докажите неравенство (35.24). 35.5-3. Докажите неравенство (35.27). 35.5-4. Как следовало бы модифицировать представленную в этом разделе схему аппроксимации, чтобы она позволяла найти наименьшее значение, превышающее или равное заданной величине 1, суммы элементов некоторого подмножества заданного входного списка? Задачи 35-1.
Расфасовка по контейнерам Предположим, имеется множество, состоящее из п предметов, причем размер тъго предмета з; удовлетворяет неравенству О < а; < 1. Нужно упаковать все предметы в контейнеры единичного размера, использовав при этом минимальное количество контейнеров. Каждый ювтейнер вмещает произвольное количество объектов, лишь бы их суммарный размер не превышал 1. Эта граница выражается полиномиальной функцией от размера входных данных, который равен сумме количества битов 1я 1, необходимых для представления числа 8, и юличества битов, необходимых для представления множества Я, которое, в свою очередь, полиномиально зависит от и и от 1/е. Поскольку время выполнения процедуры АггкОх Яг!взвт Яг!м выражается полиномиальной функцией от длины списка Ь;, эта процедура является схемой аппроксимации с полностью полиномиальным временем выполнения. Глава 35. Приближенные алгоритмы 1183 а) Докажите, что задача по определению минимального количества необходимых контейнеров является г(Р-полной.
(Указание: приведите к ней задачу о сумме подмножества.) При эвристическом методе выбора первого подходящего (йгзьйс) по очереди выбираются все предметы, и каждый помещается в первый же контейнер, в который этот предмет может поместиться. Пусть Я = 2 '," аь б) Докажите, что оптимальное количество контейнеров, необходимых для упаковки всех предметов, не меньше Я. в) Докажите, что при использовании эвристического метода выбора первого подходящего„не более чем один контейнер остается заполненным меньше чем наполовину. г) Докажите, что количество контейнеров, которые используются в эвристическом методе выбора первого подходящего, никогда не превышает величину (251.
д) Докажите, что коэффициент аппроксимации эвристического метода выбора первого подходящего равен 2. е) Представьте эффективную реализацию эвристического метода выбора первого подходящего и проанализируйте время работы полученного алгоритма. 35-2. Приближенный размер максимальной клики Пусть С = (К Е) — неориентированный граф. Определим для произвольного числа к > 1 неориентированный граф С(ь) = (У®, Е(")), где т'(") — множество всех упорядоченных Й-кортежей вершин из множества У, а Е определяется таким образом, что элемент (сы сз,..., сь) (ь) смежен элементу (юы шз,..., ьпь) тогда и только тогда, когда при любом значении 1 < 1 < Й каждая вершина щ является смежной в графе С вершине в; (либо с; = в;). а) Докажите, что размер максимальной клики в графе С® равен к-й степени размера максимальной клики в графе С.
б) Докажите, что если существует приближенный алгоритм, позволяющий найти клику максимального размера и обладающий постоянным коэффициентом аппроксимации, то для решения данной задачи существует схема аппроксимации с полностью полиномиальным временем работы. 35-3. Взвешенная задача о покрытии множества Предположим, задача о покрытии множества обобщается таким образом, что каждому множеству Я; из семейства У' сопоставляется вес шо а вес 1184 Часть ЧП. Избранные темы покРытиЯ С вычислЯетсЯ как 2 з, с ц;. НУжно найти покРытие с минимальным весом. (В разделе 35.3 рассматривается случай, югда и~, = 1 для всех 1.) Покажите, что жадный эвристический подход, который применяется в задаче о покрытии множества, можно естественным образом обобщить так, чтобы он позволял получить приближенное решение любого экземпляра взвешенной задачи о покрытии множества.
Покажите, что коэффициент аппроксимации этого эвристического подхода равен Н (с(), где и' — максимальный размер произвольного множества Яь 35-4. Паросочетание максимальной мощности Напомним, что в неориентированном графе С паросочетанием называется такое множество ребер, в котором никакие два ребра не инццлентны одной и той же вершине. Из раздела 26.3 мы узнали, как найти максимальное паросочетание в двудольном графе. В настоящей задаче будет производиться поиск паросочетаний в неориентированных графах общего вида (т.е. в графах, которые не обязательно являются двудольными). а) Максимальным паросочетаиием (шахппа1 ша~сЫпй) называется паросочетание, юторое не является собственным подмножеством никакого другого паросочетания. Покажите, что максимальное ларосочетание не обязательно совпадает с паросочетанием максимальной мощности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
