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

Question

Скажем, у меня есть две матрицы точек, A и B, которые содержат координаты точки. Я хочу найти пары точек, которые минимизируют сумму евклидовых разностей между парами точек.

Например, в одномерном случае у меня есть: A = [4 1 1,5]; B = [4 1,2 0]; Если алгоритм сначала сопоставляет ближайшие пары (например, this one), это может вернуть пары [4 4], [1 1,2], [1,5 0]. Это дало бы общую разницу в 1,5 + 0,2 + 0 = 1,7.

Я ищу решение, которое минимизировало бы общую разницу между парами, что дает решение [4 4], [1 0], [1,5 1,2] для общей разницы .3 + 1 + 0 = 1.3.

Это для 10k-100k точек в 3D.

Спасибо за вашу помощь!

Answer 1

Спасибо всем за ваши комментарии! И, в частности, @jodag для определения этой проблемы как задачи назначения, предоставления венгерского алгоритма в качестве решения и предоставления ссылки на реализацию Matlab .

Кажется, это работает, по крайней мере, для небольшого числа частиц. Если я застряну, я попытаюсь разделить область поиска.

Answer 2

Я не знаю, нужен ли вам ответ, ограниченный Matlab (потому что я не видел ни одной функции Matlab для выполнения пространственного индекса), но здесь идет речь.

Вы можете использовать https://www.boost.org/doc/libs/1_68_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html для «пространственного индексации ваших узлов» (https://en.wikipedia.org/wiki/Spatial_database#Spatial_index)

Цель состоит в том, чтобы иметь возможность искать узел шкафа в O (log (N)) N, являющемся числом узлов

Предположим, у вас есть два набора A и B, каждый из которых содержит N узлов

индексирование A и B стоит O (N log (N)) и O (N log (N))

выбирая точку i в A, которую вы ищете в RTree (B), вы находите точку j. store d1 (расстояние между i и j) (стоимость поиска O (log (N))

выбирая точку j в B, вы ищете в RTree (A), если вы найдете точку i, тогда вы получите совпадение [i в A с j в B], если вы получите узел k, то рассчитайте расстояние d2

если d2

сделать это для всех N точек

общая стоимость чего-то в O (N log (N))