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