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

Ответ 1

Проблема, которую вы описываете, эквивалентна проблеме идеального соответствия с минимальной стоимостью, которая может быть эффективно (и точно) решена с использованием Венгерского алгоритма. В задаче идеального соответствия минимальной стоимости у вас есть входной взвешенный двудольный граф, где два набора имеют одинаковый размер n, а каждое ребро имеет неотрицательную стоимость. Цель состоит в том, чтобы найти идеальное соответствие минимальной стоимости.

В вашем случае двудольный граф является бикликом. То есть каждая вершина в одном наборе связана с каждой вершиной в другом наборе, и стоимость ребра (i,j) равна (A[i] - B[i])^2 (где i соответствует индексу i в массив A и j соответствует индексу j в массиве B).

РЕДАКТИРОВАТЬ: Это не лучшее решение проблемы. Ivo Merchiers предложили лучшее решение с точки зрения эффективности и простоты. Причина, по которой я не удаляю свой ответ, заключается в том, что предложенное мной решение полезно для мер расстояния, к которым Ivo-решение не применимо (так как его подход работает с использованием свойства евклидова расстояния).

Ответ 2

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

Если B должен оставаться фиксированным, то вам просто нужно инвертировать перестановку, необходимую для сортировки B, и применить ее к отсортированной версии A.

Это решение предполагает, что вы хотите найти только перестановку, а не самую простую перестановку (поскольку сортировка и сортировка по перестановкам не будут невероятно эффективными).

Доказательство: пусть S, T будет нашей парой массивов. Мы можем предположить, что S сортируется без потери общности, поскольку все, что имеет значение, это отображение между двумя наборами элементов.

Пусть T будет перестановкой, которая минимизирует расстояние между двумя массивами, и пусть d будет этим расстоянием.

Предположим, что T не отсортировано. Тогда существуют элементы i, j st T_i> T_j

S_i + k1 = S_j
T_i = T_j + k2
where k1,k2 > 0

Пусть x будет общим расстоянием всех элементов, кроме я и j.

d = x + (S_i - T_i)^2 + ((S_i + k1) - (T_i - k2))^2

Если мы поменяем местами порядок T_i и T_j, то наше новое расстояние будет:

d' = x + (S_i - (T_i - k2))^2 + ((S_i + k1) - T_i)^2

Таким образом: d - d '= 2 * k1 * k2, что противоречит нашему предположению, что T - это перестановка, минимизирующая расстояние, поэтому перестановка, которая делает это, должна быть отсортирована.

Сортировка двух массивов может быть выполнена в O (n log n), используя различные методы.

Ответ 3

Вы можете просто отсортировать A и B и сопоставить соответствующие элементы.

Представьте, что есть два элемента A, Ai и Aj, соответствующие Bi и Bj.

Вклад ошибки из этих совпадений:

(Ай-Би) ^ 2 + (Ай-Би) ^ 2

= Ai ^ 2 + Bi ^ 2 + Aj ^ 2 + Bj ^ 2 - 2 (AiBi + AjBj)

Лучше поменять местами спички или оставить их такими, какие они есть?

Ну, разница в ошибке, если мы поменяем их местами:

2 (AiBi + AjBj) - 2 (AiBj + AjBi)

~ AiBi - AiBj + AjBj - AjBi

= Ai (Би - Би) - Ай (Би - Би)

= (Ай - Ай) (Би - Би)

Таким образом, если A s и B s находятся в одном и том же порядке, этот продукт является положительным, и ошибка будет повышаться, если вы поменяете их местами. Если они не в том же порядке, этот продукт отрицательный, и ошибка будет сброшена, если вы поменяете их местами.

Если вы неоднократно меняете местами любые пары, которые вышли из строя, до тех пор, пока таких пар не будет, ваша ошибка будет продолжать снижаться, и вы в конечном итоге будете иметь n- е наибольшее A, совпадающее с n- м наибольшим B на всем протяжении массив.

Таким образом, их сортировка и сопоставление оптимальны и, конечно, быстрее, чем по венгерскому алгоритму.

Ответ 4

Построить двудольный граф из векторов. Найти минимальный вес идеального соответствия на этом графике.

Как построить график.

1. Пусть A, B две части графа. Каждый с n узлами.
2. Соедините i в A с j в B с ребром веса abs(A[i] - B[j]).

Я считаю, что это может быть сделано в O(n^2).

См. Http://www.cse.iitd.ernet.in/~naveen/courses/CSL851/lec4.pdf.

Если каждое число в A имеет только одно ближайшее число в B то вы можете сделать это в O(n \log n). Это, вероятно, может иметь место, так как у вас есть реальные цифры.

Как?

1. Сортировать A O(n \log n)
2. Двоичный поиск ближайшего числа для каждого числа в B. O(n \log n).

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