假设我有两个长度为A的数组，分别名为B和A。
这两个数组包含实数值。我们将两个数组之间的距离定义为均方距离。
2) )
我想找到A的置换，它将最小距离赋予B。天真的方法是尝试A的每个排列并记录最小距离。 但是，此方法的复杂度为O（n！）。
是否有一种算法的复杂度小于O（n！）？
猜你喜欢:
您可以同时对A和B进行排序。在这种情况下，欧几里得距离很小。
如果B必须保持固定，那么您只需要反转排序B所需的排列并将其应用于A的排序版本。
此解决方案确实假定您只想找到一个排列，而不是最简单的排列（因为通过排列进行排序和取消排序将不会非常有效。）
证明：令S，T为我们的一对数组。我们可以假设S被排序而不失一般性，因为所有这些重要的是两组元素之间的映射。
令T为使两个数组之间的距离最小的排列，并以d为该距离。
假设T未排序。 然后存在元素i，js.t。 T_i> T_j
S_i + k1 = S_j
T_i = T_j + k2
where k1,k2 > 0
令x为除i和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相矛盾，即T是使距离最小的排列，因此必须对排列进行排序。
可以使用多种方法在O（n log n）中对两个数组进行排序。
您描述的问题等同于最小成本完美匹配问题，可以使用匈牙利算法有效（准确）解决问题。 在“最小成本完美匹配问题”中，您有一个输入加权二分图，其中两组具有相同的大小n，每个边的成本均为非负数。 目标是找到最低成本的完美匹配。
在您的情况下，二部图是双斜图。 即，一组中的每个顶点都连接到另一组中的每个顶点，并且边(i,j)的成本为(A[i] - B[i])^2（其中i对应于数组A中的索引i），而27556878683697326326对应于数组B中的索引j）。
编辑：这不是解决该问题的最佳方法。 Ivo Merchiers在效率和简单性方面都提出了更好的解决方案。 我之所以不删除答案，是因为我建议的解决方案对于不适用Ivo解决方案的距离度量非常有价值（因为他的方法通过利用欧几里得距离的性质而起作用）。
您可以仅对A和B进行排序并匹配相应的元素。
想象一下，有两个元素A，Ai和Aj，分别对应于Bi和Bj。
这些匹配项的错误贡献为：
（Ai-Bi）^ 2 +（Aj-Bj）^ 2
= Ai2 + A2 + Aj2 + Bj2-2（Ai + AjBj）
交换比赛还是让比赛保持原样更好？
好吧，如果我们交换它们，则错误的区别是：
2（Ai + AjBj）-2（Ai Bj + Ajbi）
〜Aibi-Ai Bj + AjBj-Ajbi
= AI(BI - BJ) - AJ(BI - BJ)
=（Ai-Aj）（Bi-Bj）
因此，如果As和B的顺序相同，则该乘积为正，如果交换它们，则错误将上升。 如果它们的顺序不同，则该乘积为负，如果您交换它们，该错误将消失。
如果您反复交换任何乱序的对，直到没有这样的对，您的错误将继续下降，最终您将得到第n个最大的A和第n个最大的B直到整个数组 。
因此，仅对其进行排序和匹配是最佳的，当然，它比匈牙利算法要快得多。
从向量构造二部图。 在此图中找到最小的重量完美匹配。
如何构造图。
- 令
O(n \log n)、B是图表的两个部分。 每个节点都有O(n \log n)节点。 - 使用重量边缘
abs(A[i] - B[j])将B中的O(n \log n)连接到B中的O(n \log n)。
我相信可以在O(n \log n)中完成。
参见[http://www.cse.iitd.ernet.in/~naveen/courses/CSL851/lec4.pdf]
如果O(n \log n)中的每个数字在B中只有一个最接近的数字，那么您可以在O(n \log n)中进行此操作。可能是这种情况，因为您拥有实数。
怎么样？
- 排序
O(n \log n) - 二进制搜索B.
O(n \log n)中每个数字的最接近数字。
如果这些数字来自真实世界，并且甚至具有一些随机性，那么每对数字之间的差异可能是唯一的。 您可以通过对输入向量进行实验来验证是否是这种情况。 然后问题就容易解决了！
