Самый дальний-первый обход

Последовательность точек, удаленных от предыдущих точек

Первые пять точек в дальнем первом обходе плоского множества точек. Первая точка выбирается произвольно, а каждая последующая точка находится как можно дальше от всех ранее выбранных точек.

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

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

Определение и свойства

Обход наиболее дальнего первого — это последовательность точек в компактном метрическом пространстве , где каждая точка появляется не более одного раза. Если пространство конечно, каждая точка появляется ровно один раз, и обход является перестановкой всех точек в пространстве. Первая точка последовательности может быть любой точкой в ​​пространстве. Каждая точка p после первой должна иметь максимально возможное расстояние до множества точек, более ранних, чем p в последовательности, где расстояние от точки до множества определяется как минимум попарных расстояний до точек в множестве. Данное пространство может иметь много различных обходов наиболее дальнего первого, в зависимости как от выбора первой точки в последовательности (которая может быть любой точкой в ​​пространстве), так и от связей для максимального расстояния среди более поздних выборов. ^[2]

Обходы самой дальней точки могут быть охарактеризованы следующими свойствами. Зафиксируем число k и рассмотрим префикс, образованный первыми k точками обхода самой дальней первой точки любого метрического пространства. Пусть r — расстояние между конечной точкой префикса и другими точками в префиксе. Тогда это подмножество обладает следующими двумя свойствами:

• Все пары выбранных точек находятся на расстоянии не менее r друг от друга, и
• Все точки метрического пространства находятся на расстоянии не более r от подмножества.

Наоборот, любая последовательность, имеющая эти свойства, для всех выборов k , должна быть дальним первым обходом. Это два определяющих свойства множества Делоне , поэтому каждый префикс дальнего первого обхода образует множество Делоне. ^[3]

Приложения

Rosenkrantz, Stearns & Lewis (1977) использовали дальний первый обход для определения эвристики дальнего вставки для задачи коммивояжера . Эта эвристика находит приближенные решения задачи коммивояжера, создавая тур на подмножестве точек, добавляя по одной точке за раз в тур в порядке, заданном дальним первым обходом. Чтобы добавить каждую точку в тур, одно ребро предыдущего тура разрывается и заменяется парой ребер через добавленную точку, самым дешевым из возможных способов. Хотя Rosenkrantz и др. доказывают только логарифмическое отношение аппроксимации для этого метода, они показывают, что на практике он часто работает лучше, чем другие методы вставки с лучшими доказуемыми отношениями аппроксимации. ^[4]

Позже та же последовательность точек была популяризирована Гонсалесом (1985), который использовал ее как часть жадных алгоритмов аппроксимации для двух задач кластеризации, в которых целью является разбиение набора точек на k кластеров. Одна из двух задач, которые Гонсалес решает таким образом, стремится минимизировать максимальный диаметр кластера, в то время как другая, известная как метрическая задача k -центра , стремится минимизировать максимальный радиус, расстояние от выбранной центральной точки кластера до самой дальней точки от него в том же кластере. Например, задача k -центра может быть использована для моделирования размещения пожарных станций в городе, чтобы гарантировать, что каждый адрес в городе может быть быстро достигнут пожарной машиной. Для обеих задач кластеризации Гонсалес выбирает набор из k центров кластеров, выбирая первые k точек наиболее дальнего первого обхода, а затем создает кластеры, назначая каждую входную точку ближайшему центру кластера. Если r — расстояние от набора из k выбранных центров до следующей точки в позиции k  + 1 в обходе, то при таком кластеризации каждая точка находится в пределах расстояния r от своего центра, а диаметр каждого кластера не превышает 2 r . Однако подмножество из k центров вместе со следующей точкой находятся на расстоянии не менее r друг от друга, и любая k -кластеризация поместит некоторые две из этих точек в один кластер, причем один из них будет находиться на расстоянии не менее r /2 от своего центра и с диаметром не менее r . Таким образом, эвристика Гонсалеса дает коэффициент аппроксимации 2 для обеих задач кластеризации. ^[3]

Эвристика Гонсалеса была независимо переоткрыта для метрической проблемы k -центра Дайером и Фризе (1985), которые применили ее в более общем виде к взвешенным проблемам k -центра. ^[5] Другая работа по проблеме k -центра того же времени, Хохбаум и Шмойс (1985), достигает того же коэффициента аппроксимации 2, ^[6] но ее методы отличаются. ^[5] Тем не менее, эвристика Гонсалеса и название «обход самого дальнего первого» часто неправильно приписываются Хохбауму и Шмойсу. ^[7] Как для задачи кластеризации диаметра min-max, так и для метрической проблемы k -центра эти аппроксимации оптимальны: существование эвристики полиномиального времени с любым постоянным коэффициентом аппроксимации меньше 2 означало бы, что P = NP . ^{[3] [6]}

Как и для кластеризации, обход наиболее дальнего первого может также использоваться в другом типе задачи размещения объектов, задаче дисперсии объектов на максимум-мин, в которой цель состоит в том, чтобы выбрать местоположения k различных объектов так, чтобы они находились как можно дальше друг от друга. Точнее, цель в этой задаче состоит в том, чтобы выбрать k точек из заданного метрического пространства или заданного набора точек-кандидатов таким образом, чтобы максимизировать минимальное попарное расстояние между выбранными точками. Опять же, это можно аппроксимировать выбором первых k точек обхода наиболее дальнего первого. Если r обозначает расстояние k -й точки от всех предыдущих точек, то каждая точка метрического пространства или набора кандидатов находится в пределах расстояния r от первых k  − 1 точек. По принципу ящика некоторые две точки оптимального решения (какой бы она ни была) должны находиться в пределах расстояния r от одной и той же точки среди этих первых k  − 1 выбранных точек и (по неравенству треугольника ) в пределах расстояния 2 r друг от друга. Таким образом, эвристическое решение, полученное с помощью обхода самого дальнего первого узла, отличается от оптимального примерно в два раза. ^{[8] [9] [10]}

Другие приложения обхода наиболее дальнего первого включают квантование цвета (кластеризация цветов на изображении в меньший набор репрезентативных цветов), ^[11] прогрессивное сканирование изображений (выбор порядка отображения пикселей изображения таким образом, чтобы префиксы порядка создавали хорошие версии всего изображения с более низким разрешением, а не заполняли изображение сверху вниз), ^[12] выбор точек в методе вероятностной дорожной карты для планирования движения , ^[13] упрощение облаков точек , ^[14] генерация масок для полутоновых изображений, ^{[15] [16]} иерархическая кластеризация , ^[1] поиск сходств между полигональными сетками схожих поверхностей, ^[17] выбор разнообразных и ценных целей наблюдения для подводных роботизированных исследований, ^[18] обнаружение неисправностей в сенсорных сетях , ^[19] моделирование филогенетического разнообразия , ^[20] сопоставление транспортных средств в гетерогенном парке с запросами клиентов на доставку, ^[21] равномерное распределение геодезических обсерваторий на поверхности Земли ^[22] или других типов сенсорных сетей, ^[23] генерация виртуальных точечных источников света в методе мгновенного рендеринга компьютерной графики с использованием излучения , ^[24] и геометрический диапазон поиска структур данных . ^[25]

Алгоритмы

Жадный точный алгоритм

Самый дальний обход конечного множества точек может быть вычислен с помощью жадного алгоритма , который сохраняет расстояние каждой точки от ранее выбранных точек, выполняя следующие шаги: ^[3]

• Инициализируем последовательность выбранных точек пустой последовательностью, а расстояния каждой точки до выбранных точек — бесконечностью.
• Пока не все точки выбраны, повторите следующие шаги:
  • Просмотрите список еще не выбранных точек, чтобы найти точку p , которая находится на максимальном расстоянии от выбранных точек.
  • Удалим p из еще не выбранных точек и добавим его в конец последовательности выбранных точек.
  • Для каждой оставшейся, еще не выбранной точки q , замените расстояние, сохраненное для q, на минимум ее старого значения и расстояние от p до q .

Для набора из n точек этот алгоритм требует O ( n ² ) шагов и O ( n ² ) вычислений расстояния. ^[3]

Приближения

Более быстрый алгоритм приближения , предложенный Хар-Пеледом и Менделем (2006), применим к любому подмножеству точек в метрическом пространстве с ограниченной размерностью удвоения , классу пространств, включающих евклидовы пространства ограниченной размерности. Их алгоритм находит последовательность точек, в которой каждая последующая точка имеет расстояние в пределах 1 −  ε -множителя самого дальнего расстояния от ранее выбранной точки, где ε может быть выбрано любым положительным числом. Это занимает время . ^[2] ${\displaystyle O(n\log n)}$

Результаты для ограниченной размерности удвоения не применимы к многомерным евклидовым пространствам, поскольку постоянный множитель в большой нотации O для этих алгоритмов зависит от размерности. Вместо этого другой метод аппроксимации, основанный на лемме Джонсона–Линденштрауса и локально-чувствительном хешировании, имеет время выполнения Для метрик, определенных кратчайшими путями на взвешенных неориентированных графах, рандомизированная инкрементная конструкция, основанная на алгоритме Дейкстры, достигает времени , где n и m — числа вершин и ребер входного графа соответственно. ^[26] ${\displaystyle O(\varepsilon ^{-2}n^{1+1/(1+\varepsilon )^{2}+o(1)}).}$ ${\displaystyle O(\varepsilon ^{-1}m\log n\log {\tfrac {n}{\varepsilon }})}$

Инкрементная вставка Вороного

Для выбора точек из непрерывного пространства, такого как евклидова плоскость , а не из конечного набора точек-кандидатов, эти методы не будут работать напрямую, поскольку потребуется поддерживать бесконечное количество расстояний. Вместо этого каждая новая точка должна быть выбрана как центр наибольшего пустого круга, определяемого ранее выбранным набором точек. ^[12] Этот центр всегда будет лежать на вершине диаграммы Вороного уже выбранных точек или в точке, где ребро диаграммы Вороного пересекает границу области. В этой формулировке метод построения обходов наиболее дальнего первого уровня также называется инкрементной вставкой Вороного . ^[27] Он похож на уточнение Делоне для генерации сетки конечных элементов , но отличается выбором вершины Вороного для вставки на каждом шаге. ^[28]

Смотрите также

• Алгоритм Ллойда — другой метод генерации равномерно распределенных точек в геометрических пространствах.

Ссылки

1. Dasgupta, S.; Long, PM (2005), "Гарантии производительности для иерархической кластеризации", Журнал компьютерных и системных наук , 70 (4): 555–569, doi : 10.1016/j.jcss.2004.10.006 , MR  2136964
2. Har-Peled, S. ; Mendel, M. (2006), "Быстрое построение сетей в низкоразмерных метриках и их приложения", SIAM Journal on Computing , 35 (5): 1148–1184, arXiv : cs/0409057 , doi :10.1137/S0097539704446281, MR  2217141, S2CID  37346335
3. Гонсалес, TF (1985), «Кластеризация для минимизации максимального межкластерного расстояния», Теоретическая информатика , 38 (2–3): 293–306, doi : 10.1016/0304-3975(85)90224-5 , MR  0807927
4. Розенкранц, DJ; Стернс, RE; Льюис, PM II (1977), «Анализ нескольких эвристик для задачи коммивояжера», SIAM Journal on Computing , 6 (3): 563–581, doi :10.1137/0206041, MR  0459617, S2CID  14764079
5. Дайер, ME ; Фриз, AM (1985), «Простая эвристика для проблемы p-центра» (PDF) , Operations Research Letters , 3 (6): 285–288, doi :10.1016/0167-6377(85)90002-1, MR  0797340
6. Hochbaum, Dorit S. ; Shmoys, David B. (1985), "Лучшая возможная эвристика для проблемы k -центра", Mathematics of Operations Research , 10 (2): 180–184, doi :10.1287/moor.10.2.180, MR  0793876
7. Яркие примеры неправильного приписывания эвристики «самый дальний первый» Хохбауму и Шмойсу (1985) см., например,
   • Dasgupta, Sanjoy (2002), "Гарантии производительности для иерархической кластеризации", в Kivinen, Jyrki; Sloan, Robert H. (ред.), Computational Learning Theory, 15-я ежегодная конференция по Computational Learning Theory, COLT 2002, Сидней, Австралия, 8-10 июля 2002 г., Труды , Lecture Notes in Computer Science, т. 2375, Springer, стр. 351–363, doi :10.1007/3-540-45435-7_24, ISBN 978-3-540-43836-6(исправлено в журнальной версии той же статьи за 2005 год)
   • Агарвал, Самир; Рамамурти, Рави; Белонжи, Серж Дж.; Дженсен, Хенрик Ванн (2003), «Структурированная выборка важности карт окружающей среды», ACM Trans. Graph. , 22 (3): 605–612, doi :10.1145/882262.882314
   • Барам, Йорам; Эль-Янив, Ран; Луз, Коби (2004), «Онлайн-выбор алгоритмов активного обучения» (PDF) , J. Mach. Learn. Res. , 5 : 255–291
   • Basu, Sugato; Bilenko, Michael; Banerjee, Arindam; Mooney, Raymond J. (2006), «Вероятностная полуконтролируемая кластеризация с ограничениями», в Chapelle, Olivier; Schölkopf, Bernhard; Zien, Alexander (ред.), Полуконтролируемое обучение , The MIT Press, стр. 73–102, doi :10.7551/mitpress/9780262033589.003.0005, ISBN 978-0-262-03358-9
   • Лима, Кристиан Феррейра Лемос; Ассис, Франциско М.; де Соуза, Клеонилсон Протасио (2011), «Сравнительное исследование использования энтропии Шеннона, Реньи и Цаллиса для выбора атрибутов при обнаружении сетевых вторжений», Международный семинар IEEE по измерениям и сетям, M&N 2011, Анакапри, Италия, 10-11 октября 2011 г. , IEEE, стр. 77–82, doi :10.1109/IWMN.2011.6088496, S2CID  7510040
   • «Class FarthestFirst», Weka , версия 3.9.5 , Университет Вайкато, 21 декабря 2020 г. , получено 06.11.2021 г. – через SourceForge
8. Уайт, Дуглас Дж. (1991), «Проблема максимальной дисперсии», Журнал IMA по математике, применяемой в бизнесе и промышленности , 3 (2): 131–140 (1992), doi :10.1093/imaman/3.2.131, MR  1154657; Уайт приписывает использование обхода наиболее дальнего первого элемента в качестве эвристики для этой проблемы Steuer, RE (1986), Multiple-Criteria Optimization: Theory, Computation, and Applications , New York: Wiley
9. Тамир, Ари (1991), «Неприятное расположение объектов на графах», SIAM Journal on Discrete Mathematics , 4 (4): 550–567, doi :10.1137/0404048, MR  1129392
10. Рави, СС; Розенкранц, Д.Дж.; Тайи, ГК (1994), «Эвристические и специальные алгоритмы для задач дисперсии», Исследование операций , 42 (2): 299–310, doi :10.1287/opre.42.2.299, JSTOR  171673, S2CID  16489402
11. Сян, З. (1997), «Квантование цветного изображения путем минимизации максимального межкластерного расстояния», ACM Transactions on Graphics , 16 (3): 260–276, doi : 10.1145/256157.256159 , S2CID  17713417
12. Eldar, Y.; Lindenbaum, M.; Porat, M.; Zeevi, YY (1997), «Стратегия самой дальней точки для прогрессивной выборки изображений», IEEE Transactions on Image Processing , 6 (9): 1305–1315, Bibcode : 1997ITIP....6.1305E, doi : 10.1109/83.623193, PMID  18283019
13. Мазер, Э.; Ауактцин, Дж. М.; Бессьер, П. (1998), «Алгоритм клубка Ариадны», Журнал исследований искусственного интеллекта , 9 : 295–316, arXiv : 1105.5440 , doi : 10.1613/jair.468
14. Мённинг, К.; Доджсон, Н.А. (2003), «Новый алгоритм упрощения облака точек», 3-я Международная конференция IASTED по визуализации, визуализации и обработке изображений
15. Готсман, Крейг; Аллебах, Ян П. (1996), «Границы и алгоритмы для экранов с дизерингом» (PDF) , в Роговиц, Бернис Э.; Аллебах, Ян П. (ред.), Человеческое зрение и электронная визуализация , Proc. SPIE, т. 2657, стр. 483–492, doi :10.1117/12.238746, S2CID  10608234
16. Шахиди, Р.; Молони, К.; Рампони, Г. (2004), «Проектирование масок самой дальней точки для полутонирования изображений», Журнал EURASIP по прикладной обработке сигналов , 2004 (12): 1886–1898, Bibcode : 2004EJASP2004...45S, doi : 10.1155/S1110865704403217
17. Липман, Ю.; Фанкхаузер, Т. (2009), «Голосование Мёбиуса за поверхностное соответствие», Proc. ACM SIGGRAPH , стр. 72:1–72:12, doi :10.1145/1576246.1531378, ISBN 978-1-60558-726-4, S2CID  6001942
18. Гирдхар, И.; Жигер, П.; Дудек, Г. (2012), «Автономное адаптивное подводное исследование с использованием онлайн-тематического моделирования» (PDF) , Proc. Int. Symp. Experimental Robotics
19. Altinisik, U.; Yildirim, M.; Erkan, K. (2012), «Изоляция непредопределенных неисправностей датчиков с использованием алгоритма дальнего первого обхода», Ind. Eng. Chem. Res. , 51 (32): 10641–10648, doi :10.1021/ie201850k
20. Бордевич, Магнус; Родриго, Аллен; Семпл, Чарльз (2008), «Выбор таксонов для сохранения или секвенирования: желаемые критерии и жадное решение», Systematic Biology , 57 (6): 825–834, doi : 10.1080/10635150802552831 , PMID  19085326
21. Фишер, Маршалл Л.; Джайкумар, Рамчандран (1981), «Обобщенная эвристика назначения для маршрутизации транспортных средств», Networks , 11 (2): 109–124, doi :10.1002/net.3230110205, MR  0618209; как цитируется Гейсенсом, Филиппом; Голденом, Брюсом; Ассадом, Арджангом (1986), «Новая эвристика для определения размера и состава флота», в Галло, Джорджио; Санди, Клаудио (ред.), Netflow в Пизе , Исследования математического программирования, т. 26, Springer, стр. 233–236, doi :10.1007/bfb0121103, ISBN 978-3-642-00922-8
22. Хазе, Хайо (2000), «Новый метод выбора дополнительных участков для гомогенизации неоднородного косферического распределения точек», в Rummel, Reinhard; Drewes, Hermann; Bosch, Wolfgang; et al. (ред.), Towards an Integrated Global Geodetic Observing System (IGGOS): Симпозиум IAG Section II в Мюнхене, 5–9 октября 1998 г., Постеры – Сессия B , Симпозиумы Международной ассоциации геодезии, том 120, Springer, стр. 180–183, doi :10.1007/978-3-642-59745-9_35, ISBN 978-3-642-64107-7
23. Виейра, Луис Филипе М.; Виейра, Маркос Аугусто М.; Руис, Линьер Беатрис ; Лоурейро, Антонио А.Ф.; Сильва, Диоген Сесилио; Фернандес, Антонио Отавио (2004), «Эффективный алгоритм развертывания дополнительной сенсорной сети» (PDF) , Proc. Бразильский симп. Компьютерные сети , стр. 3–14.
24. Лайне, Самули; Сарансаари, Ханну; Контканен, Янне; Лехтинен, Яакко; Айла, Тимо (2007), «Постепенная мгновенная излучательность для непрямого освещения в реальном времени», Материалы 18-й конференции Eurographics по методам рендеринга (EGSR'07) , Эйр-ла-Виль, Швейцария, Швейцария: Ассоциация Eurographics, стр. 277 –286, дои :10.2312/EGWR/EGSR07/277-286, ISBN 978-3-905673-52-4, S2CID  18626929
25. Аббар, С.; Амер-Яхья, С.; Индик, П.; Махабади, С.; Варадараджан, К. Р. (2013), «Проблема разнообразных близких соседей», Труды 29-го ежегодного симпозиума по вычислительной геометрии , стр. 207–214, doi : 10.1145/2462356.2462401, hdl : 1721.1/87000 , ISBN 978-1-4503-2031-3, S2CID  6286186
26. Эппштейн, Дэвид ; Хар-Пелед, Сариэль ; Сидиропулос, Анастасиос (2020), «Приблизительная жадная кластеризация и выбор расстояния для метрик графа», Журнал вычислительной геометрии , 11 (1): 629–652, doi :10.20382/jocg.v11i1a25, MR  4194877, S2CID  18316279
27. Терамото, Сачио; Асано, Тетсуо ; Като, Наоки; Доерр, Бенджамин (2006), «Вставка точек одинаково в каждом случае», IEICE Transactions on Information and Systems , E89-D (8): 2348–2356, Bibcode : 2006IEITI..89.2348T, doi : 10.1093/ietisy/e89-d.8.2348, hdl : 2433/84849
28. Рупперт, Джим (1995), «Алгоритм уточнения Делоне для качественной генерации двумерной сетки», Журнал алгоритмов , 18 (3): 548–585, doi :10.1006/jagm.1995.1021