Меню Главная Случайная статья Настройки Задача поиска ближайшего соседа Материал из https://ru.wikipedia.org Другие значения этого понятия см. в статье ближайший сосед Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. Содержание 1 Приложения 2 Модели данных 3 Виды целей 4 Алгоритмы 4.1 Разбиение пространства 4.2 Обратный индекс 5 См. также 6 Ссылки Приложения Задача поиска ближайшего соседа встречается во множестве приложений, например в областях: Распознавание образов Классификация текстов Рекомендательные и экспертные системы Динамическое размещение рекламы в Интернете Модели данных Перед решением прикладной задачи, необходимо выбрать форму представления объектов и функцию близости. В большинстве случаев, объекты представляются в виде многомерных векторов, а в качестве функции близости используется скалярное произведение их разности, но могут быть и другие формы представления данных, например: Множества — размер пересечения множеств Строки — расстояние Левенштейна Граф — соответствие структур Виды целей Помимо классической задачи отыскания ближайшей к заданной точке, могут быть поставлены задачи: Найти приблизительных ближайших соседей (не обязательно наиболее близкого) Найти ближайшего соседа для группы элементов Найти несколько ближайших соседей Найти все пары элементов, расстояние между которыми меньше некоторого заданного Найти ближайших соседей в динамически меняющейся среде Алгоритмы Разбиение пространства Диаграммы Вороного KD-деревья BSP-деревья Деревья покрытий VP-деревья R-деревья Обратный индекс Метод редких точек См. также Метод k ближайших соседей Диаграммы Вороного Ссылки Yury Lifshits. Algorithms for Nearest Neighbors: Theoretical Aspects Могилко А. А. Параллельный алгоритм поиска ближайшей точки в радиусе