Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Архив1 / docx53 / отчет(17).docx
Скачиваний:
24
Добавлен:
01.08.2013
Размер:
283.87 Кб
Скачать

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»

Факультет вычислительной математики и кибернетики

Кафедра математического обеспечения ЭВМ

Построение выпуклой оболочки n-точек на плоскости

(вариант 592)

Выполнил: студент группы 8309

Лялюшкин Н. А.

Проверил: Замараев В.А.

Нижний Новгород

2012

Оглавление

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

a) Постановка задачи 3

b)Алгоритм построение выпуклой оболочки с помощью сортировки 3

c)Алгоритм сортировки с использованием d-куч. 4

d)Псевдокод операций используемых над d-кучей и некоторые оценки сложности. 4

e)Алгоритм сортировки k-слиянием. 7

f)Алгоритм сортировки вставками. 8

2.Обоснование теоретических оценок временной сложности алгоритмов. 8

Сложность сортировки с помощью d-куч: 9

Сложность сортировки с помощью сортировки k-слиянием: 13

3.Описание программы. 14

4.Проведенные эксперименты. 16

5.Сравнение алгоритмов 19

6.Выводы 20

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

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

Для точек a1, …, an, где n≥1, ai=(ai,1, ai,2)R2 при i=1, …, n, указать вершины b1, …, bm выпуклой оболочки Conv(a1, …, an) в порядке их встречи при движении по ее границе. Заметим, что в общем случае Conv(a1, …, an) будет многоугольником, а в вырожденных случаях может получиться отрезок или точка. В случае отрезка выходом решающего поставленную задачу алгоритма должны быть две являющиеся его концами точки, а в случае точки  сама эта точка.

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

Алгоритмы:

  • алгоритм, использующий сортировку с помощью d-кучи, d=50

  • алгоритм, использующий сортировку (k-50)-слиянием, k=92

    1. Алгоритм построение выпуклой оболочки с помощью сортировки

  1. Поиск лексикографического минимума c = lexmin(a1, … ,an) среди всего массива точек {a1, a2…, an}. Для этого выбирается подмножество точек с минимальной первой координатой, а затем в этом подмножестве выбирается точка с минимальной второй координатой. Полученная точка c будет первым элементом выпуклой оболочки.

  2. Делаем перенос начала системы координат в полученную точку {a1-c, a2-c…, an-c}.

На точках a1, …, an определяется линейный порядок ( ≤ ), что для c1,c2 {a1-c, … ,an–c} имеет место c1 ≤ c2, если

либо det(c1,c2)>0,

либо (det(c1,c2)=0)&( (c1,1)2+(c1,2)2) < (c2,1)2+(c2,2)2 ).

  1. Выполняется сортировка точек по введенному отношению быть не больше(≤).

  2. Производится просмотр отсортированного массива с целью получения итоговых точек b1, …, bm исходя из того условия, что точка bi+1 располагается строго слева от вектора, идущего из точки bi-1 в точку bi, что эквивалентно требованию того, чтобы det(bi-bi-1,bi+1-bi)>0.

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

    1. Алгоритм сортировки с использованиемd-куч.

  1. Из массива точек формируется завершённое d-арное дерево(каждому узлу дерева приписывается элемент массива). Для завершённого d-арного дерева выполняется:

    1. Каждый не листовой узел, кроме, быть может, одного, должен иметь ровно d непосредственных потомков. (Узел исключения может иметь любое число потомков от 0 до d)

    2. Если h – высота дерева, то для {0,1,..n-1} i-ый уровень дерева имеет ровно di узлов, а на последнем уровне может быть любое число узлов от 1 до dn.

  2. Выполняется операция окучивания (применение операции diving(i) по очереди к узлам n-1,…0. Вес каждого узла не превосходит весов элементов, находящихся в его потомках.

  3. Записываем в конец массива Sort элемент, являющийся корнем в d-куче. На место корня ставим элемент с максимальным индексом, размер кучи уменьшаем на 1 и осуществляем погружение корневого элемента кучи.

  4. Повторение описанных операций (в пункте 2.) до тех пор, пока размер кучи не будет равен 1.

  5. В куче останется элемент с максимальным весом, его необходимо записать в конец массива Sort.

Таким образом, получим массив Sort, отсортированный по не убыванию.

Соседние файлы в папке docx53