Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 265
Текст из файла (страница 265)
Процедура возвращает значение з, величина которого отличается от оптимально- го решения не более чем в 1+ е раз. ИД4 Часть УИ. Избранные тены АРРкох-Яйвзет-Бом (,з', 4, 4) ! п=ф! г Т,,=(О) 3 Гогз=1топ 4 Ьз = Минов-115тз(Ь4 „Ьз 4+х,) 5 Ь; = Тд1м(Ь„4/2п) 6 Удалить из Ь; все элементы, которые больше 4 7 Пусть ль — наибольшее значение в Ь„ 8 гетцгп яь Я = (104,102,201,101) с 1 = 308 и 4 = 0.40. Параметр сокрашения б равен 4/8 = 0.06. Процедура АРРкох-8ивзвт-Зим в указанных строках вычисляет следующие значения: Строка 2: Ьо = (0), Строка 4: Ь4 = (0,104), Строка 5: Ь| = (0,104), Строка 6: 4,| = (0,104), (О, 102, 104, 206), (О, 102, 206), (О, 102, 206), ез = е'з = та= Строка 4: Строка 5: Строка 6: (О, 102, 201, 206, 303, 407), (О, 102, 201, 303, 407), (О, 102, 201, 303), Строка 4: Строка 5: Строка 6: ьз = тз = (0,101,102,201,203,302,303,404), (О, 101, 201, 302, 404), (0,101,201,302) .
е'4 Е4 = е'4 Строка 4: Строка 5: Строка 6: Алгоритм возвращает значение г" = 302, которое приближает оптимальное ре- шение 307 = 104+ 102+ 101 в пределах позрешности 4 = 40%; фактически погрешность составляет 2% В строке 2 список Ьо инициализируется таким образом, чтобы в нем содержался только элемент О. Цикл 7ог в строках 3-6 вычисляет отсортированный список 44, содержащий соответствуюшим образом сокрашенную версию множества Рс, из которого удалены все элементы, превышающие величину 4. Поскольку список 1,4 создается на основе списка Т„ и необходимо гарантировать, что повторное сокращение не внесет слишком большой неточности.
Скоро станет понятно, что процедура АРРКОХ-80Вздт-БОМ возвращает корректное приближение, если таковое существует. В качестве примера предположим, что имеется экземпляр задачи Глава 55. Приближенные алеаритиы ПВ5 Теорема 35.8 Процедура Аггнох-Кпвзвт-875м является схемой аппроксимации с полностью полнномиальным временем выполнения, позволяющей решить задачу о сумме подмножеств. <2<У, (1 + е/2п)' (35.26) Неравенство (35.26) должно выполняться для у* е Р„, поэтому существует элемент г Е Ь„, такой, что < 2<У (1+ е/2п)" и, таким образом, 2 ( 2п) (35.27) Поскольку существует элемент 2 Е Ь„, удовлетворяющий неравенству (35.27), это неравенство должно быть справедливым для элемента 2", который имеет самое большое значение в списке Ь„, т.е.
(35.28) Теперь покажем, что у*/г* < 1 + е. Для этого покажем, что (1 + е/2п)" < 1 + е. Согласно уравнению (3.14) имеем 1цп„,,(1+ 2/2п)" = е'72 В упр. 35.5.3 предлагается показать, что (35.29) Следовательно, функция (1+ е/2п)" с ростом п увеличивается и стремится к сво- ему пределу е'1~, н мы имеем (1+ — ) < е'7 < 1+ 2/2+ (е/2) < 1+2 (согласно (3.13)) (согласно (35.25)) . (35.30) м эек 3726 Доказаяеельса7ео. В результате сокращения списка Ь2 в строке 5 и удаления из этого списка всех элементов, превышающих значение 2, поддерживается свойство, что каждый элемент списка Т 2 также является элементом списка Р,.
Поэтому значение 2', которое возвращается в строке 8, на самом деле является суммой некоторого подмножества множества Я. Обозначим оптимальное решение задачи о сумме подмножества у' Е Р„. Тогда из строки 6 известно, что 2' < у'. Согласно неравенству (35.1) нужно показать, что у"/2' < 1 + е.
Необходимо также показать, что время работы этого алгоритма выражается полиномиальной функцией и от 1/е, и от размера входных данных. В упр. 35.5.2 предлагается для каждого элемента у нз Р,, который не превышает 1, показать, что сУШествУет элемент 2 Е Ьо такой, что Часть И1. Избраиные темы ИВ6 Объединение неравенств (35.28) и (35.30) завершает анализ коэффициента аппроксимации.
Чтобы показать, что процедура АРРкох-Бппзет-Бпм представляет собой схему аппроксимации с полностью полиномиальным временем выполнения„оценим границу длины списка 1„. После сокращения последовательные элементы з и з' в списке йн должны удовлетворять соотношению г'/з > 1+ «/2п. Другими словами, они должны отличаться не менее чем в 1+ «/2п раз.
Поэтому каждый список содеРжит значение О, возможно, значение 1 и до ~1о8, «,Сз„С~ дополнительных значений. Количество элементов в кюкдом списке Ь, не превышает 1пС 1о81+аСзп С + 2 = 1 (1 /2 ) + 2 ( +2 2п(1+ «/2п) 1п С Зп!пС ( +2 « (согласно (3.17)) (согласно (35.25)) . Упражнении 35.5.1 Докажите уравнение (35.23). Затем покажите, что после выполнения строки 5 процедуры ЕХАСт-БОВЗЕт-БОМ список Ь, является отсортированным и содер- жит все элементы списка Ро значения которых не превышают С. 35.5.2 Докажите неравенство (35.26) по индукции по С. 35.5З Докажите неравенство (35.29). 35.5.4 Как следовало бы модифицировать представленную в этом разделе схему аппрок- симации, чтобы она позволяла найти хорошее приближение наименьшего значе- ния суммы элементов некоторого подмножества заданного входного списка, не меньшего заданной величины С? 35.5.5 Измените процедуру Аргкох-Бивзнт-Бом таким образом, чтобы она возвраща- ла также подмножество Я, дающее сумму г .
Эта граница является полиномиальной функцией от размера входных данных, который равен сумме количества битов 18 С, необходимых для представления числа С, и количества битов, необходимых для представления множества Я, которое, в свою очередь, полиномиально зависит от и и от 1/«. Поскольку время выполнения процедуры АГРК0Х-БОВЗЕт-БОМ выражается полиномиальной функцией от длины списка Ь„эта процедура является схемой аппроксимации с полностью полиномиапьным временем выполнения.
Глооз 35. Прналнжелнме алгоритмы ПВ7 Задачи 35.1. Расфасоека по контейнеран Предположим, что имеется множество, состоящее из и предметов, причем размер з-го предмета а; удовлетворяет неравенству О < л; < 1. Нужно упаковать все предметы в контейнеры единичного размера, использовав при этом минимальное количество контейнеров. Каждый контейнер вмещает произвольное количество объектов, лишь бы их суммарный размер не превышал 1з. а. Докажите, что задача по определению минимального количества необходимых контейнеров является ХР-полной.
(Указаниег приведите к ней задачу о сумме подмножества.) При эвристическом методе еыбора переого подходпийего (1)гй1-й1) по очереди выбираются все предметы, и каждый помещается в первый же контейнер, в который этот предмет может поместиться. Пусть Я = 2,", но б. Докажите, что оптимальное количество контейнеров, необходимых для упаковки всех предметов, не меньше (51.
е. Докажите, что при использовании эвристического метода выбора первого подходящего все контейнеры, кроме, возможно, одного, буаут заполнены не менее, чем наполовину. * Докажите, что количество контейнеров, которые используются в эвристическом методе выбора первого подходящего, никогда не превышает величи- д. Докажите, что коэффициент аппроксимации эвристического метода выбора первого подходяшего равен 2.
е. Представьте эффективную реализацию эвристического метода выбора первого подходящего и проанализируйте время работы полученного алгоритма. 35.2. Приближение райнера максимальной клики Пусть С = (У, Е) является неориентированным графом. Определим для любого числа гс > 1 граф С(") как неориентированный граф (У("), Е(ь)), где У(ь)— множество всех упорядоченных гс-кортежей вершин из множества У, а Е(") определяется таким образом, что (ом пз,..., оь ) смежны с (нгы нгз,..., щ,) тогда и только тогда, когда для з = 1, 2,..., )с каждая вершина тгй является смежной в графе С вершине нгг (либо когда гд = нг;). ваше не так девиа с втой задачей нв практике приходилось сталкиввтьсл множесгву давьзователей компьютеров, когарме старались рвзместать юж макло балыке файлов на как можно меньшем иночестве дискст...— Примеч. лер.
ИгВ Часть 111 Избранные ыеыы а. Докажите, что размер максимальной клики в графе С~~) равен )г-й степени размера максимальной клики в графе С. б. Докажите, что если существует приближенный алгоритм, позволяющий найти клику максимального размера и обладающий постоянным коэффициентом аппроксимации, то для решения данной задачи существует схема аппроксимации с полиномиальным временем работы. 35.3. Взвешенная задача о покрытии множества Предположим, что задача о покрытии множества обобщается таким образом, что каждому множеству Я; из семейства с сопоставляется вес ьо„а вес покрытия С вычисляется как ~з сьо,.
Требуется найти покрытие с минимальным весом. (В разделе 35.3 рассматривается случай, когда ш; = 1 для всех г.) Покажите, как естественным образом обобщить жадный эвристический подход, который применяется в задаче о покрытии множества, так, чтобы он позволял получить приближенное решение любого экземпляра взвешенной задачи о покрытии множества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
