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