У меня есть два набора, A и B. Наборы состоят из N точек измерения и упорядочены (N‹10). Мне нужно найти ближайшую часть B к A. Допустим, ближайшая часть - B1. Количество точек в B1 должно быть таким же, как и в A, а сумма расстояний от всех точек в B1 до A должна быть минимальной.
Я проверил k-d дерево. Это только помогает найти ближайшую точку в наборе. Итак, существует ли алгоритм для быстрого поиска ближайшего диапазона?
Спасибо.
Я полагаю, что вам просто нужен алгоритм поиска n ближайших соседей, который является простым расширением алгоритма ближайшего соседа. Запустите это для каждой точки в наборе A и минимизируйте общую сумму.
Алгоритм упоминается в эта статья ("Вводный курс по kd-деревьям"). Расширение более чем на одного ближайшего соседа упоминается лишь кратко, но должно быть достаточно ясно. Это статья, из которой я успешно реализовал модифицированный алгоритм.
Эталонную реализацию на C# можно найти здесь, она прокомментирована и содержит соответствующие модульные тесты. Должно быть легко адаптироваться к императивному языку по вашему выбору.
