0

Дано n-мерное векторное пространство. В пространстве имеются вектора напр.

[ 0.02182626 -0.03014402 -0.06414173 -0.01990378  0.00629869...]

Как найти некоторое заданное число ближайших векторов(точек) к выбранному при большом количестве векторов(1кк+) и n>1000.

Банальнейшим решением является перебор расстояний до всех векторов, по формуле расстояния между точками, и нахождение минимального значения. Формула для расстояния между точками в n-мерном пространстве:

sqrt((a1 - b1)2 + (a2 - b2)2 + ... + (an - bn)2), где sqrt - квадратный корень, a и b - координаты точек, 2 -ка после скобок- возведение в квадрат

Такое решение, вероятно, является медленным. Возможно кто то подскажет решение на одном из указанных языков. Важна, именно, скорость нахождения ближайших соседей.

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

14
  • дак вероятно, или медленным?
    – teran
    19 сен 2018 в 10:45
  • 1
    можете, наверное, начало координат перенести в искомую точку, и сравнить не длину вектора, а сумму модулей координат. в целом это избавит от возведения в квадрат и вычисления корня, но сомнительно, что это ускорит процесс.
    – teran
    19 сен 2018 в 10:51
  • 1
    Квадраты это обобщение Теоремы Пифагора для n-мерного пространства. В 2-мерном sqrt((a1 - b1)2 + (a2 - b2)2). Где (a1 - b1) и (a2 - b2) катеты. Формула (9.7) studopedia.ru/…
    – Hertz
    19 сен 2018 в 11:10
  • 1
    @MaxU в целом без разницы, когда координаты вычитать - при переносе или при вычислении дистанции(ее эквивалента), вычесть то все равно надо, хоть так хоть эдак
    – teran
    19 сен 2018 в 13:51
  • 1
    Для сравнения дистанций не нужно извлекать корень, достаточно сравнивать квадраты расстояний. Правда, для многомерного случая это особо не поможет. И для одноразового поиска ближайших соседей конкретной точки метода быстрее не существует. Если на наборе точек нужно много раз искать - то есть варианты, например, kd-tree, однако здесь вступит в дело т.н. "проклятие размерности"
    – MBo
    19 сен 2018 в 14:41

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.