Поиск по сайту
Рефераты / Математика /Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ реферат на тему: Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскостинайдена за время, пропорциональное суммарному числу их вершин. Рис. 6: Зависимость время выполнения алгоритмов при равномерном случайном расположении точек (N<=200000). Как видно из диаграмм, все алгоритмы в среднем при равномерном распределении точек показали почти линейное время. Различается время примерно в одинаковое число раз, что связано с реализацией данных алгоритмов. Так же видно, при данном распределении быстрее всех работает быстрый алгоритм построения выпуклой оболочки. Это объясняется тем, что в этом случае при каждом шаге он отбрасывает примерно одинаковую часть точек. Поэтому на каждом i-том уровне рекурсии происходит обработка Nki точек, где k часть вершин, которая остается. Это k будет меньше единицы, и не будет сильно изменяться на более глубоких вызовах рекурсивной процедуры. Отсюда получаем то, что время будет стремиться к линейному. Такого не должно наблюдаться при тестах, в которых почти все данные точки будут являться вершинами выпуклой оболочки. Рис. 7: Зависимость время выполнения при расположении точек на окружности. Как видно в данном случае алгоритм Грэхема оказался самым эффективным. Быстрый метод в этом случае не выбрасывает на каждом шаге точек, но так как делит их примерно на равные части, то получается, что он работает примерно время O(N log N), что вполне приемлемо. Что касается динамического построения, то в процессе добавления точек в дерево попадают все вершины, а так как при работе с AWL деревом в моей реализации используются сложные операции с указателями то и процедура получилась медленной. Рис. 8: Нежелательный случай расположения точек для быстрого алгоритма. Из алгоритма быстрого построения следует, что в некоторых случая на каком-то шаге может оказаться, что не была удалена ни одна вершина, и все точки оказались по одну сторону от bh и eh (рис. 8). Если такое случается очень редко, то это не отразится на времени выполнения значительно, а если такое происходит на каждом шаге, то это приводит к оценке O(N2). Для моей реализации этого алгоритма можно взять график ex и точку, расположенную на оси ординат над точкой O. Рис. 9: Время работы быстрой оболочки O(N2). Выводы Как видно из результатов тестов, быстрый метод с данной задачей справляется неудовлетворительно. Теперь можно подвести итоги. В большинстве случаев самыми быстрыми являются алгоритмы Грэхема и быстрый алгоритм. С учетом того, что они просты для реализации, они вполне приемлемы для многих задач. Но быстрый метод имеет существенный недостаток. Если нас интересует поведение алгоритма в худшем случае, он неприемлем. Алгоритм типа “разделяй и властвуй” не показал очень быстрых результатов и не является очень простым в реализации, но он в худшем случае все равно имеет оптимальную оценку. Так же он может быть очень эффективно распараллелен. Динамический способ стоит реализовывать только в случае, если требуется открытый алгоритм, так как он не является очень быстрым и его реализация связана с различными трудностями. Заключение В этой работе были показаны основные алгоритмы построения выпуклых оболочек на плоскости. Так же были проведены сравнения на конкретных реализациях алгоритмов и тестах. Все задачи, поставленные перед этой работой, на мой взгляд, решены. Приложение Unit1.pas unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls, Spin; скачать реферат 1 2 3 4 5 6 ... последняя Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ Внимание! Студенческий отдых и мегатусовка после сессии!
Рефераты и/или содержимое рефератов предназначено исключительно для ознакомления, без целей коммерческого использования. Все права в отношении рефератов и/или содержимого рефератов принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием рефератов и/или содержимого рефератов.
|
Обратная связь. |