Скачиваний:
25
Добавлен:
01.05.2014
Размер:
53.83 Кб
Скачать

Санкт-Петербургский

Государственный Электротехнический университет

Кафедра МОЭВМ

Отчет к работе

по дисциплине "Комбинаторные алгортмы"

“Аппроксимация выпукой оболочки”

Факультет: КТИ

Группа: 7341

Выполнили: Матвеева Т.В.

Шеповалов Д.А.

Преподаватель: Ивановский С. А.

г. Санкт-Петербург

2002г.

  1. Постановка задачи.

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

  1. Общие сведения.

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

  1. Теоретические данные.

    1. Описание алгоритма.

В данной работе рассматривается один из таких алгоритмов, а именно алгоритм Бентли, Фауста и Препарата (1982). Основная идея этого алгоритма проста и состоит в том, чтобы выделить из множества точек некоторое подмножество, выпуклая оболочка которого и будет служить аппроксимацией выпуклой оболочки исходного множества точек.

На первом шаге алгоритма ищется минимальное и максимальное значение x-координаты точек множества, а затем вертикальная полоса между ними разбивается на k полос равной ширины.

Эти k полос образуют последовательность так называемых ящиков, по которым будут распределены N точек исходного множества S. После этого в каждой из полос ищутся две точки, имеющие минимальное и максимальное значения y-координаты.

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

Таким образом, результирующее множество, обозначаемое S*, содержит самое большое 2k+4 точек. Наконец, строится выпуклая оболочка множества S*, которая служит аппроксимацией оболочки исходного множества.

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

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

Точная выпуклая оболочка (красная линия) и охватывающая оболочка (зеленая линия):

    1. Оценка алгоритма.

Объем необходимой памяти пропорционален k (в предположении, что исходные точки уже представлены в памяти). Для нахождения минимального и максимального значений x-координаты требуется время (N). Поиск экстремумов во всех полосах требует времени (N), а выпуклая оболочка множества S* может быть построена за время O(k) ( так как множество S* содержит не более 2K+4 точек, причем эти точки уже упорядочены по значению x-координаты). Следовательно, полное время работы алгоритма равно (N+k).

Простота и эффективность описанного алгоритма имели бы небольшую ценность, если бы получаемый результат был слишком неточным. Стоит оценить точность такого подхода. Прежде всего, так как для построения выпуклой оболочки алгоритм использует лишь точки исходного множества, то полученная аппроксимация является внутренней в том смысле, что любая точка, попавшая внутрь приближенной оболочки, будет также и внутренней точкой действительной выпуклой оболочки. Тут же может возникнуть следующий вопрос – насколько далеко от приближенной выпуклой оболочки может оказаться точка из S, находящаяся вне ее? Ответ на этот вопрос достаточно прост – на расстоянии (x- x)/ k.

4. Описание пользовательского интерфейса программы

При запуске программы пользователю предоставляется возможность сформировать исходное множество точек, для которых необходимо построить аппроксимирующую оболочку. Существует две возможности для формирования данного множества:

а.) выбрать пункт меню Исходные данные – Генерация. В появившемся окне Генерация точек в поле ввода ввести количество точек множества. Нажать кнопку Ок. Далее выбрать распределение. В данной программе представлено два вида распределения:

  • нормальное (дополнительно указываются мат. ожидание и отклонение);

  • равномерное;

b.) загрузить готовое множество из файла. Для этого необходимо выбрать пункт меню Исходные данные – Открыть и в появившемся диалоге выбора файла выбрать файл данных. Данный файл имеет расширение *.dat и содержит количество точек и координаты точек.

Далее необходимо количество полос. Для этого существует шкала в левой части формы. Значение по умолчанию – 18.

Работу алгоритма можно увидеть в двух режимах: конечный результат алгоритма, либо пошаговое его выполнение. Для этого на форме имеются кнопки Запуск и Следующий шаг.

В результате пользователь может увидеть на экране построенную аппроксимирующую оболочку, для удобства выделенную одним цветом, а также реальную выпуклую оболочку, выделенную другим цветом (при нажатии CH).

Любое состояние поля с отображением работы алгоритма можно сохранить в файл *.bmp. Для этого необходимо выбрать пункт меню Screen Shots – Создать bmp файл. В появившемся диалоге указать имя файла и сохранить его.

При пошаговой работе для лучшего понимания пользователю предоставляется возможность увидеть работу алгоритма, выделяя определенные шаги цветом, как то выделение максимальной и минимальной точки множества, выделение максимальной и минимальной точки в каждой полосе, и построение аппроксимирующей оболочки. Если у пользователя имеется желание заново посмотреть на работу алгоритма, то он путем нажатия кнопки Заново он имеет возможность вернуться к исходному виду множества точек и проделать алгоритм заново. Возможно также с помощью пункта меню Исходные данные – Новый начать ввод данных заново.

Имеется возможность увидеть два вида оболочки – аппроксимирующую и действительную охватывающую оболочки. Для этого необходимо выбрать либо Convex Hull (аппроксимирующая выпуклая оболочка), либо Super Hull (охватывающая выпуклая оболочка), которые находятся в пункте меню Алгоритмы.