Алгоритмы - построение и анализ (1021735), страница 238
Текст из файла (страница 238)
Задача о независимом множестве (спссерепссепс-зес ргоЫепс) заключается в том, чтобы 1146 Часть ЧП. Избранные темы найти в заданном графе С независимое множество максимального раз- мера. а) Сформулируйте задачу принятия решения, соответствующую задаче о независимом множестве, и докажите, что она является ХР-полной. (Указание: приведите к этой задаче задачу о клике.) б) Предположим, что для задачи принятия решения, определенной в части а, имеется подпрограмма в виде "черного ящика", решающая эту задачу. Сформулируйте алгоритм поиска независимого множества, имеющего максимальный размер. Время работы этого алгоритма должно выражаться полиномиальной функцией от величин (Ц н )Е).
При этом предполагается, что каждый запрос подпрограммы учитывается как одна операция. в) Несмотря на то, что задача о независимом множестве является М'- полной, некоторые особые случаи разрешимы в течение полиномиального времени. г) Разработайте эффективный алгоритм, позволяющий решить задачу о независимом множестве, если степень каждой вершины графа С равна 2. Проанализируйте время работы этого алгоритма и докажите его корректность. д) Разработайте эффективный алгоритм, позволяющий решить задачу о независимом множестве, если граф С вЂ” двудольный. Проанализируйте время работы этого алгоритма и докажите его корректность.
(Указание: воспользуйтесь результатами, полученными в разделе 26.3.) 34-2. Бонни и Клайд Бонни и Клайд только что ограбили банк. У них есть мешок денег, который нужно разделить. В каждом из описанных ниже сценариев требуется либо сформулировать алгоритм с полиномиальным временем работы, либо доказать, что задача ХР-полная. В каждом случае в качестве входных данных выступает список, состоящий из и содержащихся в мешке элементов, а также стоимость каждого из них.
а) В мешке и монет двух различных номинаций: одни монеты стоят х долларов, а другие — у долларов. Деньги следует разделить поровну. б) Имеется и монет произвольного количества различных номиналов, но при этом каждый номинал является неотрицательной целой степенью двойки, т.е. возможны такие номиналы: 1 доллар, 2 доллара, 4 доллара и т.д. Деньги следует разделить поровну. Глава 34. ХР-полнота 1147 в) Имеется и чеков, по невероятному совпадению выписанных на имя "Бонни или Клайд".
Нужно разделить чеки таким образом, чтобы по ним можно было получить одинаковые суммы. г) Как и в случае в, имеется и чеков, но на этот раз допускается рас- хождение в суммах, которое не должно превышать 100 долларов. 34-3. Раскраска графов Если задан неориентированный граф С = ()г, Е), то его я-раскрашиваиием ()г-со!ог!пд) называется функция с: Ъ' -> (1,2,...,й), такая что с(и) ~ с(о) для каждого ребра (и, о) е Е. Другими словами, числа 1, 2,..., й представляют к цветов, и смежные вершины должны быть разного цвета. Задача о раскрашивании графов (ягарЬ-со!опля ргоЫет) заключается в том, чтобы определить минимальное количество цветов, необходимых для раскрашивания заданного графа.
а) Сформулируйте эффективный алгоритм 2-раскрашивания графа, если такое раскрашивание возможно. б) Переформулируйте задачу о раскрашивании графов в виде задачи принятия решения. Покажите, что эта задача разрешима в течение полиномиального времени тогда и только тогда, когда задача о раскрашивании графов разрешима в течение полиномиального времени. в) Пусть язык З-Со!.ок представляет собой множество графов, для которых возможно 3-раскрашивание. Покажите, что если задача 3-Соьок — ХР-полная, то задача принятия решения из части б тоже ХР-полная. Чтобы доказать ХР-полноту задачи З-Соьок, воспользуемся приведением к этой задаче задачи 3-СХР БАт.
Для заданной формулы ф, содержащей т выражений в скобках и п переменных хм хз,..., х„конструируется граф С = (Р; Е) описанным ниже способом. Множество У содержит по одной вершине для каждой переменной, по одной вершине для каждого отрицания переменной, по 5 вершин для каждого подвыражения в скобках и 3 специальных вершины: ткон, гАьзв и кю.
Ребра в этом графе могут быть двух типов: "литеральные" ребра, которые не зависят от подвыражений в скобках, и "дизъюнктивные" ребра, которые от них зависят. Литеральные ребра образуют треугольник на специальных вершинах, а также образуют треугольник на вершинах х,, х; и кю для 1 = 1,2,...,и. г) Докажите, что при любом 3-раскрашивании с графа, состоящего из литеральных ребер, из каждой пары вершин х;, . х; одна окрашена Часть ЧП. Избранные темы 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 статей, в заголовке, аннотации или списке ключевых слов которых содержится термин 'ХР-полный'.
Он встречается чаше, чем термины компилятор', 'база данных', 'экспертная система', 'нейронная сеть' или 'операционная система"'. Недавняя работа по теории сложности пролила свет на вопрос о сложности приближенных компьютерных вычислений. В ней приводится новое определение класса ХР с помощью "вероятностно проверяемых доказательств".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
