МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
___________________________ Санкт- Петербургский государственный электротехнический
университет ( ЛЭТИ )
КАФЕДРА МОЭВМ
Пояснительная записка к курсовой работе
по дисциплине
«Комбинаторные алгоритмы»
Преподаватель
Ивановский С.А..
Выполнили студенты гр. 8308
Муратова А.В.,
Суворов А.А.,
Шафиев А.Р.
Санкт – Петербург
2003
Содержание
Содержание 2
Теоретические материалы 3
Примеры работы алгоритма и иллюстрации 7
Описание программы 14
Функции 14
Структура 14
Структуры данных 14
Структура программы 16
Руководство пользователя 16
Список используемой литературы 25
Приложение 1 26
Приложение 2 28
Теоретические материалы
Во многих прикладных областях, где возникают геометрические задачи, в частности связанные с обработкой данных в реальном времени, и ряд вычислений должен выполняться по мере поступления точек (данных). В общем случае алгоритм, обрабатывающий данные по мере поступления, называется открытым.
Основной чертой открытых алгоритмов является отсутствие ограничений на время коррекции, что равносильно тому, что новый элемент данных (точка) вводится по запросу сразу же после того, как завершается коррекция, связанная с предыдущим элементом данных. Будем называть временной интервал между вводом двух последовательных элементов данных задержкой поступления данных. Более сложный в смысле предъявляемых требований случай применения открытых алгоритмов возникает, когда задержка поступления данных находится вне контроля алгоритма. Иначе говоря, данные поступают не по запросу алгоритма, а подаются на вход алгоритма в некоторые моменты времени, никак не связанные с работой алгоритма.
Будем считать, что поступление данных происходит (распределено) равномерно по времени. В такой ситуации коррекция должна выполняться за время, не превышающее постоянную задержку поступления данных. Алгоритмы, работающие в таком режиме, и называются соответственно алгоритмами реального времени. Следует отметить, что обычно открытые алгоритмы глобально являются менее эффективными по сравнению с соответствующими закрытыми алгоритмами (какая-то плата должна быть внесена за открытость алгоритма).
Далее рассмотрим алгоритм построения выпуклой оболочки в реальном времени
Задача (ВЫПУКЛАЯ ОБОЛОЧКА В РЕАЛЬНОМ ВРЕМЕНИ). На плоскости задана последовательность из N точек pi, .... рN. Требуется найти их выпуклую оболочку при условии, что время задержки поступления точек постоянно.
Рис. 1. Опорные прямые из точки pi к выпуклому многоугольнику Ci-1
При решении задачи, единственное, что необходимо, — это уметь быстро строить две опорные .прямые к выпуклому многоугольнику, проходящие через некоторую точку. В частности, если точки обрабатываются в порядке p1, p2, ... и pi — текущая точка, то обозначим через Сi-1 выпуклую оболочку множества { p1, p2, ..., pi-1 }. Необходимо построить из точки pi опорные прямые к Ci-1, если они существуют (т. е. если точка pi является внешней для Ci-1). Таких прямых не существует тогда и только тогда, когда точка pi является внутренней для Ci-1. В последнем случае точка pi просто удаляется. В первом случае должна быть удалена соответствующая цепочка вершин, заключенная между двумя опорными точками, и вместо них должна быть вставлена точка pi. Эта ситуация показана на рис.1. Для удобства будем называть опорную прямую левой или правой в соответствии с тем, по какую сторону она находится, если смотреть из точки pi на Ci-1.
Рассмотрим построение опорных прямых из некоторой точки р к выпуклому многоугольнику С. Важную роль играет классификация вершин многоугольника С по отношению к отрезку pv, соединяющему вершину v с точкой р. Вершина v называется вогнутой, если
Рис. 2. Классификация вершины и многоугольника С относительно отрезка pv. (Стрелки указывают направление обхода при поиске левой опорной прямой.)
отрезок pv пересекает внутренность многоугольника С. Иначе, если две смежные с v вершины лежат по одну сторону от прямой, проходящей через точки р и v, вершина v называется опорной. В оставшемся случае v называется выпуклой вершиной. Вершина и может быть классифицирована за постоянное время.
Если v — опорная вершина, то на этом решение задачи завершается. Предположим, что ищется левая опорная прямая. Если точка v не является опорной, то необходимо идти по вершинам многоугольника С против или по часовой стрелке в зависимости от того, является ли и вогнутой или выпуклой вершиной (рис. 2). Таким способом можно определить две опорные точки (если они существуют). Если это сделано, необходимо иметь возможность удалить из циклической последовательности вершин многоугольника С цепочку вершин (возможно, пустую) и вставить в образовавшийся разрыв точку р.
Необходимо иметь возможность эффективно выполнять следующие операции:
I. ПОИСК в упорядоченной последовательности элементов (кольцевого списка вершин оболочки) для определения опорных прямых из точки рi,
II. РАСЦЕПЛЕНИЕ последовательности на две последовательности и СЦЕПЛЕНИЕ двух последовательностей;
III. ВСТАВКА одного элемента (текущей точки pi).
Структура данных, в полной мере удовлетворяющая перечисленным требованиям, хорошо известна и называется сцепляемой очередью. Она реализуется с помощью сбалансированного по высоте дерева поиска, и при этом каждая из указанных выше операций может быть выполнена за время O(logi) в худшем случае, где i—число узлов дерева. Естественно, кольцевая последовательность вершин представляется в этой древовидной структуре данных (называемой далее Т) цепочкой, и при этом первый и последний элементы считаются смежными.
В структуре Т будут выделены две вершины: т — самый левый член цепочки и М — корневой член цепочки. Кроме того, мы будем использовать угол (m pi M), который обозначим а. Этот угол называется выпуклым, если он меньше или равен , и вогнутым в противном случае.
В зависимости от классификации вершин m и М (вогнутая, опорная или выпуклая) и угла а возможны всего восемнадцать случаев. Однако все эти случаи можно свести к восьми (покрывающим все возможности), расположенным в таблице 1 и изображенным
Таблица 1
Случай |
a |
m |
M |
1 |
выпуклый |
вогнутая |
вогнутая |
2 |
выпуклый |
вогнутая |
невогнутая |
3 |
выпуклый |
невогнутая |
выпуклая |
4 |
выпуклый |
невогнутая |
невыпуклая |
5 |
вогнутый |
выпуклая |
выпуклая |
6 |
вогнутый |
выпуклая |
невыпуклая |
7 |
вогнутый |
невыпуклая |
вогнутая |
8 |
вогнутый |
невыпуклая |
невогнутая |
на рисунке 3. Диаграммы на рисунке 3. расшифровываются следующим образом: окружность, на которой лежат точки М и m, обозначает многоугольник Р; упорядоченная последовательность вершин начинается в точке m и располагается по окружности в порядке против часовой стрелки; L(M) и R(M) —это последовательности вершин, хранимые в левом и правом поддеревьях корня дерева Т.
Каждый из представленных на рисунке 3 случаев требует различной обработки для определения левой и правой опорных точек, обозначаемых соответственно I и r.
Рассмотрим сначала случаи 2, 4, 6 и 8. Для этих случаев известно, что I и r существуют (так как р не может быть внутренней точкой многоугольника) и их следует искать в различных поддеревьях корня дерева Т (одно из этих поддеревьев расширяется, чтобы включить сам корень). Таким образом, поиск I и r должен проходить одинаково. Например, следующая процедура осуществляет поиск вершины I:
function ЛЕВЫЙ-ПОИСК(T)
Input: дерево Т, описывающее последовательность вершин Output: вершина I
begin с :=КОРЕНЬ(T);
if (pc — опорная прямая) then l := с
else begin if (с—выпуклая вершина) then
Т := ЛДЕРЕВО(с) else Т := ПДЕРЕВО(с)
l:== ЛЕВЫЙ-ПОИСКА)
end;
return ;
end.
Очевидно, что функция ЛЕВЫЙ-ПОИСК проходит по дереву Т некоторый путь, затрачивая в каждом узле ограниченное время на классификацию соответствующей узлу вершины. То же самое имеет место и для функции ПРАВЫЙ-ПОИСК. Теперь рассмотрим случаи 1. 3, 5 и 7. В каждом из этих случаев обе вершины l и r следует искать в одном и том же поддереве корня, если они только существуют (следует отметить, что в случаях 1 и 7 точка р может быть внутренней точкой Р). Таким образом, в каждом случае процедура поиска рекурсивно вызывает себя для поиска в поддереве текущего дерева (выбирается поддерево, соответствующее последовательности, обведенной на рис. 3 штриховой линией) до тех пор, пока не встретится один из случаев
Рис. 3.17. Для удаления точек, оказавшихся внутри выпуклой оболочки, требуется выполнить различные действия в зависимости от относительного положения вершин l и r.
2. 4, 6 или 8. В этом месте инициируется раздельный поиск с помощью функций ЛЕВЫЙ-ПОИСК и ПРАВЫЙ-ПОИСК. Если в процессе поиска будет достигнут лист дерева Т и при этом не имел место ни один из случаев 2, 4, 6 или 8, то точка р является внутренней для многоугольника. Учитывая, что дерево Т сбалансировано и содержит не более i < N вершин, а на обработку в каждом узле требуется ограниченное время, получаем для времени поиска оценку О (log i).
Чтобы завершить описание, рассмотрим процедуру перестройки многоугольника Ci-1 , выполняемую, если точка pi является внешней для него. Вершины между l и r должны быть удалены, a pi должна быть вставлена на их место. В зависимости от того, предшествует вершина I вершине r в дереве Т или нет, требуется выполнить немного различные действия (рис. 3). В первом случае необходимо дважды выполнить операцию расцепления и один раз сцепления; во втором случае только дважды выполняется операция расцепления.
Обе операции РАСЦЕПИТЬ и СЦЕПИТЬ выполняются за время O(log i). В результате, учитывая, что коррекция выпуклой оболочки может быть выполнена за время О(log i), получаем:
Выпуклая оболочка множества из N точек на плоскости может быть найдена с помощью открытого алгоритма за время O(N* log2 N) со временем коррекции O(log2 N), т.е. может быть построена в реальном времени.
Теоретические сведения взяты из [1].