Блог

Учитывая 2 упорядоченных набора из n точек в каждом, A и B, как мне найти наилучшую круговую перестановку, которая минимизирует среднее попарное расстояние (используя расстояние по вашему выбору) между точками.

Другими словами, как мне алгоритмически найти k такое, чтобы оно минимизировалось sum(||A[i] - B[(i k) % n||) с 0 <= k < n помощью? (Я опустил деление на n , потому что минимизация общего расстояния должна дать тот же результат, что и среднее значение, которое я считаю).

Одним из дополнительных требований является то, что алгоритм должен использоваться в N-мерных пространствах, поэтому я не могу просто сортировать массивы.

Я мог бы, очевидно, вычислить каждое попарное расстояние, но это дало бы O (n ^ 2) (n x n попарное вычисление расстояния n накоплений) сложность, которая является неоптимальной ([править] Я имею в виду здесь, что я очень надеюсь, что можно добиться большего, чем грубая сила).

Применение: Одно приложение находится в графике, где я хочу сопоставить каждую точку фигуры с точкой другой формы без создания пересекающихся ребер. Смотрите рисунок ниже, где мы сопоставляем каждую точку красной фигуры с точкой на синей фигуре.

У меня есть две идеи.

Если вы хотите оптимизировать сумму квадратов расстояний, то существует алгоритм времени O (n log n), основанный на быстрой свертке. Модифицированная цель позволяет нам находить вклад каждой координаты отдельно для каждого возможного поворота. Затем мы суммируем по элементам и выбираем лучшее.

Чтобы решить уменьшенную задачу в 1D: мы хотим

 sum_i (A[i] - B[(i k) mod n])**2
 

для каждого k . Сделайте некоторую алгебру:

 sum_i (A[i] - B[(i k) mod n])**2 =
sum_i (A[i]**2 - 2*A[i]*B[(i k) mod n]   B[(i k) mod n]**2) =
sum_i A[i]**2   sum_i B[i]**2 - 2*sum_i (A[i]*B[(i k) mod n]).
 

Первые два члена одинаковы для всех k , поэтому просто вычислите их. Вектор третьих членов для всех k может быть быстро вычислен в объеме как постоянное время A , свернутое с обратным B .

Моя вторая идея — рекурсивная эвристика. Если n оно мало, просто перебирайте его. В противном случае создайте экземпляр меньшего размера, вычисляя среднюю точку каждой пары последовательных точек в каждом списке. Рекурсивно выровняйте их. Затем умножьте эвристическое вращение на два и сравните его с поворотами на один вверх и один вниз от него. При постоянных измерениях это приводит к повторению типа T (n) = T (n / 2) O (n), что равно O (n).