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

Скачать 257.85 Kb.

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

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

1 2 3 4 5

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

Для начала рассмотрим несколько малопродуктивных алгоритмов построения выпуклой оболочки.
Определение 3. Точка p выпуклого множества S называется крайней, если не существует пары точек a, b  S таких, что p лежит на открытом отрезке ab.
Очевидно, что подмножество крайних точек E является наименьшим подмножеством S, выпуклая оболочка которого, является выпуклой оболочкой множества S, или conv(E)=conv(S). Поэтому нам необходимо для нахождения выпуклой оболочки выполнить два шага:

Определить крайние точки.

Упорядочить эти точки так, чтобы они образовали выпуклый многоугольник.
Теорема 3. Точка p не является крайней точкой множества S только тогда когда она лежит в некотором треугольнике, вершинами которого принадлежат S, но сама она не является вершиной этого треугольника.
Эта теорема дает возможность построить алгоритм проверки крайности точки. Если мы имеем дело с множеством S мощности N, то можно построить O(N³) треугольников. Проверка принадлежности точки треугольнику выполняется за постоянное количество операций. Следовательно, за время O(N³) можно определить, является ли точка крайней, а за O(N⁴) и для всех точек.

Следующая теорема показывает, – в каком порядке должны быть точки в конечном множестве.
Теорема 4. Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла относительно любой внутренней точки.
Упорядочить крайние точки множества можно относительно их центроида. Центроид множества для N точек вычисляется за время O(N) арифметических операций. Грэхем предложил использовать для этого только три любые неколлинеарные точки множества S. В худшем случае это требует время O(N), но почти всегда это первые три точки.

Упорядочить их можно за время O(N log N). Таким образом, мы решаем задачу ВО1 за время O(N⁴).

Метод обхода Грэхема

Приведенный выше алгоритм является неэффективным, поэтому необходим способ более быстрого построения выпуклой оболочки. Для этого нам необходим другой подход.

Грэхэм в одной из первых своих работ сумел показать, как можно, предварительно отсортировав точки относительно полярного угла с центром в какой-нибудь внутренней точке, можно найти крайние точки за линейное время^⁵.

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

Отсортированные точки следует поместить в двусвязный список. Так как внутренние точки принадлежат некоторому треугольнику (Opq), где p и q – соседние вершины точке выпуклой оболочки. Суть алгоритма в последовательном просмотре отсортированного списка и удалении внутренних вершин. Оставшиеся точки будут являться вершинами выпуклой оболочки.

Просмотр начнем с точки являющейся вершиной ВО. Для этого можно взять точку с минимальной абсциссой, а если их несколько, то и минимальной ординатой и пометить как начальную. После чего, обходим список, начиная с нее, против часовой стрелки и проверяем внутренний угол для текущей точки. Если он больше либо равен , то удаляем вершину, а иначе переходим к следующей. Так как за каждый просмотр мы или удаляем одну вершину, или переходим к следующей, а просмотр заканчиваем при достижении вершины начало, которая не удалится, то мы выполняем не более N шагов. Рассмотренный метод называют методом обхода Грэхема.
Теорема 5. Выпуклая оболочка N точек на плоскости может быть найдена за время O(N log N) при памяти O(N) с использованием только арифметических операций и сравнений.
Доказательство. Из предыдущего алгоритма видно, что в нем используются только арифметические операции и сравнения. Для нахождения внутренней точки и обхода требуется линейное время, а на сортировку уходит O(N log N). Для представления списка нам достаточно O(N) памяти.
Так как выше было доказано, что нижняя оценка для алгоритма решающего эту задачу равна O(N log N), то получаем, что обход Грэхема имеет оптимальное время выполнения. Но он является оптимальным в худшем случае, а поведение его в среднем мы не изучили. Этот алгоритм имеет несколько недостатков.

В нем используются тригонометрические функции, а так как их вычисление связано с большими затратами по времени, то желательно от них избавиться. Эндрю предложил метод решения этой проблемы^⁶.

Если на плоскости заданы N точек, то существует самая левая и самая правая точки, и они являются вершинами выпуклой оболочки. Прямая, проходящая через эти точки делит множество на две части. Это точки, которые лежат выше и точки, которые ниже прямой. Оба множества порождают соответствующие им части выпуклой оболочки, причем они являются монотонными ломаными относительно оси x. Поэтому, отдельно отсортировав эти множества по значению абсциссы, производится обход Грэхема.

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

1 2 3 4 5

Похожие:

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

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