Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
EMST из 25 случайных точек на плоскости

Евклидово минимального покрывающего дерево или EMST является минимальным покрывающим деревом из набора п точек в плоскости (или в более общем случае в ℝ г ), где вес ребра между каждой парой точек является евклидовом расстояния между этими двумя точками. Проще говоря, EMST соединяет набор точек с помощью линий, так что общая длина всех линий минимизируется, и любая точка может быть достигнута из любой другой, следуя линиям.

В плоскости, EMST для заданного множества точек может быть найден в & thetas ; ( п войти п ) раз , используя O ( п ) пространство в алгебраическом дереве решений модели вычислений. Более быстрые рандомизированные алгоритмы сложности O ( n  log log  n ) известны в более мощных моделях вычислений, которые более точно моделируют возможности реальных компьютеров. [1]

В более высоких измерениях ( d ≥ 3) поиск оптимального алгоритма остается открытой проблемой .

Нижняя граница [ править ]

Асимптотическая нижняя граница Ω ( n log n ) для временной сложности задачи EMST может быть установлена ​​в ограниченных моделях вычислений, таких как модели алгебраического дерева решений и алгебраического дерева вычислений , в которых алгоритм имеет доступ только к входным точкам через определенные ограниченные примитивы, которые выполняют простые алгебраические вычисления над своими координатами: в этих моделях проблема ближайшей пары точек требует времени Ω ( n  log  n ), но ближайшая пара обязательно является краем EMST, поэтому EMST также требует этого много времени. [2]Однако, если входные точки имеют целочисленные координаты и побитовые операции, а операции индексации таблиц разрешены с использованием этих координат, тогда возможны более быстрые алгоритмы. [1]

Алгоритмы для вычисления ЕМСТ в двух измерениях [ править ]

Самый простой алгоритм для поиска EMST в двух измерениях, учитывая n точек, состоит в том, чтобы фактически построить полный граф на n вершинах, который имеет n ( n -1) / 2 ребра, вычислить вес каждого ребра, найдя расстояние между каждой парой точек, а затем запустить на нем стандартный алгоритм минимального остовного дерева (например, версию алгоритма Прима или алгоритма Крускала ). Поскольку этот граф имеет Θ ( n 2 ) ребер для n различных точек, его построение уже требует Ω ( n 2 ) времени. Для этого решения также требуется Ω (n 2 ) место для хранения всех краев.

Лучший подход к нахождению Эмста в плоскости, следует отметить , что подграф каждую триангуляции Делона из п точек, значительно уменьшенный набора ребер:

  1. Вычислите триангуляцию Делоне за время O ( n log n ) и пространство O ( n ). Поскольку триангуляция Делоне является плоским графом , а количество ребер в любом плоском графе не более чем в три раза превышает количество вершин, это генерирует только O ( n ) ребер.
  2. Обозначьте каждый край его длиной.
  3. Запустите алгоритм минимального остовного дерева графа на этом графе, чтобы найти минимальное остовное дерево. Так как существует O ( N ) ребер, это требует O ( п войти п ) времени с использованием любого стандартного минимального остовного дерева алгоритмы , такие как алгоритм борувки , алгоритм Прима или алгоритма Крускала .

Конечным результатом является алгоритм, занимающий время O ( n log n ) и пространство O ( n ).

Если входные координаты являются целыми числами и могут использоваться в качестве индексов массива , возможны более быстрые алгоритмы: триангуляция Делоне может быть построена с помощью рандомизированного алгоритма за ожидаемое время O ( n  log log  n ). [1] Кроме того, поскольку триангуляция Делоне является плоским графом , ее минимальное остовное дерево может быть найдено за линейное время с помощью варианта алгоритма Борувки, который удаляет все ребра, кроме самых дешевых, между каждой парой компонентов после каждого этапа алгоритма. [3] Следовательно, общее ожидаемое время для этого алгоритма составляет O ( n  log log  n ). [1]

Высшие измерения [ править ]

Проблема также может быть обобщена на n точек в d -мерном пространстве ℝ d . В более высоких измерениях связность, определяемая триангуляцией Делоне (которая также разделяет выпуклую оболочку на d -мерные симплексы ), содержит минимальное остовное дерево; однако триангуляция может содержать полный граф. [4] Следовательно, поиск евклидова минимального остовного дерева как остовного дерева полного графа или как остовного дерева триангуляции Делоне занимает время O ( dn 2 ). Для трех измерений можно найти минимальное остовное дерево за время O (( n  log n ) 4/3 ), и в любом измерении больше трех его можно решить за время, которое быстрее, чем квадратичная временная граница для полного графа и алгоритмов триангуляции Делоне. [4] Для равномерно случайных наборов точек можно вычислить минимальные остовные деревья так же быстро, как и сортировку. [5] Используя хорошо разделенную парную декомпозицию , можно получить (1 + ε) -аппроксимацию за время O ( n log n ). [6]

Поддерево триангуляции Делоне [ править ]

Все края с Emst являются ребром относительных окрестностей графа , [7] [8] [9] , который , в свою очередь , является ребром графа Gabriel , которые являются ребром в триангуляции Делона точек, [10] [11] , как можно доказать с помощью эквивалентного контрапозитивного утверждения: каждое ребро, не входящее в триангуляцию Делоне, также не входит ни в какой EMST. Доказательство основано на двух свойствах минимальных остовных деревьев и триангуляций Делоне:

  1. ( свойство цикла минимальных остовных деревьев): для любого цикла C в графе, если вес ребра e из C больше, чем веса других ребер C, то это ребро не может принадлежать MST .
  2. (свойство триангуляции Делоне): если есть круг с двумя входными точками на его границе, который не содержит других входных точек, линия между этими двумя точками является ребром каждой триангуляции Делоне.

Рассмотрим ребро e между двумя входными точками p и q, которое не является ребром триангуляции Делоне. Свойство 2 означает, что окружность C с диаметром e должна содержать другую точку r внутри. Но тогда r ближе как к p, так и к q, чем они друг к другу, и поэтому ребро от p до q является самым длинным ребром в цикле точек p → q → r → p , и по свойству 1 e не принадлежит любой ЕМСТ.

Ожидаемый размер [ править ]

Ожидаемый размер EMST для большого количества точек был определен Дж. Майклом Стилом . [12] Если - плотность функции вероятности для точек выбора, то для больших и размер EMST приблизительно равен

где - константа, зависящая только от размерности . Точные значения констант неизвестны, но могут быть оценены на основании эмпирических данных.

Приложения [ править ]

Очевидное применение евклидовых минимальных остовных деревьев - найти самую дешевую сеть проводов или труб для соединения набора мест, предполагая, что ссылки стоят фиксированную сумму за единицу длины. Однако, хотя они дают абсолютную нижнюю границу необходимого количества соединений, большинство таких сетей предпочитают k-связанный граф дереву, так что отказ любого отдельного канала не разбивает сеть на части.

Другое применение EMST - это алгоритм аппроксимации с постоянным множителем для приближенного решения евклидовой задачи коммивояжера , версии задачи коммивояжера на множестве точек на плоскости с ребрами, помеченными их длиной. Этот реалистичный вариант задачи может быть решен с коэффициентом 2 путем вычисления EMST, выполнения обхода по его границе, которая очерчивает все дерево, а затем удаления всех, кроме одного вхождения каждой вершины, из этого обхода.

Планарная реализация [ править ]

Проблема реализации для евклидовых минимальных остовных деревьев формулируется следующим образом: для дерева T  = ( V ,  E ) найти местоположение D ( u ) для каждой вершины u  ∈  V так, чтобы T было минимальным остовным деревом D ( u ) : u ∈ V, или определите, что таких местоположений не существует. Проверка существования реализация в плоскости является NP-трудной . [13]

См. Также [ править ]

  • Прямолинейное минимальное остовное дерево

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

  1. ^ a b c d Бучин, Кевин; Мульцер, Вольфганг (2009). Триангуляции Делоне за время O (sort ( n )) и более (PDF) . Proc. 50-й симпозиум IEEE по основам информатики . С. 139–148. DOI : 10.1109 / FOCS.2009.53 ..
  2. ^ Яо, AC-C. (1989), "Нижние оценки для алгебраических вычислительных деревьев с целочисленными входами", Proc. Тридцатый ежегодный симпозиум по Основе информатики (FOCS 1989) ., Стр 308-313, DOI : 10,1109 / SFCS.1989.63495.
  3. ^ Эпштайна, Дэвид (1999), "Spanning дерева и гаечные ключи", в Саке, J.-R. ; Уррутия, Дж. (Ред.), Справочник по вычислительной геометрии , Elsevier, стр. 425–461. CS1 maint: обескураженный параметр ( ссылка ); Мареш, Мартин (2004), "Два алгоритма линейного времени для MST на второстепенных классах замкнутых графов" (PDF) , Archivum mathematicum , 40 (3): 315–320 .
  4. ^ a b Агарвал, ПК ; Эдельсбруннер, Х .; Schwarzkopf, O .; Welzl, Е. (1991), "евклидовы минимум охватывает деревья и бихроматического ближайшие пары", Дискретные и Вычислительная геометрия , М., 6 (1): 407-422, DOI : 10.1007 / BF02574698.
  5. ^ Chatterjee, S .; Коннор, М .; Кумар П. (2010), «Геометрические минимальные остовные деревья с GeoFilterKruskal», в Фесте, Паола (ред.), Симпозиум по экспериментальным алгоритмам , Лекционные заметки по информатике, 6049 , Springer-Verlag, стр. 486–500, doi : 10.1007 / 978-3-642-13193-6_41.
  6. ^ Шмид, Михель (16 августа 2005). «Разложение хорошо разделенных пар и его приложения» (PDF) . Проверено 26 марта 2014 года . CS1 maint: discouraged parameter (link)
  7. ^ Ежи В. Яромчик и Годфрид Т. Туссен, «Графы относительного соседства и их родственники», Труды IEEE , Vol. 80, No. 9, сентябрь 1992 г., стр. 1502–1517.
  8. ^ Годфрид Т. Туссен, "Комментарий к алгоритмам для вычисления графа относительного соседства", Electronics Letters , Vol. 16, No. 22, October 1981, pp. 860–861.
  9. ^ Годфрид Т. Туссен, "График относительной окрестности конечного плоского множества", Распознавание образов , Vol. 12. 1980. С. 261–268.
  10. ^ Роберт Плесс. Лекция 17: Диаграммы Вороного и триангуляции Делоне. Весна 2003 г., страница класса вычислительной геометрии. Адъюнкт-профессор компьютерных наук и инженерии Вашингтонского университета. http://www.cs.wustl.edu/~pless/506/l17.html Архивировано 12 сентября 2006 г. на Wayback Machine.
  11. ^ Роберт Седжвик и Кевин Уэйн. Минимальные конспекты лекций по связующему дереву. Компьютерные науки 226: алгоритмы и структуры данных, весна 2007 г., Принстонский университет. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf
  12. ^ Стил, Дж. Майкл (1988). «Темпы роста евклидовых минимальных остовных деревьев со степенно взвешенными ребрами» (PDF) . Летопись вероятности . 16 (4): 1767–1787. DOI : 10.1214 / AOP / 1176991596 .
  13. ^ Идс, Питер ; Whitesides, Sue (1994), "Проблема реализации евклидовых минимальных остовных деревьев NP-трудна", Proc. Десятый ACM симпозиум по вычислительной геометрии . С. 49-56, DOI : 10,1145 / 177424,177507.
  • Колледж Смита: Проект открытых проблем: проблема 5: Евклидово минимальное остовное дерево
  • Институт информатики Макса Планка: Решения для упражнений , Кавита Теликепалли (Постскриптум)
  • STANN (Майкл Коннор, Пиюш Кумар и Самид Чаттерджи): библиотека C ++, которая может вычислять евклидовы минимальные остовные деревья в малых размерностях.