Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 223
Текст из файла (страница 223)
Избранные темы Предположим, что положение каждого охотника и каждого привидения задано фиксированной точкой на плоскости и что никакие три точки не коллинеарны. а) Докажите, что всегда существует прямая, проходящая через одного охотника и одно привидение, для которой количество охотников, попавших в одну из полуплоскостей относительно этой прямой, равно количеству привидений в этой же полуплоскости.
Опишите, как найти такую прямую за время 0 (и 18 и). б) Разработайте алгоритм, позволяющий в течение времени 0 (пз 18 и) разбить охотников и привидения на пары таким образом, чтобы не было пересечения пучков. 33-4. Сбор палочек Профессор занимается исследованием множества из п палочек, сложенных в кучу в некоторой конфигурации. Положение каждой палочки задается ее конечными точками, а каждая конечная точка представляет собой упорядоченную тройку координат (х,у, з). Вертикальных палочек нет.
Профессор хочет собрать по одной все палочки, соблюдая условие, согласно которому он может снимать палочку только тогда, когда на ней не лежат никакие другие палочки. а) Разработайте процедуру, которая бы для двух заданных палочек а и 6 определяла, находится ли палочка а над палочкой 6, под ней или палочка а не связана ни одним из этих соотношений с палочкой 6. б) Разработайте эффективный алгоритм, позволяющий определить, можно ли собрать все палочки, и в случае положительного ответа предлагающий допустимую последовательность, в которой следует собирать палочки. 33-5. Разреженно-оболочечные распределения Рассмотрим задачу, в которой нужно построить выпуклую оболочку множества заданных на плоскости точек, нанесенных в соответствии с какимто известным случайным распределением.
Для некоторых распределений математическое ожидание размера (количества точек) выпуклой оболочки такого множества, состоящего из и точек, равно 0 (п~ '), где е ) 0— некоторая положительная константа. Назовем такое распределение разреженно-обалочечным (зратзе-Ы!ед). К разреженно-оболочечным распределениям относятся следующие. ° Точки равномерно распределены в круге единичного радиуса. Мате- матическое ожидание размера выпуклой оболочки равно 9 (и'~з). 1083 Глава 33. Вычислительная геометрия ° Точки равномерно распределены внутри выпуклого й-угольника, где Ь вЂ” произвольная константа. Математическое ожидание размера выпуклой оболочки равно О (18 и). ° Точки наносятся в соответствии с двумерным нормальным распределением.
Математическое ожидание размера выпуклой оболочки равно 6 ( Яп)]. а) Даны два выпуклых многоугольника с тт1 и ттз вершинами соответственно. Покажите, как построить выпуклую оболочку всех пт + пз точек в течение времени О (пт + ттз). (Многоугольники могут пересекаться.) б) Покажите, что можно разработать алгоритм, который отыскивает выпуклую оболочку и независимых точек, подчиненных некоторому разреженно-оболочечному распределению, за время О (и). (Указание: рекурсивно постройте выпуклую оболочку для двух половин множества, а затем объедините полученные результаты.) Заключительные замечания В этой главе мы лишь вкратце обсудили тему алгоритмов и методов вычислительной геометрии. Среди серьезных изданий по вычислительной геометрии можно выделить книги Препараты (Ргерата1а) и Шамоса (БЬашоз) [247], а также Эдельсбруннера (Еское!зЬпшпег) [83] и О'Рурка (О'Кош1се) [235].
Несмотря на то, что геометрия изучается с античных времен, развитие алгоритмов для геометрических задач — относительно новое направление. Препарата и Шамос отмечают, что самое раннее упоминание о сложности задачи было сделано Лемоном (Е. 1.епюше) в 1902 году. Изучая евклидовы построения, в которых используется только циркуль и линейка, все действия он свел к набору пяти примитивов: размешение ножки циркуля в заданной точке, размещение ножки циркуля на заданной прямой, построение окружности, совмещение края линейки с заданной точкой и наконец построение прямой. Лемона интересовало количество примитивов, необходимых для построения заданной конструкции; это число он назвал "простотой" данной конструкции.
Описанный в разделе 33.2 алгоритм, в котором определяется, пересекаются ли какие-либо отрезки, предложен Шамосом и Гоем (Ноеу) [275]. Изначальная версия сканирования по Грэхему была представлена Грэхемом (ОгаЬаш) [130]. Алгоритм оборачивания предложен Джарвисом ()агт1з) [165]. Яо (1Гао) [318] с помощью модели дерева решений доказал, что нижняя граница времени работы алгоритма, предназначенного для построения выпуклой оболочки, равна й(п18п). С учетом количества вершин Ь выпуклой оболочки 1084 Часть ЧП. Избранные темы в асимптотическом пределе оптимальным является алгоритм отсечения и поиска, разработанный Киркпатриком (К1гкрапзск) и Зайделем (ЯеЫе1) [180), время работы которого равно О 1п 18 Й).
Алгоритм разбиения со временем работы О (и 18 п), предназначенный для поиска пары ближайших точек, предложен Препаратой и опубликован в книге Препараты и Шамоса 1247]. Препарата и Шамос также показали, что в модели дерева решений этот алгоритм асимптотически оптимален. ГЛАВА 34 ХР-полнота Почти все изученные нами до сих пор алгоритмы имеют лолиномиальное время райчвы (ро1упош1а1-Йпе а1яопбппз): для входных данных размера п их время работы в наихудшем случае равно 0 (и")), где й — некоторая константа. Возникает естественный вопрос: все ли задачи можно решить в течение полиномиального времени? Ответ отрицательный. В качестве примера можно привести знаменитую "задачу осталова"„предложенную Тьюрингом (Типпд).
Эту задачу невозможно решить ни на одном компьютере, каким бы количеством времени мы не располагали. Существуют также задачи, которые можно решить, но не удается сделать это за время 0 (и"), где 1с — некоторая константа. Вообще говоря, о задачах, разрешимых с помощью алгоритмов с полиномиальным временем работы, возникает представление как о легко разрешимых или простых, а о задачах, время работы которых превосходит полиномиальное, — как о трудно разрешимых или сложных.
Однако тема этой главы — интересный класс задач, которые называются "ИР- полными". Их статус пока что неизвестен. Для решения ХР-полных задач до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них таких алгоритмов не существует.
Этот так называемый вопрос Р ~ ИР с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем. Особо интригующим аспектом ХР-полных задач является то, что некоторые из них на первый взгляд аналогичны задачам, для решения которых существуют алгоритмы с полиномиальным временем работы.
В каждой из описанных ниже пар задач одна из них разрешима в течение полиномиального времени, а другая 1086 Часть Ч1!. Избранные темы является ХР-полной. При этом различие между задачами кажется совершенно незначительным. Поиск самых коротких и самых длинных простых путей. В главе 24 мы убедились, что даже при отрицательных весах ребер кратчайшие пути от отдельно взятого источника в ориентированном графе С = (Ъ; Е) можно найти в течение времени 0 (УЕ). Однако поиск самого длинного пути между двумя вершинами оказывается сложным. Задача по определению того, содержит ли граф простой путь, количество ребер в котором не меньше заданного числа, является ХР-полной. Эйлеров и Гамильтонов циклы.
Эйлеров цикл (Ев!ег юш) связанного ориентированного графа С = (Ъ; Е) — это цикл, в котором переход по кажцому ребру С осуществляется ровно один раз, хотя допускается неоднократное посещение некоторых вершин. В соответствии с результатами задачи 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- СХР-выполнимости в сертификате должно быть указано, какие значения следует присвоить переменным. В течение полиномиального времени легко проверить, удовлетворяет ли такое присваивание булевой формуле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
