Всегда думал, что задачи типа "дано 100....000 точек, для каждой найти ближайшую" - это олимпиадная блажь, на практике никому не нужная. Оказалось, что понадобилась, причем как раз на работе, причем в усложненном виде.
Задача такая. Дано порядка 10000 точек в N-мерном (N небольшое - не более 10) единичном кубике, для каждой нужно найти K (K < 100) ближайших. Строгих ограничений, понятно, нет, но хотелось бы, чтобы на обычном компьютере это укладывалось в несколько секунд.
Буду рад любым идеям как это можно решать хотя бы приближенно. Заранее спасибо за советы.
UPD: оптимизированное решение "в лоб" работает порядка минуты. Нужно ускорить его хотя бы в несколько десятков раз.
UPD^2: после прочтения комментариев и обдумывания, пришел к выводу, что оптимальным по "сложность написания/качество" будет следующий алгоритм: создаем N списков точек, отсортированных по различным измерениям, и перебираем для заданной только точки, входящие в 2К ближайших по какому-либо измерению.
Comments (0)
