问与答 算法-给定两个数组,找到给出两个数组之间最接近距离的排列

hawthorne · 2020-03-08 13:47:12 · 热度: 97

假设我有两个长度为A的数组,分别名为BA

这两个数组包含实数值。我们将两个数组之间的距离定义为均方距离。

2) )

我想找到A的置换,它将最小距离赋予B。天真的方法是尝试A的每个排列并记录最小距离。 但是,此方法的复杂度为O(n!)。

是否有一种算法的复杂度小于O(n!)?

猜你喜欢:
共收到 4 条回复
andres #1 · 2020-03-08 13:47:12

您可以同时对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)中对两个数组进行排序。

vitor #2 · 2020-03-08 13:47:14

您描述的问题等同于最小成本完美匹配问题,可以使用匈牙利算法有效(准确)解决问题。 在“最小成本完美匹配问题”中,您有一个输入加权二分图,其中两组具有相同的大小n,每个边的成本均为非负数。 目标是找到最低成本的完美匹配。

在您的情况下,二部图是双斜图。 即,一组中的每个顶点都连接到另一组中的每个顶点,并且边(i,j)的成本为(A[i] - B[i])^2(其中i对应于数组A中的索引i),而27556878683697326326对应于数组B中的索引j)。

编辑:这不是解决该问题的最佳方法。 Ivo Merchiers在效率和简单性方面都提出了更好的解决方案。 我之所以不删除答案,是因为我建议的解决方案对于不适用Ivo解决方案的距离度量非常有价值(因为他的方法通过利用欧几里得距离的性质而起作用)。

quinton #3 · 2020-03-08 13:47:15

您可以仅对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直到整个数组 。

因此,仅对其进行排序和匹配是最佳的,当然,它比匈牙利算法要快得多。

sanjeev #4 · 2020-03-08 13:47:17

从向量构造二部图。 在此图中找到最小的重量完美匹配。

如何构造图。

  1. O(n \log n)B是图表的两个部分。 每个节点都有O(n \log n)节点。
  2. 使用重量边缘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)中进行此操作。可能是这种情况,因为您拥有实数。

怎么样?

  1. 排序O(n \log n)
  2. 二进制搜索B.O(n \log n)中每个数字的最接近数字。

如果这些数字来自真实世界,并且甚至具有一些随机性,那么每对数字之间的差异可能是唯一的。 您可以通过对输入向量进行实验来验证是否是这种情况。 然后问题就容易解决了!

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册