Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 239
Текст из файла (страница 239)
Избранные темы 1148 дкй'> Рис. 34.18. Структурный элемент, который соответствует подвыражению (х Н у Ч з), используюшийся в задаче 34-3 как с (Ткпк), а другая — как с(Рази). Покажите, что для любого набора значений функции ф существует 3-раскрашивание графа, содержащего только литеральные ребра.
Дизъюнктивные ребра нужны для того, чтобы наложить на 3-раскрашивание условия, соответствующие истинности дизъюнкций, составляющих формулу ф. Структурный элемент, показанный на рис. 34.18, соответствует подвыражению (х Ч у Ч з). Структурный элемент, соответствующий каждому подвыражению, состоит из трех вершин для входящих в него литералов, пяти вспомогательных вершин (на рисунке они выделены темным цветом), соединенных с входящими в выражение литералами, и с особой вершиной ткин, как показано на рисунке.
д) Докажите, что если каждая из вершин х, у и з окрашена в один из двух цветов — с(Ткал) или с(ри.зн), — то для изображенного на рисунке структурного элемента правильное 3-раскрашивание возможно тогда и только тогда, когда цвет хотя бы одной из вершин х, у и з — с(Ткик). е) Завершите доказательство ХР-полноты задачи З-Соьок. 34-4. Расписание с прибылью и сроками выполнения Предположим, что имеется одна вычислительная машина и п заданий аы аз,..., а„. Каждое задание а характеризуется временем выполнения сз, прибылью р и конечным сроком выполнения ф В каждый момент времени машина может обрабатывать только одно задание, причем задание а после запуска должно без прерываний выполняться в течение времени 1.
Если задание а будет выполнено до наступления конечного срока его выполнения И, то будет получена прибыль ру, но если конечный срок выполнения будет упущен, то и прибыли не будет. Сформулируем такую задачу оптимизации: пусть для множества и заданий Глава 34. (чР-полнота 1149 известны время обработки, прибыль и время выполнения; требуется составить расписание таким образом, чтобы были выполнены все задания и общая сумма прибыли была максимальной. а) Сформулируйте эту задачу в виде задачи принятия решения. б) Покажите, что эта задача принятия решения ЫР-полная.
в) Сформулируйте алгоритм с полиномиальным временем работы, позволяющий решить задачу принятия решения в предположении, что все времена выполнения выражаются целыми числами от 1 до и. (Указание: воспользуйтесь методами динамического программирования.) г) Сформулируйте алгоритм с полиномиальным временем работы, позволяюший решить задачу оптимизации в предположении, что все времена выполнения выражаются целыми числами от 1 до п. Заключительные замечания Книга Гарея (Оагеу) и Джонсона ()оЬпзоп) [1101 является замечательным учебником по вопросам Ь!Р-полноты; в ней подробно обсуждается эта теория и описываются многие задачи, ЫР-полнота которых была доказана до 1979 года. Из этой книги позаимствовано доказательство теоремы 34.13, а список ЫР-полных задач, описанных в разделе 34.5, взят из содержания этой книги.
В период 1981-1992 гг. Джонсон написал серию из 23 статей в .Уоигла! оГА1~ог11Ьия, рассказывая о новых достижениях в исследованиях ЫР-полноты. В книгах Хапкрофта (Норсгой), Мотвани (Монкаш) и Ульмана (1Л!шап) [1531, Льюиса (Ьеиз) и Пападимитриу (Рарайш!1г!ои) [2041, Пападимитриу [2361 и Сипсера (81рзег) [279! проблема ЫР- полноты удачно трактуется в контексте теории сложности. В книге Ахо (АЬо), Хопкрофта и Ульмана [51 также описывается ЫР-полнота и приводятся примеры приведений, в том числе приведение задачи о гамильтоновом цикле к задаче о вершинном покрытии. Класс Р был введен в 1964 году Кобхемом (СоЬЬаш) [641 и независимо в 1965 году Эдмондсом (Ес!шолй) [841, который ввел также класс ЫР и выдвинул гипотезу, что Р ф Ь)Р.
Понятие ЫР-полноты впервые было предложено Куком (Соо1с) [67! в 1971 году. Кук представил первое доказательство ЫР-полноты задач о выполнимости формул и 3-СЫР выполнимости. Левин (Еенп) [203) независимо пришел к этому понятию; он доказал ЫР-полноту задачи о мозаике. Карп (Кагр) [1731 в ! 972 году предложил методику приведения и продемонстрировал богатое разнообразие ЫР-полных задач. В статье Крапа впервые доказывается ЫР-полнота задач о клике, о вершинном покрытии и о гамильтоновом цикле. С тех пор многими исследователями была доказана Ь!Р-полнота сотен задач. В 1995 году 1150 Часть Ч!!.
Избранные темы на заседании, посвященном 60-летию Карпа, Пападимитриу в своем докладе заметил: "... каждый год выходит около 6000 статей, в заголовке, аннотации или списке ключевых слов которых содержится термин 'ХР-полный'. Он встречается чаше, чем термины компилятор', 'база данных', 'экспертная система', 'нейронная сеть' или 'операционная система"'. Недавняя работа по теории сложности пролила свет на вопрос о сложности приближенных компьютерных вычислений.
В ней приводится новое определение класса ХР с помощью "вероятностно проверяемых доказательств". В этом определении подразумевается, что для таких задач, как задача о клике, о вершинном покрытии, задача о коммивояжере, в которой выполняется неравенство треугольника, и многих других получение хорошего приближенного решения является ХР- сложным, поэтому оно не легче, чем получение оптимальных решений. Введение в эту область можно найти в диссертации Ароры (Агота) [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/е) п~) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
