Алгоритмы - построение и анализ (1021735), страница 239
Текст из файла (страница 239)
В этом определении подразумевается, что для таких задач, как задача о клике, о вершинном покрытии, задача о коммивояжере, в которой выполняется неравенство треугольника, и многих других получение хорошего приближенного решения является ХР- сложным, поэтому оно не легче, чем получение оптимальных решений. Введение в эту область можно найти в диссертации Ароры (Агота) [19], в главе Ароры и Лунда (1ллб) в [149], в обзорной статье Ароры [20], в книге под редакцией Мэйра (Мауг), Промеля (Ргоше!) и Стиджера (51еяег) [214], а также в обзорной статье Джонсона [! 67].
ГЛАВА 35 Приближенные алгоритмы Многие задачи, представляющие практический интерес, являются ХР-полными. Однако они слишком важны, чтобы отказаться от их решения лишь на том основании, что получить их оптимальное решение трудно. Если задача ХР-полная, мало шансов найти алгоритм с полиномиальиым временем работы, позволяющий найти ее точное решение. Несмотря на это надежда на точное решение остается.
Во-первых, если объем входных данных небольшой, алгоритм, время работы которого выражается показательной функцией, вполне может подойти. Во-вторых, иногда удается выделить важные частные случаи, разрешимые в течение полиномиального времени. В-третьих, остается возможность найти в течение полиномиального времени решение, близкое к оптимальнаму (в наихудшем либо в среднем случае).
На практике такие решения часто являются достаточно хорошими. Алгоритм, возвращающий решения, близкие к оптимальным, называется лриближенным алгоритмам (арргох|ша1юп а1допйпп). В этой главе описаны приближенные алгоритмы с полиномиальным временем выполнения, предназначенные для решения неюторых ХР-полных задач. Оценка качества приближенных алгоритмов Предположим, мы занимаемся задачей оптимизации, каждому из возможных решений которой сопоставляется положительная стоимость, и требуется найти решение, близкое к оптимальному.
В зависимости от задачи, оптимальное решение можно определить либо как такое, которому соответствует максимально возможная стоимость, или таюе, которому соответствует минимально возможная стоимость; другими словами, это может быть либо задача максимизации, либо задача минимизации. Часть ЧП.
Избранные темы 1152 Говорят, что алгоритм решения задачи обладает отношением, или коэффициентам аппроксимации (приближения) (арргохппаг1оп гагю) р(п), если для произвольных входных данных размера п стоимость С решения, полученного в результате выполнения этого алгоритма, отличается от стоимости С' оптимального решения не более чем в р(п) раз: г'С С* з шах ~ —, — ) < р1гз). 1,С" С/- 135.1) 'Если коэффициент аппроксимации не зависит от п, мы используем термины "отношение аппроксимации р" и "р-приближенный алгоритм", указывающие на отсутствие зависимости от п. Алгоритм, в котором достигается коэффициент аппроксимации р 1п), будем называть р(п)-приближенггым алгоритмом (р 1гз)-арргохппагюп а!яог11)пп).
Определения коэффициента аппроксимации и р 1гз)-приближенного алгоритма применимы и к задачам минимизации, и к задачам максимизации. Для задач максимизации выполняется неравенство О < С < С', и отношение С'/С равно величине, на которую стоимость оптимального решения больше стоимости приближенного решения. Аналогично, для задач минимизации выполняется неравенство О < С' < С, и отношение С/С' дает значение, во сколько раз стоимость приближенного решения больше стоимости оптимального решения.
Поскольку предполагается, что стоимости всех решений положительные, эти коэффициенты вполне определены. Коэффициент аппроксимации приближенного алгоритма не может быть меньше 1, поскольку из неравенства С/С' < 1 следует неравенство С*/С ) 1. Таким образом, 1-прнближенный алгоритм' выдает оптимальное решение, а приближенный алгоритм с ббльшим отношением аппроксимации может возвратить решение, которое намного хуже оптимального. Для ряда задач разработаны приближенные алгоритмы с полиномиальным временем работы и малыми постоянными отношениями аппроксимации. Есть также задачи, для которых лучшие из известных приближенных алгоритмов с полиномиальным временем работы характеризуются коэффициентами аппроксимации, величина которых возрастает с ростом размера входных данных и. Примером такой задачи является задача о покрытии множества, представленная в разделе 35.3.
Некоторые ХР-полные задачи допускают наличие приближенных алгоритмов с полиномиальным временем работы, коэффициент аппроксимации которых можно уменьшать за счет увеличения времени их работы. Другими словами, в них допускается компромисс между временем вычисления и качеством приближения. В качестве примера можно привести задачу о сумме подмножества, которая исследуется в разделе 35.5. Эта ситуация достаточно важна и заслуживает собственного имени. Схема аппроксимации (арргохппайоп зсЬеше) задачи оптимизации — это приближенный алгоритм, входные данные которого включают в себя не только пара- Глава 35. Приближенные алгоритмы 1153 метры экземпляра задачи, но и такое значение е > О, что для любого фиксированного значения е эта схема является (1+ е)-приближенным алгоритмом. Схему аппроксимации называют схемой аппроксимации с полинамиальныи временем выполнения (ро!упоппа1-Йпе арргохппабоп зс!зеше), если для любого фиксированного значения е > О работа этой схемы завершается в течение времени, выраженного полиномиальной функцией от размера п входных данных.
Время работы схемы аппроксимации с полиномиальным временем вычисления может очень быстро возрастать при уменьшении величины е. Например, это время может вести себя как О (пз~'). В идеале, если величина е уменьшается на постоянный множитель, время, необходимое для достижения нужного приближения, не должно возрастать больше, чем на постоянный множитель. Другими словами, хотелось бы„чтобы время работы схемы выражалось полиномиальной функцией от величин 1/е и и. Говорят, что схема аппроксимации является схемой аппроксимации с полностью полиномиальным временем работы (Го!!у ро!упош!а!-!!ше арргохппайоп зс!зеше), если время ее работы выражается полиномом от 1/е и размера входных данных задачи гг.
Например, время работы такой схемы может вести себя как О ((1/е) пз) . В такой схеме любого уменьшения величины е на постоянный множитель можно добиться за счет увеличения времени работы на соответствующий постоянный множитель. Краткое содержание главы В первых четырех разделах этой главы приведены некоторые примеры приближенных алгоритмов с полиномиальным временем работы, позволяющие получать приближенные решения ХР-полных задач. В пятом разделе представлена схема аппроксимации с полностью полиномиальным временем работы. Начало раздела 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 Рис. 35.1. Работа алгоритма Аи'кох Чвктпх Сочла создается множество Е', представляющее собой копию множества ребер графа Е 1С]. Цикл в строках З-б выбирает из множества Е' ребро (и, ч), добавляет его конечные точки и и ч в множество С и удаляет из множества Е' все ребра, которые покрываются вершиной и или вершиной о.
Если для представления множества Е' используются списки смежных вершин, время выполнения этого алгоритма равно 0(У+ Е). Работа алгоритма Авккох Чнктнх Сочли проиллюстрирована на рис. 35.1. В части а рисунка изображен граф С, содержащий 7 вершин и 8 ребер. В части б ребро (Ь, с), выделенное серым цветом, — первое по счету ребро, выбранное алгоритмом Аи'кох Чнктнх Сочин. Вершины 6 и с, показанные светло-серой штриховкой, добавляются в множество С, в котором содержится создаваемое вершинное покрытие. Показанные пунктиром ребра (а, 6), (с, е) и (с, д) удаляются, поскольку они уже покрыты вершинами из множества С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
