Эффективная реализация поиска ближайшего соседа

Я пытаюсь реализовать эффективный алгоритм для решения проблемы поиска ближайшего соседа.

Я читал руководства о некоторых структурах данных, которые поддерживают операции для такого рода проблем (например, R-tree, cover tree и т. Д.), Но все они сложно реализовать.

Также я не могу найти образец исходного кода для этих структур данных. Я знаю C ++ и пытаюсь решить эту проблему на этом языке.

В идеале мне нужны ссылки, описывающие, как реализовать эти структуры данных с использованием исходного кода.


c++ tree nearest-neighbor
person dato datuashvili    schedule 06.04.2012    source источник
comment
Какова размерность ваших данных? Для двухмерных точечных данных я бы рекомендовал использовать Kd-дерево. Это легко реализовать. Для других типов данных / геометрии вы можете посмотреть R-деревья (boost 1.54 поддерживает индексы rtree)   -  person gvd    schedule 03.11.2013

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете попробовать алгоритм поиска по строкам, чтобы найти ближайшую пару точек: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep.

person Gigamegs    schedule 06.04.2012

arrow_upward
14
arrow_downward

Есть несколько хороших вариантов библиотек быстрого поиска ближайшего соседа.

  • ANN, которая основана на работе Маунта и Арьи. Эта работа задокументирована в статье С. Арья и Д. М. Маунта. «Приблизительные запросы ближайшего соседа в фиксированных размерах». В Proc. 4-й симпозиум ACM-SIAM. Дискретные алгоритмы, страницы 271–280, 1993.

  • FLANN, основанный на работе Мариуса Муджи и Co. Есть статья Мариуса Муджи и Дэвида Дж. Лоу, «Быстрые приближенные ближайшие соседи с автоматической конфигурацией алгоритма» на Международной конференции по теории и приложениям компьютерного зрения (VISAPP'09), 2009 г. Код для FLANN доступен на github.

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

Изменить в ответ на комментарий

Обе эти библиотеки содержат обширную документацию и примеры.

Пример кода для ИНС доступен в Руководстве, в разделе 2.1.4

Пример кода для FLANN доступен в каталоге примеров репозитория FLANN, например / examples /flann_examples.c

person Andrew Walker    schedule 06.04.2012
comment
как его использовать, если, например, у меня есть (x1, y1) (x2, y2) ... (xn, yn)? - person dato datuashvili; 06.04.2012
comment
@dato - ответ был обновлен и теперь включает ссылки на авторитетные примеры из документации каждого проекта. - person Andrew Walker; 06.04.2012
comment
мне нужна установка да библиотека FLANN? - person dato datuashvili; 06.04.2012
comment
Да, возможно. Использование FLANN (или ANN) требует, чтобы вы сделали соответствующие файлы доступными в ваших путях включения и библиотеки, точно так же, как и с любой другой нетривиальной библиотекой C ++. - person Andrew Walker; 06.04.2012
comment
@AndrewWalker Не могли бы вы добавить к ответу nanoflann? Это форк от FLANN и, видимо, быстрее. Это действительно удобная библиотека только для заголовков C ++ 11. Спасибо и привет - person krjw; 16.10.2018