Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 240
Текст из файла (страница 240)
В такой схеме любого уменьшения величины е на постоянный множитель можно добиться за счет увеличения времени работы на соответствующий постоянный множитель. Краткое содержание главы В первых четырех разделах этой главы приведены некоторые примеры приближенных алгоритмов с полиномиальным временем работы, позволяющие получать приближенные решения ХР-полных задач. В пятом разделе представлена схема аппроксимации с полностью полиномиальным временем работы.
Начало раздела 35.1 посвяшено исследованию задачи о вершинном покрытии, которая относится к классу ХР-полных задач минимизации. Для этой задачи существует приближенный алгоритм, характеризующийся коэффициентом аппроксимации 2. В разделе 35.2 представлен приближенный алгоритм с коэффициентом аппроксимации 2, предназначенный для решения частного случая задачи коммивояжера, когда функция стоимости удовлетворяет неравенству треугольника. Также показано, что если неравенство треугольника не соблюдается, то для любой константы р > 1 р-приближенного алгоритма не существует, если не выполняется условие Р = ЫР. В разделе 35.3 показано, как использовать жадный метод в качестве эффективного приближенного алгоритма для решения задачи о покрытии множества.
При этом возвращается покрытие, стоимость которого в наихудшем случае превышает оптимальную на множитель, выражающийся логарифмической функцией. В разделе 35.4 представлены еще два приближенного алгоритма. В первом из них исследуется оптимизирующая версия задачи о 3-СИР выполнимости 1154 Часть ЧП.
Избранные темы и приводится простой рандомизированный алгоритм, который выдает решение, характеризующееся математическим ожиданием коэффициента аппроксимации, равным 8/7. Затем изучается взвешенный вариант задачи о вершинном покрытии и описывается, как с помощью методов линейного программирования разработать 2-приближенный алгоритм. Наконец, в разделе 35.5 представлена схема аппроксимации с полностью полиномиальным временем выполнения, предназначенная для решения задачи о сумме подмножеств.
35.1 Задача о вершинном покрытии Задача о вершинном покрытии определена в разделе 34.5.2. В этом же разделе доказано, что эта задача является ХР-полной. Вершинное покрытие (чеггех сочег) неориентированного графа С = (У, Е) — это такое подмножество Г С )г, что если (и, с) — ребро графа С, то либо и Е У', либо ч Е Г (могут выполняться и оба эти соотношения). Размером вершинного покрытия называется количество содержащихся в нем вершин.
Задача о вершинном покрытии (чеггех-сочег ргоЫегп) состоит в том, чтобы найти для заданного неориентированного графа вершинное покрытие минимального размера. Назовем такое вершинное покрытие оптимальным вершинным покрытием (орйпа1 чеггех сочег). Эта задача представляет собой оптимизирующую версию ХР-полной задачи принятия решений. Несмотря на то, что найти оптимальное вершинное покрытие графа С может оказаться трудно, не так сложно найти вершинное покрытие, близкое к оптимальному.
Приведенный ниже приближенный алгоритм принимает в качестве входных данных параметры неориентированного графа С и возвращает вершинное покрытие, размер которого превышает размер оптимального вершинного покрытия не более чем в два раза. АРРкОх Чектех СОчек(С) 1 С+-9 2 Е' — Е~С~ 3 зчЫ1е Е' ф 6 4 бо Пусть (и, ч) — произвольное ребро из множества Е' 5 С ~ — С11(и, ч) 6 Удаляем из множества Е' все ребра, инцидентные вершинам ц или ч 7 гегцгп С Рассмотрим работу алгоритма АРРкох Чектех Сочек.
Как уже было сказано, вершинное покрытие, которое конструируется, содержится в переменной С. В строке 1 переменная С инициализируется пустым множеством. В строке 2 Глава 35. Приближенные алгоритмы 1155 (6,'и~.виям---- -~а' ф ('„~~: 7) Рис. 35.1. Работа алгоритма Аи'кох Чвктпх Сочла создается множество Е', представляющее собой копию множества ребер графа Е 1С]. Цикл в строках З-б выбирает из множества Е' ребро (и, ч), добавляет его конечные точки и и ч в множество С и удаляет из множества Е' все ребра, которые покрываются вершиной и или вершиной о. Если для представления множества Е' используются списки смежных вершин, время выполнения этого алгоритма равно 0(У+ Е).
Работа алгоритма Авккох Чнктнх Сочли проиллюстрирована на рис. 35.1. В части а рисунка изображен граф С, содержащий 7 вершин и 8 ребер. В части б ребро (Ь, с), выделенное серым цветом, — первое по счету ребро, выбранное алгоритмом Аи'кох Чнктнх Сочин. Вершины 6 и с, показанные светло-серой штриховкой, добавляются в множество С, в котором содержится создаваемое вершинное покрытие. Показанные пунктиром ребра (а, 6), (с, е) и (с, д) удаляются, поскольку они уже покрыты вершинами из множества С. В части в рисунка выбрано ребро (е, г"), а вершины е и г" добавляются в множество С.
В части г выбрано ребро (И,д), а вершины д и д добавляются в множество С. В части д показано множество С, которое представляет собой вершинное покрытие, полученное в результате выполнения алгоритма Аггкох Чнктнх Сочнк. Как видно из рисунка, оно состоит из шести вершин: Ь, с, с1, е, г", д. В части е рисунка показано оптимальное вершинное покрытие для рассмотренного экземпляра задачи. Оно состоит всего из трех вершин: Ь, д и е. Часть Ч11. Избранные темы 1156 Теорема 35.1.
Алгоритм АРекох Чектех Сочек является 2-приближенным ал- горитмом с полиномиальным временем работы. Доказаюиельсигво. Мы уже показали, что время работы алгоритма Аеекох Чектех Сочек выражается полиномиальной функцией. Множество вершин С, которое возвращается алгоритмом Ае кох Чектех Сочек, является вершинным покрытием, поскольку алгоритм не выходит из цикла, пока каждое ребро Е [С] не будет покрыто некоторой вершиной из множества С. Чтобы показать, что рассматриваемый алгоритм возвращает вершинное покрытие, размер которого превышает размер оптимального вершинного покрытия не более чем в два раза, обозначим через А множество ребер, выбранных в строке 4 алгоритма Аеекох Чектех Сочек.
Чтобы покрыть ребра множества А, каждое вершинное покрытие, в том числе и оптимальное покрытие С', должно содержать хотя бы одну конечную точку каждого ребра из множества А. Никакие два ребра из этого множества не имеют общих конечных точек, поскольку после того, как ребро выбирается в строке 4, все другие ребра с такими же конечными точками удаляются из множества Е' в строке 6. Таким образом, никакие два ребра из множества А не покрываются одной и той же вершиной из множества С', из чего следует, что нижняя граница размера оптимального вершинного покрытия равна 1С'~ > 1А). (35.2) При кажцом выполнении строки 4 выбирается ребро, ни одна из конечных точек которого пока еще не вошла в множество С.
Это позволяет оценить сверху (фактически указать точную верхнюю границу) размера возвращаемого вершинного покрытия: 1С) = 21А). (35. 3) Сопоставляя уравнения (35.2) и (35.3), получаем 1С( = 21А! < 21С'), что и доказывает теорему. Еще раз вернемся к приведенному выше доказательству. На первый взгляд может показаться удивительным, как можно доказать, что размер вершинного покрытия, возвращенного процедурой Аеккох Чектех Сочек, не более чем в два раза превышает размер оптимального вершинного покрытия, если не известно, чему равен размер оптимального вершинного покрытия. Это становится возможным благодаря использованию нижней границы оптимального вершинного покрытия.
Как предлагается показать в упражнении 35.1-2, множество А, состоящее из ребер, выбранных в строке 4 процедуры Аеекох Чектех Сочек, фактически является Глава 35. Приближенные алгоритмы 1157 максимальным паросочетанием вершин в графе С. (Максимальное иаросочетание (шахппа1 ша1сЫпд) — это паросочетание, которое не является собственным подмножеством какого-нибудь другого паросочетания.) Как было показано при доказательстве теоремы 35.1, размер максимального паросочетания равен нижней границе размера оптимального вершинного покрытия. Алгоритм возвращает вершинное покрытие, размер которого не более чем в два раза превышает размер максимального паросочетания множества А. Составив отношение размера возвращаемого решения к полученной нижней границе, находим коэффициент аппроксимации. Эта методика будет использоваться и в следующих разделах.
Упражнения 35.1-1. Приведите пример графа, для которого процедура АРгкох Чнктех Сочли всегда возвращает неоптимальное решение. 35.1-2. Обозначим через А множество ребер, выбранных в строке 4 процедуры Авркох Чектпх Сочли. Докажите, что множество А — максимальное паросочетание в графе С. * 35.1-3. Профессор предложил такую эвристическую схему решения задачи о вершинном покрытии. Одна за другой выбираются вершины с максимальной степенью, и для каждой из них удаляются все инцидентные ребра.
Приведите пример, демонстрирующий, что коэффициент аппроксимации, предложенной профессором, превышает 2. (Указание: попытайтесь построить двудольный граф, вершины в левой части которого имеют одинаковые степени, а вершины в правой части — разные степени.) 35.1-4. Сформулируйте эффективный жадный алгоритм, позволяющий найти оптимальное вершинное покрытие дерева в течение линейного времени. 35.1-5. Из доказательства теоремы 34.12 известно, что задача о вершинном покрытии и ХР-полная задача о клике являются взаимодополняющими в том смысле, что оптимальное вершинное покрытие — это дополнение к клику максимального размера в дополняющем графе.
Следует лн из этого, что для задачи о клике существует приближенный алгоритм с полиномиальным временем решения, обладающий постоянным коэффициентом аппроксимации? Обоснуйте ваш ответ. 35.2 Задача о коммивояжере Обратимся к задаче о коммивояжере, представленной в разделе 34.5.4. В этой задаче задается полный неориентированный граф С = (У, Е), каждому из ребер (и,п) е Е которого сопоставляется неотрицательная целочисленная стоимость с(и,с), и необходимо найти гамильтонов цикл (тур) минимальной стоимости Часть Чй.
Избранные темы 1158 графа С. Введем дополнительное обозначение с(А) — полную стоимость всех ребер подмножества А С Е; с(А) = ~~~ с(и, с). 1о,о) сА Во многих практических ситуациях наиболее дешевый переход из места и в место ю — всегда по прямой, так что если по пути зайти в какой-нибудь промежуточный путь о, это не может привести к уменьшению стоимости.
Выражаясь другими словами, если срезать путь, пропустив какой-нибудь промежуточный пункт, — это никогда не станет причиной увеличения стоимости. Формализуем это понятие, выдвинув утверждение, что функция стоимости с удовлетворяет неравенству треугольника (птап81е шеоиа111у), если для всех вершин и, о, ю е ъ' с(и,ю) < с(и,с)+с(с,ю). Неравенство треугольника имеет естественный характер и автоматически удовлетворяется во многих приложениях. Например, если вершины графа — точки на плоскости, и стоимость перехода от одной вершины к другой выражается обычным евклидовым расстоянием между ними, то неравенство треугольника выполняется.
(Кроме евклидового расстояния существует множество других функций стоимости, удовлетворяющих неравенству треугольника.) Как видно из упражнения 35.2-2, задача о коммивояжере является МР-полной даже в том случае, если потребовать, чтобы функция стоимости удовлетворяла неравенству треугольника. Таким образом, мало надежд найти алгоритм с полиномиальным временем работы, позволяющий получить точное решение этой задачи. Поэтому есть смысл заняться поиском хороших приближенных алгоритмов. В разделе 35.2.1 исследуется 2-приближенный алгоритм, позволяющий решить задачу о коммивояжере, в которой выполняется неравенство треугольника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
