Тема данной курсовой работы

Скачать 257.85 Kb.

Название	Тема данной курсовой работы
страница	4/5
Дата публикации	30.04.2015
Размер	257.85 Kb.
Тип	Документы

100-bal.ru > Право > Документы

1 2 3 4 5

Динамические алгоритмы построения выпуклой оболочки

Все приведенные алгоритмы не являются открытыми, так как требуют изначально знать все точки множества S. Но в некоторых случаях требуется иметь алгоритм способный при поступлении новой точки изменять выпуклую оболочку. В данном случае мы имеем дело с задачей ВО2.

Очевидно, что решение задачи существует. Можно каждый раз после поступления точки использовать обход Грэхема и получить алгоритм со сложностью O(N² log N), но хотелось бы не приносить в жертву оценку O(N log N).

Для этого следует обратить внимание на то, что каждую новую точку алгоритм должен или отбрасывать, или вставлять его в список точек образующих выпуклую оболочку. Чтобы получить это оценку, мы на каждую точку должны тратить время O(log N), то есть мы должна находить место вставки и вставлять точку за O(log N). Такой алгоритм построил Препарата^⁸.

В этом алгоритме необходимо быстро находить опорные прямые к выпуклому многоугольнику P и проходящие через некоторую точку p. После этого одну из цепей, на которые разбивают опорные точки границу выпуклого многоугольника, заменить на p.

Будем называть опорную прямую pl левой, если многоугольник P лежит справа от pl, и соответственно прямую pr правой, если слева. Точки l и r будем называть опорными. Так же будем различать вогнутые вершины, т.е. те для которых отрезок, соединяющий их и p, пересекает внутренность многоугольника. А те, которые ни вогнутые и ни опорные будут выпуклыми.

При поверке какой-то вершины на вогнутость или выгнутость мы можем определить, где искать опорную точку. Тык же мы должны иметь возможность быстро удалить цепочку вершин и вставить место нее p. Для этого нам нужно хранить многоугольник не писком, как это делалось в предыдущих алгоритмах, а AWL или другим сбалансированным деревом.

В этом дереве T переход к левому потомку будет соответствовать движению по часовой стрелке по выпуклой оболочке, а для правого против часовой стрелки. Для каждого узла в этом дереве мы должны иметь возможность получать доступ к самой левому узлу. Если рассмотреть корневой узел дерева M и m – самый левый узел, то они разбивают границу выпуклого многоугольника на две цепи, причем одна хранится в левом поддереве M, а вторая в правом. В зависимости от типа вершины М и m, а также от того, какой угол (mpM) – левый или правый, можно определить в каком поддереве находится опорная вершина.

Рассмотрим поиск левой опорной вершины. Если (mpM) – левый а m – вогнутая или то (mpM) – правый а M – выпуклая, то поиск нежно продолжать в левом поддереве, иначе – в правом. Аналогично и для правой опорной вершины.

Рис. 4: Два варианта для m, M и p.
Таким способом мы находим за время O(log i) левую и правую опорные прямые. После этого за время O(log i) мы можем удалить все выпуклые вершины и сбалансируем дерево. Отсюда следует теорема:
Теорема 7. Выпуклая оболочка множества из N точек на плоскости может быть найдена с помощью открытого алгоритма за время (N log N) и со временем коррекции (log N).

Сравнительный анализ алгоритмов построения выпуклой оболочки

Так как теоретически показали, что время работы всех алгоритмов в среднем O(log N), то следует ожидать при тестировании почти всегда результаты отличающиеся на константу.

Проведем исследования зависимости времени работы алгоритмов от размеров задачи при равномерном распределении точек:

Рис. 5: Зависимость время выполнения алгоритмов при равномерном случайном расположении точек (N<=100).

Рис. 6: Зависимость время выполнения алгоритмов при равномерном случайном расположении точек (N<=200000).
Как видно из диаграмм, все алгоритмы в среднем при равномерном распределении точек показали почти линейное время. Различается время примерно в одинаковое число раз, что связано с реализацией данных алгоритмов. Так же видно, при данном распределении быстрее всех работает быстрый алгоритм построения выпуклой оболочки. Это объясняется тем, что в этом случае при каждом шаге он отбрасывает примерно одинаковую часть точек. Поэтому на каждом i-том уровне рекурсии происходит обработка Nkⁱ точек, где k часть вершин, которая остается. Это k будет меньше единицы, и не будет сильно изменяться на более глубоких вызовах рекурсивной процедуры. Отсюда получаем то, что время будет стремиться к линейному.

Такого не должно наблюдаться при тестах, в которых почти все данные точки будут являться вершинами выпуклой оболочки.

Рис. 7: Зависимость время выполнения при расположении точек на окружности.
Как видно в данном случае алгоритм Грэхема оказался самым эффективным. Быстрый метод в этом случае не выбрасывает на каждом шаге точек, но так как делит их примерно на равные части, то получается, что он работает примерно время O(N log N), что вполне приемлемо. Что касается динамического построения, то в процессе добавления точек в дерево попадают все вершины, а так как при работе с AWL деревом в моей реализации используются сложные операции с указателями то и процедура получилась медленной.

Рис. 8: Нежелательный случай расположения точек для быстрого алгоритма.

Из алгоритма быстрого построения следует, что в некоторых случая на каком-то шаге может оказаться, что не была удалена ни одна вершина, и все точки оказались по одну сторону от bh и eh (рис. 8). Если такое случается очень редко, то это не отразится на времени выполнения значительно, а если такое происходит на каждом шаге, то это приводит к оценке O(N²). Для моей реализации этого алгоритма можно взять график e^x и точку, расположенную на оси ординат над точкой O.

Рис. 9: Время работы быстрой оболочки O(N²).

1 2 3 4 5

Похожие:

	Рекомендации по написанию курсовой работы При подготовке курсовой... Затем студент приступает к сбору информации. Первоначальное представление о теме и структуре работы можно составить по учебникам,...		Рекомендации студенту по выполнению рефератА (курсовой работы) Процесс... Выбор темы является весьма ответственным этапом выполнения реферата (курсовой работы), тема выбирается студентами самостоятельно...
	Отчетной работы) Курсовой проект (вид работы) По дисциплине «Теория антикризисного управления» Титульный лист курсовой работы (проекта), контрольной работы, домашнего задания, реферата, отчета о практике		Методические указания к выполнению курсовой работы по дисциплине... Рассматриваются вопросы, связанные с условиями и порядком выполнения курсовой работы. Даны общие требования к курсовой работе, выбору...
	Методические указания по выполнению курсовой работы 1 Содержание и структура работы Задание на выполнение курсовой работы по дисциплине «стратегический менеджмент», тематика курсвых работ		Выдержки из курсовой работы ...
	Методические указания по самостоятельной подготовке к практическим... Представлены методические указания по дисциплине «Маркетинг» к выполнению курсовой работы, проведению практических занятий, библиографический...		Каково целевое назначение курсовой работы как вида учебного процесса? В какой последовательности следует осуществлять подготовку дипломной (курсовой) работы?
	Методические указания к выполнению курсовой работы по дисциплине... Основными задачами, решаемыми студентами при выполнении курсовой работы являются		1. Экономическая сущность амортизации ос Темой данной курсовой работы является учет амортизации и методы ее начисления в условиях рынка
	Методические рекомендации по написанию курсовой работы по дисциплине... Цель курсовой работы состоит в том, чтобы развить у студентов навыки самостоятельной творческой работы, углубленно изучить какую-либо...		Методические указания к выполнению курсовой работы по дисциплине... Целью курсовой работы является закрепление теоретических знаний и выработка у студентов практических навыков по калькулированию себестоимости...
	Курсовая работа По курсу “Теория управления” Тема курсовой работы:... Тема курсовой работы: «Анализ и синтез оптимальной одноконтурной сау при использовании непрерывного и цифрового регуляторов»		Указания по оформлению курсовой работы по «Технологии профессиональной деятельности» Курсовая работа оформляется в виде электронного файла и пересылается преподавателю на электронную почту не позднее чем за 2 дня до...
	Рекомендации по выполнению курсовой работы Цель и значение курсовой... При разработке учебно – методического комплекса учебной дисциплины в основу положены		Методические указания по выполнению курсовой работы для студентов... Целью курсовой работы является систематизация, углубление и закрепление теоретических знаний по дисциплине, развитие навыков самостоятельной...

Школьные материалы