Алгоритмы - построение и анализ (1021735), страница 224
Текст из файла (страница 224)
Задача по определению того, содержит ли граф простой путь, количество ребер в котором не меньше заданного числа, является ХР-полной. Эйлеров и Гамильтонов циклы. Эйлеров цикл (Ев!ег юш) связанного ориентированного графа С = (Ъ; Е) — это цикл, в котором переход по кажцому ребру С осуществляется ровно один раз, хотя допускается неоднократное посещение некоторых вершин. В соответствии с результатами задачи 22-3, определить наличие Эйлерова цикла (а также найти составляющие его ребра) можно в течение времени 0 (Е).
Гамильтонов цикл (лаш!11оп(ал сус!е) ориентированного графа С = (У, Е) — это простой цикл, содержащий все вершины из множества У. Задача по определению того, содержится ли в ориентированном графе Гамильтонов цикл, является ХР-полной. (Далее в этой главе будет доказано, что задача по определению того, содержится ли в неориентированном графе Гамильтонов цикл, также является МР-полной.) 2-СЯ- и 3-СИР-выполнимость. Булева формула содержит переменные, принимающие значения О и 1, булевы операторы, такие как Л (И), Ч (ИЛИ) и (НЕ), а также скобки.
Булева формула называется вынолннмой (за!!збаЫе), если входящим в ее состав переменным можно присвоить такие значения О и 1, чтобы в результате вычисления формулы получилось значение 1. Далее в этой главе даются более формализованные определения всех терминов, а пока, говоря неформально, булева формула представлена в й-коньюнктивной нормальной форме (к-сон!вас!1че поппа! 1опп), или /с-СЯ, если она имеет вид конъюнкции (И) взятых в скобки выражений, являющихся дизъюнкцией (ИЛИ) ровно к переменных или их отрицаний (НЕ).
НапримеР, фоРмУла (Я~ Ч - хз) д (- Я~ Ч хз) д (- хз Ч . хз) пРедставлена в 2-СИР. (Для нее существует выполнимый набор х~ = 1, хз = О, хз = 1.) Можно сформулировать алгоритм с полиномиальным временем работы, позволяющий определить, является ли 2-СХР формула выполнимой.
Однако, как будет показано далее в этой главе, определение того, является ли 3-СИР формула выполнимой — это ХР-полная задача. Глава 34. ХР-полнота 1087 1з(Р-полнота и классы Р и 1з(Р В этой главе мы будем ссылаться на три класса задач: Р, ХР и ХРС (класс ХР- полных задач). В этом разделе они описываются неформально, а их формальное определение будет дано позже. Класс Р состоит из задач, разрешимых в течение полиномиального времени работы. Точнее говоря — это задачи, которые можно решить за время О (и"), где к — некоторая константа, а и — размер входных данных задачи.
Большинство задач, рассмотренных в предыдущих главах, принадлежат классу Р. Класс ХР состоит из задач, которые поддаются проверке в течение полиномиального времени. Имеется в виду, что если мы каким-то образом получаем "сертификат" решения, то в течение времени, полиномиальным образом зависящего от размера входных данных задачи, можно проверить корректность такого решения. Например, в задаче о гамильтоновом цикле с заданным ориентированным графом С = (Ъ', Е) сертификат имел бы вил последовательности (щ, оз,..., о1~ ~) из )Ъ'! вершин.
В течение полиномиального времени легко проверить, что (о;, ю;+1) е Е при г = 1, 2,..., (У! — 1 и что (пар пт) Е Е. Приведем другой пример: в задаче о 3- СХР-выполнимости в сертификате должно быть указано, какие значения следует присвоить переменным. В течение полиномиального времени легко проверить, удовлетворяет ли такое присваивание булевой формуле. Любая задача класса Р принадлежит классу ХР, поскольку принадлежность задачи классу Р означает, что ее решение можно получить в течение полиномиального времени, даже не располагая сертификатом. Это замечание будет формализовано ниже в данной главе, а пока что можно считать, что Р С ХР.
Остается открытым вопрос, является ли Р строгим подмножеством ХР. Неформально задача принадлежит классу ХРС (такие задачи называются МР- лолными (ХР-сотр1е1е)), если она принадлежит классу ХР и является такой же "сложной", как и любая задача из класса ХР. Ниже в этой главе будет дано формальное определение того, что означает выражение "задача такая же по сложности, как любая задача из класса ХР". А пока что мы примем без доказательства положение, что если любую ХР-полную задачу можно решить в течение полиномиального времени, то для каждой задачи из класса ХР существует алгоритм с полиномиальным временем работы.
Большинство ученых, занимающихся теорией вычислительных систем, считают ХР-полные задачи очень трудноразрешимыми, потому что при огромном разнообразии изучавшихся до настоящего времени ХР- полных задач ни для одной из них пока так и не найдено решение в виде алгоритма с полиномиальным временем работы. Таким образом, было бы крайне удивительно, если бы все они оказались разрешимыми в течение полиномиального времени. Чтобы стать квалифицированным разработчиком алгоритмов, необходимо понимать основы теории ХР-полноты.
Если установлено, что задача ХР-полная, это Часть ЧП. Избранные темы 1088 служит достаточно надежным указанием на то, что она трудноразрешимая. Как инженер, вы эффективнее потратите время, если займетесь разработкой приближенного алгоритма (см. главу 35) или решением легкого особого случая, вместо того, чтобы искать быстрый алгоритм, выдающий точное решение задачи.
Более того, многие естественно возникающие интересные задачи, которые на первый взгляд не сложнее задачи сортировки, поиска в графе или определения потока в сети, фактически являются ХР-полными. Таким образом, важно ознакомиться с этим замечательным классом задач. Как показать, что задача является 1чР-полпой Методы, позволяющие доказать, что та или иная задача является ХР-полной, отличаются от методов, которые использовались в большей части этой книги лля разработки и анализа алгоритмов.
Имеется фундаментальная причина такого различия: чтобы показать, что задача является ХР-полной, делается утверждение о том, насколько она сложна (или, по крайней мере, насколько она сложна в нашем представлении), а не о том, насколью она проста. Не предпринимается попыток доказать, что существуют эффективные алгоритмы. Скорее, мы пытаемся доказать, что эффективных алгоритмов, вероятнее всего, не существует. В этом смысле доказательство ХР-полноты несколько напоминает представленное в разделе 8.1 доказательство того, что нижняя граница любого алгоритма, работающего по методу сравнений, равна 11 (и 18 и).
Однако методы, использующиеся для доказательства ХР-полноты, отличаются от методов с применением дерева решений, описанных в разделе 8.1. При доказательстве ХР-полноты задачи используются три основные концепции, описанные ниже. Задачи принятия решения и задачи оптимизации Многие представляющие интерес задачи являются задачами оиюиимизаиии (ор11ш1хабоп ргоЫешз), каждому допустимому ("законному") решению которых можно сопоставить неюторое значение и для которых нужно найти допустимое решение с наилучшим значением. Например, в задаче, получившей название Яноктвзт Рлтн, залается неориентированный граф С, а также вершины и и и, и нужно найти путь из вершины и к вершине е, в котором содержится наименьшее юличество ребер.
(Другими словами, Бнокткзт РАтн — это задача поиска кратчайшего пути между парой вершин невзвешенного неориентированного графа.) Однако ХР-полнота непосредственно применима не к задачам оптимизации, а к задачам принятия реизенин (бес1з1оп ргоЫешз), в которых ответ может быть положительным или отрицательным (говоря более формально, принимать значения "Г' или "О"). Глава 34. МР-полнота 1089 Хотя при доказательстве НР-полноты задачи приходится ограничиваться задачами принятия решения, между ними и задачами оптимизации существует удобная взаимосвязь.
Наложив ограничение на оптимизируемое значение, поставленную задачу оптимизации можно свести к соответствуюшей задаче принятия решения. Например, задаче БНОктезт Рлтн соответствует задача принятия решения под названием Рлтн: существует ли для заданных исходных данных, в число которых входит направленный граф С, вершины и и о, и целое число Й, путь из вершины и к вершине о, состоящий не более чем из й ребер. Взаимосвязь между задачей оптимизации и соответствующей ей задачей принятия решения полезна для нас, если мы пытаемся показать, что задача оптимизации является "сложной".
Причина этого заключается в том, что задача принятия решения в некотором смысле "проще" или, по крайней мере, "не сложнее". Например, задачу Рати можно решить, решив задачу Зноктнзт Рлтн, а затем сравнивая количество ребер в найденном крагчайшем пути со значением параметра Й в задаче принятия решения. Другими словами, если задача оптимизации простая, соответствующая ей задача принятия решения тоже простая. Формулируя это утверждение так, чтобы оно имело большее отношение к МР-полноте, можно сказать, что если удается засвидетельствовать сложность задачи принятия решения, это означает, что соответствующая задача оптимизации тоже сложная. Таким образом, хотя и приходится ограничиваться рассмотрением задач принятия решения, теория МР-полноты зачастую имеет следствия и для задач оптимизации.
Приведение Сделанное выше замечание о том, что одна задача не сложнее или не легче другой, применимо, даже если обе задачи являются задачами принятия решения. Эта идея используется почти во всех доказательствах ИР-полноты. Это делается следующим образом. Рассмотрим задачу принятия решения, скажем, задачу А, которую хотелось бы решить в течение полиномиального времени. Назовем входные данные отдельно взятой задачи экземлляром (1пз1апсе) этой задачи.
Например, экземпляром задачи Рлтн является некоторый граф С, некоторые его вершины и и о, а также некоторое целое число к. А теперь предположим, что существует другая задача принятия решения, скажем, В, для которой заранее известно, как решить ее в течение полиномиального времени. Наконец, предположим, что имеется процедура с приведенными ниже характеристиками, преобразующая любой экземпляр а задачи А в некоторый экземпляр ~9 задачи В. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
