close

Вход

Забыли?

вход по аккаунту

?

Об определении диаметра конечного множества точек в евклидовом пространстве.

код для вставкиСкачать
Автоматика, телемеханика и связь на железных дорогах
127
УДК 513.8
ОБ ОПРЕДЕЛЕНИИ ДИАМЕТРА КОНЕЧНОГО МНОЖЕСТВА
ТОЧЕК В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ
Е.Ю. Морозова
Аннотация
В работе предложен эффективный алгоритм определения диаметра конечного
множества точек в евклидовом пространстве. При этом рассматривается задача
нахождения глобального максимума выпуклой функции на выпуклом многогранном
множестве. В основе подхода лежит комбинированный метод, позволяющий
традиционными методами находить точки локального минимума и метод
статистических испытаний, позволяющий улучшать найденные точки.
Ключевые слова: диаметр множества; выпуклая оболочка множества;
задача выпуклого программирования; метод статистических испытаний
Введение
Задача определения диаметра конечного множества точек возникает
во многих областях: астрономии, микробиологии, популяционной генетике
и др. В случае больших значений числа точек множества непосредственное
вычисление диаметра требует значительных затрат машинного времени.
Настоящая статья посвящена описанию алгоритма определения диаметра
множества точек, который при больших является значительно более
эффективным.
1. Постановка задачи
В предлагаемом алгоритме задача определения диаметра конечного
множества точек в евклидовом пространстве сводится к задаче нахождения
глобального максимума выпуклой функции на выпуклом многогранном
множестве.
Рассматривается задача выпуклого программирования вида:
( x, y ) max,
( x, y ) conv(V ) conv(V ),
(1)
где ( x, y ) - евклидово расстояние между точками x и y , V - множество
вершин выпуклого многогранника.
Известия Петербургского университета путей сообщения
2004/1
Автоматика, телемеханика и связь на железных дорогах
128
2. Основные замечания
Пусть X {x1, x 2 ,..., x n } - конечное множество точек в евклидовом
пространстве R d .
Диаметром
DX
множества
называется
X
d
max{ ( xi , x j ) i, j 1,..., n}, где
( xi , x j )
( xki
число
xkj ) 2 - евклидово
k 1
расстояние между точками x и x .
Предварительно заметим, что
DX Dconv ( X ) , где conv ( X ) - выпуклая оболочка множества X ,
геометрически представляющая собой выпуклый многогранник с
множеством
вершин
Поэтому
Extr (conv( X )) {v1,..., v N } V .
DX max{ (vi , v j ) i, j 1,..., N } . Однако число N также может оказаться
большим, в этом случае эффективным оказывается алгоритм, приводимый
в этой статье.
В настоящее время известны различные алгоритмы построения
выпуклой оболочки множества, в частности, в пакете MATLAB имеется
встроенная функция CONVHULLN, входным аргументом которой
является матрица, образованная столбцами координат элементов
множества X , а выходным аргументом является матрица, образованная
столбцами координат элементов множества V . Незначительная
модификация стандартного алгоритма позволяет параллельно с
zij
построением множества V строить также матрицу Z
, где
i
j
i , j 1,..., N
1, если вершины v , v смежны (соединены
ребром) в многограннике conv(V )
i
zij
j
иначе
0,
Таким образом, в дальнейшем будем считать, что имеется эффективная
программа, выдающая по множеству X множество V и матрицу Z .
3. Описание алгоритма
Нетрудно видеть, что диаметр DX множества X является значением
задачи (1), для решения которой может быть использован метод
нахождения глобального минимума квазивогнутой функции на выпуклом
многогранном множестве (Баушев А.Н., Морозова Е.Ю. и др., 2003). Для
задачи нахождения глобального максимума выпуклой функции на
выпуклом многогранном множестве основная теорема может быть
переформулирована следующим образом.
Теорема 1. Квазивыпуклая функция F : C R , заданная на
замкнутом ограниченном выпуклом множестве C R n ,
достигает
2004/1
Известия Петербургского университета путей сообщения
Автоматика, телемеханика и связь на железных дорогах
129
наибольшего значения, по крайней мере, в одной из крайних точек
множества C .
Доказательство. Функция называется квазивыпуклой, если для
каждого вещественного числа c множество {x : F ( x) c} выпукло.
1
k
Если x
- выпуклая комбинация точек {x1,..., x k } , то
...
1x
kx
для квазивыпуклой функции F выполняется неравенство
F ( x) max{F ( x1 ),..., F ( x k )} .
Поскольку каждая точка выпуклого многогранника представима в
виде выпуклой комбинации его вершин, то из этого неравенства следует,
что в любой точке x C значение функции F ( x ) не больше чем ее
значение в крайней точке с наибольшим значением функции.
Следовательно, точка глобального максимума функции
на
множестве С conv(V ) conv(V ) находится среди крайних точек этого
множества.
Крайняя точка, в которой значение целевой функции не меньше ее
значений в соседних точках, называется точкой локального максимума
функции F ( x ) . Основной проблемой при решении задачи (1) является то
обстоятельство, что для квазивыпуклой функции, заданной на выпуклом
множестве, точка локального максимума не обязательно является и точкой
глобального максимума функции на этом множестве.
Приводимый ниже алгоритм включает следующие основные
элементы:
1. Нахождение точки локального максимума.
2. Статистическое моделирование направлений поиска области в
допустимом множестве с большим значением целевой функции.
3. Усечение исходного множества опорными гиперплоскостями к
поверхности текущего уровня целевой функции.
Точка локального максимума функции может быть найдена просто,
поскольку предполагается заданной матрица Z , по которой для каждой
крайней точки легко находится множество соседних крайних точек. Если
среди соседних точек находится точка с большим значением функции, то
осуществляется переход к этой точке и т.д. до тех пор, пока не будет
найдена точка локального максимума.
Пусть u 0 - найденная точка локального максимума и (u 0 ) m0 .
Обозначим соседние с u 0 вершины (крайние точки) выпуклого
множества С через u j ; j 1,..., l . Пусть u c - случайная точка на
выпуклой оболочке conv{u1,..., u l } .
Известия Петербургского университета путей сообщения
2004/1
Автоматика, телемеханика и связь на железных дорогах
130
Находим точку wc пересечения луча h {u t u 0 t (u c u 0 ), t 0} с
выпуклым множеством С . Искомой точке wc будет соответствовать
значение t c max{t : u t C} . Положим wc u tmax , ( wc ) m .
Если m m0 , то попытка моделирования u c считается неудачной,
при этом следует повторить процесс моделирования. В противном случае,
когда m m0 , строим опорную гиперплоскость к поверхности уровня
(u ) m в точке wc . Из полупространств, определяемых этой
гиперплоскостью выберем то, которое не содержит u 0 . При этом
допустимое
множество сужается,
и к полученной задаче снова
применяется описанный алгоритм.
Процесс останавливается тогда, когда все попытки моделирования
точки u c оказываются неудачными. Общее число попыток предполагается
ограниченным числом M , которое является входным параметром
алгоритма.
Опишем наиболее простой способ моделирования случайной точки
c
u . Используя стандартные датчики случайных чисел, смоделируем l 1
точку X1,..., X l 1 с равномерным распределением на отрезке [0,1].
Образуем из этих точек вариационный ряд X (1) X (2) ... X (l 1) .
l
Пусть X (0)
0, X (l ) 1,
i
X (i )
X (i 1) , i 1,..., l . Положим u
c
i
ui .
i 1
Корректность работы алгоритма основывается на следующем
утверждении.
Теорема 2. Обозначим через u M крайнюю точку локального
максимума, найденную после завершения работы алгоритма, а через C *
множество точек глобального максимума функции
на множестве C .
M
Вероятность события {u
C*} стремится к единице при неограниченном
возрастании M.
Доказательство теоремы проводится аналогично доказательству
теоремы 2 (Баушев А.Н., Морозова Е.Ю., 2004).
Для реализации описанного алгоритма была разработана программа
на базе пакета MATLAB.
4. Пример
Для иллюстрации работы алгоритма был рассмотрен следующий
пример. Было сгенерировано сто точек из двумерного нормального
распределения и по описанному алгоритму найден диаметр этого
множества. В процессе алгоритма были найдены две точки локального
максимума функции , которым соответствуют диагонали на рисунке 1.
Вторая из этих точек оказалась точкой глобального максимума.
2004/1
Известия Петербургского университета путей сообщения
Автоматика, телемеханика и связь на железных дорогах
131
5. Заключение
Предложенный алгоритм позволяет находить диаметр конечного
множества точек в евклидовом пространстве. Алгоритм является
эффективным с точки зрения затрат машинного времени в случае
большого числа точек .
Рис.1. Иллюстрация работы алгоритма на случайном плоском
множестве точек
6. Литература
Баушев А.Н., Морозова Е.Ю., Осьминин А.Т., Елисеев С.Ю., Рящиков А.С. О задаче
квазивогнутого программирования и еѐ применении к проблеме оптимизации
железнодорожных перевозок. – Обозрение прикладной и промышленной
математики. Т. 10. В. 3, 2003, с. 603-604
Баушев А.Н., Морозова Е.Ю. Метод статистических испытаний в задаче
квазивогнутого программирования. // Обозрение прикладной и промышленной
математики. Т.11. В.1, 2004, с.34-40
Известия Петербургского университета путей сообщения
2004/1
Документ
Категория
Без категории
Просмотров
8
Размер файла
741 Кб
Теги
пространство, евклидовой, конечного, множества, точек, определение, диаметра
1/--страниц
Пожаловаться на содержимое документа