Задача поиска ближайшего соседа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Другие значения этого понятия см. в статье ближайший сосед

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

Приложения[править | править исходный текст]

Задача поиска ближайшего соседа встречается во множестве приложений, например в областях:

Модели данных[править | править исходный текст]

Перед решением прикладной задачи, необходимо выбрать форму представления объектов и функцию близости. В большинстве случаев, объекты представляются в виде многомерных векторов, а в качестве функции близости используется скалярное произведение векторов, но могут быть и другие формы представления данных, например:

Виды целей[править | править исходный текст]

Помимо классической задачи отыскания ближайшей к заданной точке, могут быть поставлены задачи:

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

Алгоритмы[править | править исходный текст]

Разбиение пространства[править | править исходный текст]

Обратный индекс[править | править исходный текст]

Метод редких точек


См. также[править | править исходный текст]

Ссылки[править | править исходный текст]