Жадный геометрический гаечный ключ

Жадный геометрический гаечный ключ на 100 случайных точек с коэффициентом растяжения t = 2

Жадный геометрический гаечный ключ из тех же точек с коэффициентом растяжения t = 1,1

В вычислительной геометрии , А жадные геометрический ключ является неориентированный граф , вершины которого представляют собой точки в евклидовом пространстве , а ребра выбираются с помощью жадного алгоритма , чтобы сделать кратчайший путь расстояния в графе (с ребрами , взвешенных по длине) аппроксимируют евклидовых расстояний между парами точек. Конструкция жадных гаечных ключей была впервые опубликована Инго Альтхёфером и др. в 1993 г ​​.; в их статье также приписывается Маршаллу Берну (неопубликовано) независимое открытие той же конструкции. ^[1]

Жадные геометрические гаечные ключи имеют ограниченную степень , линейное общее количество ребер и общий вес, близкий к весу евклидова минимального остовного дерева . Хотя известные методы построения для них медленные, известны алгоритмы быстрого приближения с аналогичными свойствами. ^[2]

Строительство [ править ]

Жадный геометрический ключ определяется из входных данных, состоящих из набора точек и параметра . Цель состоит в том, чтобы построить граф, кратчайшие пути которого в большинстве случаев больше геометрических расстояний между парами точек. Его можно построить с помощью жадного алгоритма, который по одному добавляет ребра к графу, начиная с графа без ребер с точками в качестве вершин. Все пары точек рассматриваются в отсортированном (возрастающем) порядке по расстояниям, начиная с ближайшей пары . Для каждой пары точек алгоритм проверяет, содержит ли уже построенный граф путь от до длиной не более . Если нет, то край с длиной${\ displaystyle t \ geq 1}$${\ displaystyle t}$${\ Displaystyle (и, v)}$${\ displaystyle u}$${\ displaystyle v}$${\ Displaystyle т \ cdot d (и, v)}$${\ displaystyle uv}$${\ Displaystyle д (и, v)}$добавляется к графику. По построению результирующий график представляет собой геометрический гаечный ключ с коэффициентом растяжения не выше . ^[1]${\ displaystyle t}$

Наивная реализация этого метода потребовала бы времени для ввода с точками. Это связано с тем, что рассмотрение каждой из пар точек включает в себя экземпляр алгоритма Дейкстры для поиска кратчайшего пути в графе с ребрами. Он использует пространство для хранения отсортированного списка пар точек. Более тщательные алгоритмы можно построить такой же график во время , ^[3] или в пространстве . ^[4] Конструкция варианта жадного гаечного ключа, использующего кластеризацию графов для быстрого приближения расстояний графов, работает во времени в евклидовом пространстве любой ограниченной размерности и может производить гаечные ключи с (приблизительно) теми же свойствами, что и жадные гаечные ключи.${\ Displaystyle О (п ^ {3} \ журнал п)}$${\ displaystyle n}$${\ Displaystyle О (п ^ {2})}$${\ Displaystyle О (п)}$${\ Displaystyle О (п ^ {2})}$${\ Displaystyle О (п ^ {2} \ журнал п)}$${\ Displaystyle О (п)}$${\ Displaystyle О (п \ журнал п)}$^{[5] [6]} Тот же метод можно распространить на пространства с ограниченной удвоенной размерностью . ^[2]

Свойства [ править ]

Та же жадная конструкция производит гаечные ключи в произвольных метрических пространствах , но в евклидовых пространствах она обладает хорошими свойствами, некоторые из которых в целом не выполняются. ^[2]

Жадный геометрический гаечный ключ в любом метрическом пространстве всегда содержит минимальное остовное дерево входных данных, потому что алгоритм жадного построения следует тому же порядку вставки ребер, что и алгоритм Крускала для минимальных остовных деревьев. Если алгоритм жадного гаечного ключа и алгоритм Крускала запускаются параллельно, рассматривая одни и те же пары вершин в одном порядке, каждое ребро, добавленное алгоритмом Крускала, также будет добавлено алгоритмом жадного гаечного ключа, потому что конечные точки ребра еще не будут соединены дорогой. В предельном случае, когда оно достаточно велико (например , где - количество вершин в графе), два алгоритма производят одинаковый результат. ^[1]${\ displaystyle t}$${\ displaystyle t> n}$${\ displaystyle n}$

В евклидовых пространствах ограниченной размерности для любой константы жадные геометрические гаечные ключи на множествах точек имеют ограниченную степень , что означает, что они также имеют ребра. ^{[7] [8] [5]} Это свойство не распространяется даже на метрические пространства с хорошим поведением: существуют пространства с ограниченной удвоенной размерностью, в которых жадный гаечный ключ имеет неограниченную степень вершины. ^{[2] [9] [10]} Однако в таких пространствах количество ребер все равно остается . ^[2]${\ displaystyle t}$${\ displaystyle t}$${\ displaystyle n}$${\ Displaystyle О (п)}$${\ Displaystyle О (п)}$

Жадные геометрические гаечные ключи в евклидовых пространствах ограниченной размерности также имеют общий вес не более чем на постоянную величину, умноженную на общий вес евклидова минимального остовного дерева . ^{[7] [8] [5]} Это свойство сохраняется в пространствах ограниченной удвоенной размерности. ^[2]

Ссылки [ править ]