Самый дальний обход - Farthest-first traversal

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

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

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

Характеристики

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

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

Другими словами, каждый префикс обхода дальше всех образует Набор Delone.[1]

Приложения

Первое использование обхода дальше всех было сделано Розенкранц, Стернс и Льюис (1977) в связи с эвристика для задача коммивояжера. В эвристике самой дальней вставки, обсужденной Розенкранцем и др., Обход строится постепенно, добавляя по одной точке за раз в порядке, заданном обходом от самого дальнего до первого. Чтобы добавить каждую точку к обходу коммивояжера по предыдущим точкам, эта эвристика рассматривает все возможные способы взлома одного края обхода и замены его двумя ребрами через новую точку и выбирает наиболее дешевую из этих замен. Хотя Rosenkrantz et al. доказывать только логарифмический коэффициент аппроксимации для этого метода они показывают, что на практике он часто работает лучше, чем другие методы вставки с лучшими доказуемыми коэффициентами аппроксимации.[2]

Позже ту же последовательность точек популяризировал Гонсалес (1985), который использовал его как часть жадный алгоритм аппроксимации для проблемы поиска k кластеры, которые минимизируют максимум диаметр кластера. Тот же алгоритм применяется также с тем же качеством аппроксимации к метрика k-центр проблема. Эта проблема - одна из нескольких формулировок кластерный анализ и расположение объекта, в котором цель состоит в том, чтобы разбить заданный набор точек на k различные кластеры, каждый с выбранной центральной точкой, так что максимальное расстояние от любой точки до центра кластера минимизировано. Например, эту задачу можно использовать для моделирования размещения пожарных депо в городе, чтобы обеспечить быстрый доступ к каждому адресу в городе на пожарной машине. Гонсалес описал эвристику кластеризации, которая выбирает в качестве центров первые k точек обхода дальше всех, а затем присваивает каждой из входных точек ее ближайший центр. Если р это расстояние от множества k выбранные центры до следующей точки в позиции k + 1 в обходе, то это кластеризация достигает расстояния р. Однако подмножество k центры вместе со следующей точкой находятся на расстоянии не менее р друг от друга, и любые k-кластеризация поместит две из этих точек в один кластер, поэтому не существует кластеризации с расстоянием лучше, чем р/ 2. Таким образом, эвристика Гонсалеса дает коэффициент аппроксимации из 2 для этой проблемы.[1] Эту эвристику и название «самый дальний обход» часто ошибочно приписывают другой работе того же времени, Хохбаум и Шмойс (1985). Однако Хохбаум и Шмойс использовали теоретико-графические методы, а не обход с первого взгляда, чтобы получить другой алгоритм приближения для метрики. k-центр с тем же коэффициентом аппроксимации, что и эвристика Гонсалеса.[3] Как для задачи кластеризации минимального и максимального диаметра, так и для метрики k-центровой задачи, эти приближения являются оптимальными: существование эвристики за полиномиальное время с любым постоянным отношением аппроксимации меньше 2 означало бы, что P = NP.[1][3]

Так же, как и для кластеризации, обход самого дальнего-первого может также использоваться в другом типе задачи размещения объектов, задаче максимального-минимального разброса объектов, в которой цель состоит в том, чтобы выбрать расположение объектов. k разные помещения, чтобы они находились как можно дальше друг от друга. Точнее, цель в этой задаче - выбрать k точки из заданного метрического пространства или заданного набора точек-кандидатов таким образом, чтобы максимизировать минимальное попарное расстояние между выбранными точками. Опять же, это можно приблизительно оценить, выбрав первый k точки дальнего-первого обхода. Если р обозначает расстояние до kth точка из всех предыдущих точек, то каждая точка метрического пространства или набора кандидатов находится в пределах расстояния р из первых k - 1 балл. Посредством принцип голубятни, некоторые две точки оптимального решения (каким бы оно ни было) должны находиться на расстоянии р того же пункта среди этих первых k - 1 выбранный балл, и (по неравенство треугольника ) на расстоянии 2р друг друга. Таким образом, эвристическое решение, полученное при обходе по принципу «дальше впереди», в два раза меньше оптимального.[4][5][6]

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

Алгоритмы

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

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

Для набора п баллов, этот алгоритм занимает О(п2) шаги и О(п2) дистанционные вычисления. Быстрее алгоритм аппроксимации, данный Хар-Пелед и Мендель (2006) применяется к любому подмножеству точек в метрическом пространстве с ограниченными удвоение размера, класс пространств, включающий Евклидовы пространства ограниченной размерности. Их алгоритм находит последовательность точек, в которой каждая последующая точка имеет расстояние в пределах 1 -ε коэффициент наибольшего расстояния от ранее выбранной точки, где ε можно выбрать любое положительное число. Это требует времени О(п бревноп).[23]

Для выбора точек из непрерывного пространства, например Евклидова плоскость вместо конечного набора точек-кандидатов эти методы не будут работать напрямую, потому что потребуется поддерживать бесконечное количество расстояний. Вместо этого каждую новую точку следует выбирать как центр самый большой пустой круг определяется ранее выбранным набором точек.[8] Этот центр всегда будет лежать на вершине Диаграмма Вороного из уже выбранных точек или в точке, где край диаграммы Вороного пересекает границу домена. В этой формулировке метод построения обходов дальше всех был также назван инкрементная вставка Вороного.[24] Это похоже на Алгоритм Рупперта за заключительный элемент создание сетки, но отличается выбором вершины Вороного для вставки на каждом шаге.[25]

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

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

Рекомендации

  1. ^ а б c Гонсалес, Т.Ф. (1985), "Кластеризация для минимизации максимального межкластерного расстояния", Теоретическая информатика, 38 (2–3): 293–306, Дои:10.1016/0304-3975(85)90224-5, МИСТЕР  0807927.
  2. ^ Rosenkrantz, D. J .; Stearns, R.E .; Льюис, П. М., II (1977), "Анализ нескольких эвристик для задачи коммивояжера", SIAM Журнал по вычислениям, 6 (3): 563–581, Дои:10.1137/0206041, МИСТЕР  0459617.
  3. ^ а б Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1985), "Наилучшая эвристика для k-центровая проблема », Математика исследования операций, 10 (2): 180–184, Дои:10.1287 / moor.10.2.180, МИСТЕР  0793876.
  4. ^ Уайт, Дуглас Дж. (1991), "Задача максимальной дисперсии", Журнал IMA по математике, применяемой в бизнесе и промышленности, 3 (2): 131–140 (1992), Дои:10.1093 / imaman / 3.2.131, МИСТЕР  1154657. Уайт считает, что использование обхода дальше всего в качестве эвристики для решения этой проблемы Штойер, Р. Э. (1986), Оптимизация по нескольким критериям: теория, вычисления и приложения, Нью-Йорк: Wiley.
  5. ^ Тамир, Ари (1991), "Неприятное расположение объекта на графиках", Журнал SIAM по дискретной математике, 4 (4): 550–567, Дои:10.1137/0404048, МИСТЕР  1129392.
  6. ^ Ravi, S. S .; Rosenkrantz, D. J .; Тайи, Г. К. (1994), "Эвристические и специальные алгоритмы для задач дисперсии", Исследование операций, 42 (2): 299–310, Дои:10.1287 / opre.42.2.299, JSTOR  171673.
  7. ^ Сян, З. (1997), "Квантование цветного изображения путем минимизации максимального межкластерного расстояния", Транзакции ACM на графике, 16 (3): 260–276, Дои:10.1145/256157.256159.
  8. ^ а б Эльдар, Ю .; Lindenbaum, M .; Порат, М .; Zeevi, Y. Y. (1997), "Стратегия самой дальней точки для прогрессивной выборки изображений", IEEE Transactions по обработке изображений, 6 (9): 1305–1315, Bibcode:1997ITIP .... 6.1305E, Дои:10.1109/83.623193.
  9. ^ Mazer, E .; Ahuactzin, J.M .; Бессьер, П. (1998), "Алгоритм клубка Ариадны", Журнал исследований искусственного интеллекта, 9: 295–316, Дои:10.1613 / jair.468.
  10. ^ Moenning, C .; Доджсон, Н. А. (2003), "Новый алгоритм упрощения облака точек", 3-я Международная конференция IASTED по визуализации, визуализации и обработке изображений.
  11. ^ Гоцман, Крейг; Аллебах, Ян П. (1996), «Границы и алгоритмы для экранов дизеринга» (PDF)в Rogowitz, Bernice E .; Аллебах, Ян П. (ред.), Человеческое зрение и электронное изображение, Proc. SPIE, 2657, стр. 483–492, Дои:10.1117/12.238746.
  12. ^ Shahidi, R .; Moloney, C .; Рампони, Г. (2004), "Дизайн масок самой дальней точки для полутонового изображения", Журнал EURASIP по прикладной обработке сигналов, 12: 1886–1898, Bibcode:2004EJASP2004 ... 45S, Дои:10.1155 / S1110865704403217.
  13. ^ Dasgupta, S .; Лонг, П. М. (2005), «Гарантии производительности для иерархической кластеризации», Журнал компьютерных и системных наук, 70 (4): 555–569, Дои:10.1016 / j.jcss.2004.10.006, МИСТЕР  2136964.
  14. ^ Lipman, Y .; Funkhouser, T. (2009), "Голосование Мёбиуса за поверхностное соответствие", Proc. ACM SIGGRAPH, стр. 72: 1–72: 12, Дои:10.1145/1576246.1531378.
  15. ^ Girdhar, Y .; Giguère, P .; Дудек, Г. (2012), «Автономная адаптивная подводная разведка с использованием тематического онлайн-моделирования» (PDF), Proc. Int. Symp. Экспериментальная робототехника.
  16. ^ Алтинисик, У .; Йилдирим, М .; Эркан, К. (2012), «Изоляция непредвиденных неисправностей датчика с использованием алгоритма дальнего первого обхода», Ind. Eng. Chem. Res., 51 (32): 10641–10648, Дои:10.1021 / ie201850k.
  17. ^ Бордевич, Магнус; Родриго, Аллен; Семпл, Чарльз (2008), «Выбор таксонов для сохранения или упорядочивания: желательные критерии и жадное решение», Систематическая биология, 57 (6): 825–834, Дои:10.1080/10635150802552831.
  18. ^ Фишер, Маршалл Л .; Джайкумар, Рамчандран (1981), "Обобщенная эвристика назначения для маршрутизации транспортных средств", Сети, 11 (2): 109–124, Дои:10.1002 / нетто.3230110205, МИСТЕР  0618209. Как цитирует Гейзенс, Филип; Голден, Брюс; Асад, Арджанг (1986), «Новая эвристика для определения размера и состава флота», в Галло, Джорджио; Санди, Клаудио (ред.), Netflow в Пизе, Математическое программирование, 26, Springer, стр. 233–236, Дои:10.1007 / bfb0121103.
  19. ^ Hase, Hayo (2000), «Новый метод выбора дополнительных сайтов для гомогенизации неоднородного сферического распределения точек», в Rummel, Reinhard; Древес, Германн; Босх, Вольфганг; и другие. (ред.), На пути к интегрированной глобальной системе геодезических наблюдений (IGGOS): Симпозиум IAG Секция II, Мюнхен, 5-9 октября 1998 г., плакаты - Сессия B, Международная ассоциация геодезических симпозиумов, Springer, стр. 180–183, Дои:10.1007/978-3-642-59745-9_35.
  20. ^ Виейра, Луис Филипе М .; Виейра, Маркос Аугусто М .; Руис, Линниер Беатрис; Лоурейро, Антонио А. Ф .; Сильва, Диогенес Сесилио; Фернандес, Антониу Отавио (2004), «Эффективный алгоритм развертывания сети дополнительных датчиков» (PDF), Proc. Brazilian Symp. Компьютерная сеть, стр. 3–14.
  21. ^ Лайне, Самули; Сарансаари, Ханну; Контканен, Янне; Лехтинен, Яакко; Айла, Тимо (2007), «Инкрементальное мгновенное излучение для непрямого освещения в реальном времени», Материалы 18-й Еврографической конференции по техникам рендеринга (EGSR'07), Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, стр. 277–286, Дои:10.2312 / EGWR / EGSR07 / 277-286, ISBN  978-3-905673-52-4.
  22. ^ Аббар, С .; Амер-Яхья, С .; Индик, П.; Mahabadi, S .; Варадараджан, К. Р. (2013), «Проблема разнообразных ближних соседей», Материалы 29-го ежегодного Симпозиум по вычислительной геометрии, стр. 207–214, Дои:10.1145/2462356.2462401.
  23. ^ Хар-Пелед, С.; Мендель, М. (2006), "Быстрое построение сетей в низкоразмерных метриках и их приложения", SIAM Журнал по вычислениям, 35 (5): 1148–1184, arXiv:cs / 0409057, Дои:10.1137 / S0097539704446281, МИСТЕР  2217141.
  24. ^ Терамото, Сачио; Асано, Тецуо; Като, Наоки; Дорр, Бенджамин, «Равномерное размещение точек в каждом случае», Операции IEICE по информации и системам, E89-D (8): 2348–2356, Bibcode:2006IEITI..89.2348T, Дои:10.1093 / ietisy / e89-d.8.2348.
  25. ^ Рупперт, Джим (1995), "Уточняющий алгоритм Делоне для создания качественной двумерной сетки", Журнал алгоритмов, 18 (3): 548–585, Дои:10.1006 / jagm.1995.1021.