Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 243
Текст из файла (страница 243)
Препарата и Шамос отмечают, что самое раннее упоминание о сложности задачи было сделано Э. Лемоном (Е. Ьегпоше) в 1902 году. Изучая евклидовы построения, Глава ЗЗ. Вычислительяая геометрия 1095 в которых используются только циркуль н линейка, он свел все действия к набору пяти примитивов: размещение ножки циркуля в заданной точке, размещение ножки циркуля на заданной прямой, построение окружности, совмещение края линейки с заданной точкой и построение прямой.
Лемана интересовало количество примитивов, необходимых для построения заданной конструкции; это число он назвал "простотой" данной конструкции. Описанный в разделе 33.2 алгоритм, в котором определяется, пересекаются ли какие-либо отрезки, предложен Шамосом (БЬашоа) и Гаем (Ноеу) [311].
Изначальная версия сканирования по Грэхему была представлена Грэхемом (ОгаЬшп) [149]. Алгоритм оборачивания предложен Джарвисом (Заги(а) [188]. Яо (Уао) [357] с помощью модели дерева решений доказал, что нижняя граница времени работы алгоритма, предназначенного для построения произвольной выпуклой оболочки, равна П(п 18 и). С учетом количества вершин Ь выпуклой оболочки в асимптотическом пределе оптимальным является алгоритм отсечения и поиска, разработанный Киркпатриком (К(гкравтск) и Зайделем (БеЫе1) [205], время работы которого равно 0(п 18 6).
Алгоритм "разделяй и властвуй" со временем работы 0(п18п), предназначенный для поиска пары ближайших точек, предложен Препаратой (Ргерагаш) и опубликован в книге Препараты (Ргерзхвш) и Шамоса (8Ьапюз) [280]. Они также показали, что в модели дерева решений этот алгоритм асимптотически оптимален. Глава 34. ХР-полнота Почти все изученные нами ранее алгоритмы являются алгоритмами с полииомиальиым временем рабопзы (ро(упош1а1-пше а!йопбппз): для входных данных размером и их время работы в наихудшем случае равно 0(п"), где л — некоторая константа.
Возникает естественный вопрос: все ли задачи можно решить в течение полиномиального времени? Ответ отрицательный. В качестве примера можно привести знаменитую задачу останова, предложенную Тьюрингом (Тпппя). Ее невозможно решить ни на одном компьютере, каким бы количеством времени мы ни располагали. Существуют также задачи, которые можно решить, но не удается сделать это за время 0(п"), где lс — некоторая константа. Вообще говоря, о задачах, разрешимых с помощью алгоритмов с полиномиальным временем работы, возникает представление как о легко разрешимых нли простых, а о задачах, время работы которых превосходит полнномиальное, — как о трудно разрешимых илн сложных. Однако темой этой главы является интересный класс задач, которые называются ХР-полными, статус которых пока что неизвестен.
Для решения ХР-полных задач до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-либо нз них такого алгоритма не существует. Этот так называемый вопрос Р ~ ХР с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем. Особо интригующим аспектом ХР-полных задач является то, что некоторые из них, на первый взгляд, аналогичны задачам, для решения которых существуют алгоритмы с полиномиальным временем работы. В каждой нз описанных ниже пар задач одна из них разрешима в течение полиномиального времени, а другая является МР-полной.
При этом различие между задачами кажется совершенно незначительным. Поиск самых коротких н самых длинных простых путей. В главе 24 мы видели, что даже при отрицательных весах ребер крамчайшие пути от отдельно взятого источника в ориентированном графе 0 = (Ъ; Е) можно найти за время 0((г Е). Однако поиск самого длинного пути между двумя вершинами оказывается сложным.
Задача определения того, содержит лн граф простой путь, количество ребер в котором не меньше заданного числа, является ХР-полной. Эйлеров и гамильтонов циклы. Эйлеров Пипл (Еп!ег Юш) связанного ориентированного графа 0 = ()г, Е) представляет собой цикл, в котором проход по !097 Глава ЗК ФР-аалната каждому ребру С осуществляется ровно один раз, хотя допускается неоднократное посещение некоторых вершин. В соответствии с результатами задачи 22.3 определить наличие эйлерова цикла (а также найти составляющие его ребра) можно за время О(Е). Гамильтонов цикл (!запи1!оп!ап сус!е) ориентированного графа С = ($', Е) представляет собой простой цикл, содержащий все вершины из множества Г.
Задача определения, содержится ли в ориентированном графе гамильтонов цикл, является 1ЧР-полной. (Далее в этой главе будет доказано, что задача определения наличия гамильтонова цикла в неориектировакном графе также является ХР-полной.) 2-СР(Р- и 3-СР!Р-выполнимость. Булеза формула содержит переменные, принимающие значения О и 1, булевы операторы, такие как д (И), ~( (ИЛИ) и — (НЕ), а также скобки.
Булева формула называется еылолиимой (забзбаЫе), если входящим в ее состав переменным можно присвоить такие значения О и 1, что в результате вычисления формулы получится значение 1. Далее в этой главе даются более формализованные определения всех терминов, а пока, говоря неформально, булева формула представлена в й-коиаюикюивной нормальной форме (/с-соп1ппс!!те поппа! !опп), или к-СИР, если она имеет вид конъюнкции (И) взятых в скобки выражений, являющихся дизъюнкцией (ИЛИ) ровно й переменных или их отрицаний (НЕ).
Например, формула (хз ь' хз) д ( хз и хз) д ( хз ь' хз) представлена в 2-СИР. (Для нее существует выполнимый набор х~ = 1, хз = О, хз = 1.) Можно сформулировать алгоритм с полиномиальным временем работы, позволяющий определить, является ли 2-СХР- формула выполнимой. Однако, как будет показано далее в этой главе, определение, является ли 3-СИР-формула выполнимой, является ХР-полной задачей. 1ЧР-полнота и классы Р н ХР В этой главе мы будем ссылаться на три класса задач: Р, ХР и ХРС (класс ХР- полных задач).
В этом разделе они описываются неформально, а их формальное определение будет дано позже. Класс Р состоит из задач, разрешимых в течение полиномиального времени работы. Точнее говоря, это задачи, которые можно решить за время 0(п"), где й — некоторая константа, а п — размер входных данных задачи. Большинство задач, рассмотренных в предыдущих главах, принадлежат классу Р. Класс ХР состоит из задач, которые поддаются проверке в течение полиномиального времени.
Имеется в виду, что если мы каким-то образом получаем "сертификат" решения, то в течение времени, полиномиальным образом зависящего от размера входных данных задачи, можно проверить корректность такого решения. Например, в задаче о гамильтоновом цикле с заданным ориентированным графом С = ($', Е) сертификат имел бы вид последовательности (щ, ез, ез,..., о1~ !) из ~ ь' ! вершин, В течение полиномиального времени легко проверить, что (о„е,.ь~) Е Е для з = 1, 2,3,..., ~Ъ'! — 1 и что (е~~ без) Е Е.
Приведем другой пример; в задаче о 3-СИР-выполнимости в сертификате должно быть указано, какие значения следует присвоить переменным. В течение полиномиального времени легко проверить, удовлетворяет ли такое присваивание буле- 109я Часть ед Иэбаанные тены вой формуле. Любая задача класса Р принадлежит классу ХР, поскольку принадлежность задачи классу Р означает, что ее решение можно получить в течение полиномиального времени, даже не располагая сертификатом. Это замечание будет формализовано ниже в данной главе, а пока что можно считать, что Р С ХР. Остается открытым вопрос, является ли Р строгим подмножеством ХР.
Неформально задача принадлежит классу ХРС (такие задачи называются КР- «олинмя (ХР-сошр!езе)), если она принадлежит классу ХР и является столь же "сложной", как и любая задача из класса ХР. Ниже в этой главе будет дано формальное определение того, что означает выражение "задача такая же по сложности, как любая задача из класса ХР".
А пока что мы примем без доказательства положение, что если любую ХР-полную задачу можно решить в течение полиномиального времени, то для каждой задачи из класса ХР существует алгоритм с полиномиальным временем работы. Большинство ученых, занимающихся теорией вычислительных систем, считают ХР-полные задачи очень трудноразрешимыми, потому что при огромном разнообразии изучавшихся до настоящего времени ХР-полных задач ни для одной из них пока так и не найдено решение в виде алгоритма с полиномиальным временем работы. Таким образом, было бы крайне удивительно, если бы все они оказались разрешимыми в течение полиномиального времени. Чтобы стать квалифицированным разработчиком алгоритмов, необходимо понимать основы теории ХР-полноты. Если установлено, что задача ХР-полная, это служит достаточно надежным указанием на то, что она трудноразрешимая. Как инженер вы эффективнее потратите время, если займетесь разработкой приближенного алгоритма (см.
главу 35) или решением простого частного случая, вместо того чтобы искать быстрый алгоритм, выдающий точное решение задачи. Более того, многие естественно возникающие интересные задачи, которые, на первый взгляд, не сложнее задачи сортировки, поиска в графе или определения потока в сети, фактически являются ХР-полными. Таким образом, важно ознакомиться с этим замечательным классом задач. Как показать, что задача является ХР-полной Методы, позволяющие доказать, что та или иная задача является ХР-полной, отличаются от методов, которые использовались в большей части этой книги для разработки и анализа алгоритмов. Имеется фундаментальная причина такого различия: чтобы показать, что задача является ХР-полной, делается утверждение о том, насколько она сложна (нли по крайней мере, насколько она сложна в нашем представлении), а не о том, насюлью она проста.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
