假设我有两个长度相同的数组n,名为A和B.
这两个数组包含实际值.我们将两个数组之间的距离定义为均方距离.
dist(A,B) = sqrt( sum((A - B)2) )
我想找到A那个给出最小距离的排列B.天真的方法是尝试每个排列A并记录最小距离.然而,这种方法具有复杂性O(n!).
是否存在复杂度小于O(n!)的算法？
Ivo*_*ers 41
您可以对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是除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是最小化距离的排列相矛盾,因此必须对这样做的排列进行排序.
可以使用各种方法在O(n log n)中对两个阵列进行排序.
sna*_*ile 35
您描述的问题等同于最小成本完美匹配问题,该问题可以使用匈牙利算法有效(并且准确地)解决.在最小成本完美匹配问题中,您有一个输入加权二分图,其中两个集具有相同的大小n,并且每个边具有非负成本.目标是找到最低成本的完美匹配.
在您的情况下,二分图是双曲线.也就是说,一组中的每个顶点都连接到另一组中的每个顶点,并且边的成本(i,j)是(A[i] - B[i])^2(其中i对应i于数组A j中的索引并且对应j于数组B中的索引).
编辑: 这不是解决问题的最佳方案.Ivo Merchiers 在效率和简单性方面提出了更好的解决方案.我没有删除我的答案的原因是因为我建议的解决方案对于Ivo的解决方案不适用的距离测量是有价值的(因为他的方法通过利用欧几里德距离的属性来工作).
Mat*_*ans 11
您只需对A和B进行排序并匹配相应的元素即可.
想象一下,有两个元素A,Ai和Aj,对应于Bi和Bj.
这些匹配的错误贡献是:
(Ai-Bi)^ 2 +(Aj-Bj)^ 2
= Ai ^ 2 + Bi ^ 2 + Aj ^ 2 + Bj ^ 2 - 2(AiBi + AjBj)
交换比赛或保持比赛方式更好吗？
那么,如果我们交换它们的错误差异是:
2(AiBi + AjBj) - 2(AiBj + AjBi)
~AiBi - AiBj + AjBj - AjBi
= Ai(Bi - Bj) - Aj(Bi - Bj)
=(Ai - Aj)(Bi - Bj)
因此,如果A s和B s的顺序相同,则此产品为正数,如果交换它们,错误将会增加.如果它们的顺序不同,则此产品为负数,如果更换它们,错误将会减少.
如果您反复交换是不按顺序,直到有没有这样对任何对您的错误将继续下去,你会用的最终ñ个最大的一个与匹配了Ñ个最大的乙一路过关斩将数组.
只需对它们进行排序并将它们进行匹配就是最佳选择,当然它比匈牙利算法更快.
从向量构造二分图.在此图中找到最小权重完美匹配.
如何构建图形.
A,B成为图的两个部分.每个都有n节点.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).这可能是因为你有实数.
怎么样？
O(n \log n) O(n \log n).如果这些数字来自现实世界并且对它们有一点点随机性,那么每对数字之间的差异可能是唯一的.您可以通过在输入向量上运行实验来验证是否是这种情况.然后问题就变得容易解决了!