Главная » Просмотр файлов » Алгоритмы - построение и анализ

Алгоритмы - построение и анализ (1021735), страница 223

Файл №1021735 Алгоритмы - построение и анализ (Алгоритмы - построение и анализ) 223 страницаАлгоритмы - построение и анализ (1021735) страница 2232017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 (УЕ). Однако поиск самого длинного пути между двумя вершинами оказывается сложным.

Характеристики

Тип файла
DJVU-файл
Размер
18,3 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6521
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее