Всегда думал, что задачи типа "дано 100....000 точек, для каждой найти ближайшую" - это олимпиадная блажь, на практике никому не нужная. Оказалось, что понадобилась, причем как раз на работе, причем в усложненном виде.
Задача такая. Дано порядка 10000 точек в N-мерном (N небольшое - не более 10) единичном кубике, для каждой нужно найти K (K < 100) ближайших. Строгих ограничений, понятно, нет, но хотелось бы, чтобы на обычном компьютере это укладывалось в несколько секунд.
Буду рад любым идеям как это можно решать хотя бы приближенно. Заранее спасибо за советы.
UPD: оптимизированное решение "в лоб" работает порядка минуты. Нужно ускорить его хотя бы в несколько десятков раз.
UPD^2: после прочтения комментариев и обдумывания, пришел к выводу, что оптимальным по "сложность написания/качество" будет следующий алгоритм: создаем N списков точек, отсортированных по различным измерениям, и перебираем для заданной только точки, входящие в 2К ближайших по какому-либо измерению.
Как на счет квадро (или в данном случае 2^N-ро) - дерева? Спускаемся до тех пор пока в данном Н-мерном кубике не меньше К^3\2 точек, запомниаем расстояния, и потом пытаемся еще проверить в кубиках, близжайших к данному. Или, к примеру, обрабатываем все К точек по одному - оцениваем, на каком расстоянии находятся точки данного куба (минимум и максимум) от нашей, углубляемся если максимум больше текущего расстояния до И-той точки.
Аналогично можно искать кратчайшую точку к фиксированной - сортируем относительно случайной удалённой и рассматриваем ближайшие к ней сто точек в порядке сортировки. Мне кажется, тут схожая эвристика тоже должна работать. Вполне можно натыкать сколько-нибудь случайных точек, потом выбирать из них рандомную, сортировать относительно неё и брать тысячу ближайших к нужной точке в порядке нашей сортировки. Можете пострессить с тупым решением, чтобы оценить эффективность.
М-да... Я в 11-м классе это использовал для своей реализации игрушки Life на бесконечном поле. И до сих пор думал что это гениальная идея. А она оказывается банальная... ;-)
Метод, спору нет, не является точным. ;-)
А теперь, когда всё выяснено... Не поделитесь ли, откуда на практике такая задача возникла? (если это не связано с реализацией какого-нибудь советника для какого-нибудь трейдера) Заранее спасибо!
UPD: Вот зло, точно помню что коммент цеплял ко всему посту, а не к другому комменту! Всем сорри.
UPD: А вообще "единичный кубик в N-мерном пространстве" это видимо область куда значения N-критериев объекта/факта какого-то попадают. Так что главный вопрос - зачем нужно для каждой из точек искать ближайшие (вместо, скажем, кластеризации и т.п.)