Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 246
Текст из файла (страница 246)
Поскольку можно показать, что (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 ша~сЫпй) называется паросочетание, юторое не является собственным подмножеством никакого другого паросочетания.
Покажите, что максимальное ларосочетание не обязательно совпадает с паросочетанием максимальной мощности. Для этого приведите пример неориентированного графа С, максимальное паросочетание М в котором не является паросочетанием максимальной мощности. (Имеется граф всего лишь с четырьмя вершинами, обладающий указанным свойством.) б) Рассмотрим неориентированный граф С = (К Е). Сформулируйте жадный алгоритм поиска максимального паросочетания в графе С, время работы которого было бы равно 0 (Е).
В этой задаче внимание сосредотачивается на поиске приближенного алгоритма с полиномиальным временем работы, позволяющего найти паросочетание максимальной мощности. Время работы самого быстрого из известных на сегодняшний день алгоритмов, предназначенных для поиска паросочетания максимальной мощности, превышает линейное (хотя и является полиномиальным); рассматриваемый же здесь приближенный алгоритм завершает свою работу строго в течение линейного времени. Вы должны будете показать, что жадный алгоритм поиска максимального паросочетания с линейным временем выполнения, разработанный в части б, для задачи о паросочетании максимальной мощности является 2-приближенным алгоритмом. Глава 35.
Приближенные алгоритмы 1185 в) Покажите, что размер паросочетания максимальной мощности в графе С представляет собой нижнюю границу размера произвольного вершинного покрытия в этом графе. г) Рассмотрим максимальное паросочетание М в графе С = (1г, Е). Пусть Т = (о е Р': неюторое ребро из М инцидентно о) . Что можно сказать о подграфе графа С, порожденном теми вершинами графа С, которые не принадлежат Т2 д) На основании результатов части г обоснуйте вывод о том, что величина 2 1М~ равна размеру вершинного покрытия графа С. е) Воспользовавшись результатами решения частей в и д задачи, докажите, что сформулированный в части б жадный алгоритм является 2-приближенным алгоритмом для задачи о паросочетании максимальной мощности.
35-5. Расписание работы параллельной вычислительной машины В задаче о расписании работы параллельной вычислительной машины (рога!1е1-шас!ппе-зследп!1п8 ргоЫеш) исходные данные представляют собой набор из и заданий .Уз, .Уз,...,,У„, каждое из которых характеризуется временем обработки ры Для выполнения этих заданий в нашем распоряжении имеется т идентичных машин Мы Мз,..., Мт. Нужно составить расписание, в ютором для каждого задания Уь следует указать машину, на которой это задание будет выполняться, и выделенный ему интервал времени. Каждое задание должно непрерывно выполняться только на одной машине М; в течение времени ры и в это время на машине М; не может выполняться никакое другое задание.
Обозначим через Сь время завершения (сошр!ейоп 11ше) задания,4, т.е. момент времени, когда прекращается обработка задания .Уы Для каждого расписания определяется его момент завершения (ша1сезрап), равный С = шахзс <„С . В задаче нужно найти расписание с минимальным моментом завершения. Например, предположим, что имеется две машины Мз и Мз и что нужно выполнить четыре задания УП,Уз,,Уз,.У4, для юторых рз = 2, рз = 12, рз = 4 и р4 — — 5. Можно предложить расписание, при котором на машине Мг сначала выполняется задание .Уы а затем — задание Уз, а на машине Мз сначала выполняется задание У4, а затем — задание,Уз. В этом расписании Сг = 2, Сз = 14, Сз = 9, С4 = 5 и С =14. В оптимальном расписании на машине Мг выполняется задание,Уз, а на машине Мз— задания.Уы,Уз и У4.
В этом расписании С~ = 2, Сз = 12, Сз = 6, С4 = 11 иС =12. Часть П. Избранные темы 1186 В данной задаче о расписании работы параллельной вычислительной машины обозначим через С„; время завершения оптимального расписания. а) Покажите, что оптимальное время завершения по величине не меньше самого большого времени обработки, т.е.
что выполняется неравенство С' > шах рь. 14/с~п б) Покажите, что оптнмальное время завершения по величине не мень- ше средней загрузки машин, т.е. что справедливо неравенство 1 С" ) — ,'1 р,. 1~ь4в Предположим, что для составления расписания параллельных вычислительных машин нспользуется следующий жадный алгорнтм: как толью машина освобождается, на ней начинает выполняться очередное задание, еще не внесенное в расписание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
