logo标签列表

给定两个数组，找到使两个数组之间距离最接近的排列组合。

algorithm
52
假设我有两个长度相同的数组，称为A和B。这两个数组包含实数值。我们将两个数组之间的距离定义为均方距离。 dist（A，B）= sqrt（sum（（A-B）^ 2）） 我想找到使得A的排列距离B最小的排列。天真的方法是尝试A的每个排列并记录最小距离。但是，这种方法的复杂度为O（n！）。是否存在复杂度小于O（n！）的算法？
这是用于什么目的的？你需要最佳解决方案还是只需要一个足够好的解决方案？ - Yair Halberstadt
你能举个例子，详细说明一下问题，并给出你期望的答案吗？ - Aldert
我不确定我是否完全理解您所描述的问题，听起来像是您想尝试对坐标向量的所有可能排列进行计算，以使用“勾股定理”找出提供最短距离的组合。因此，您基本上正在构建所有可能组合的树形结构，为此，您需要考虑您要追求的精度程度或者它是否需要精确，您需要多少结果（可以很多），以及算法的速度？考虑到这一点，您可以做的是修剪您的树形结构；再次强调，它需要多么精确？ - Ordiel
因为另一个答案有更好的参考资料，我想。我总是欣赏好的参考资料。 - Wang Duo
5个回答
42
你可以对A和B进行排序。在这种情况下，欧几里得距离是最小的。
如果B必须保持不变，则只需反转对B进行排序所需的置换，并将其应用于A的排序版本即可。
此解决方案假定您只想找到一个排列，而不是最简单的排列（因为通过排列进行排序和取消排序将不会非常有效）。
证明： 让S，T是我们的一对数组。 我们可以假设S已经排序，没有任何损失，因为所有的事情都是元素之间的映射关系。
让T是使两个数组之间距离最小的置换，d是该距离。
假设T不被排序。那么存在元素i，j，使得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)时间内对两个数组进行排序。
3
如果这种方法是错误的，我很乐意听取反例，因为我不确定其中的问题所在，也很乐意学习新知识。 - Ivo Merchiers
4
数学上是成立的。我没有时间写证明，但大致思路如下：如果最佳解未排序，则找到两个索引 x 和 y，使得 A[x] < A[y] 并且 B[x] > B[y]。交换 A 中的这两个位置，就可以得到更优的解。 - Yair Halberstadt
2
如果这个可以被证明是正确的，那么它比接受答案中的匈牙利算法更优秀；那个算法的时间复杂度是O(n^3)。 - Ray
2
Yair的想法可行。我已经提交了一份类似的带有证明的编辑。 - Ray
3
请注意，这只适用于欧几里得距离，但不一定适用于其他距离度量方式。如果以 sqrt(A[i] - B[i]) 作为距离度量方式并选取元素 [1 4] , [4 5]，排序会产生错误的结果 sqrt(3) + sqrt(1) ，其比理想排列的误差 sqrt(4) + sqrt(0) 更大。 - yar
显示剩余2条评论
40
你描述的问题等同于最小代价完美匹配问题，可以使用匈牙利算法高效（且精确地）解决。在最小代价完美匹配问题中，输入加权二分图具有两个大小为n的集合，每条边都有非负成本。目标是找到最小成本的完美匹配。
在你的情况下，二分图是一个双全图。也就是说，一组中的每个顶点都连接到另一组中的每个顶点，边（i，j）的成本为（A [i] - B [i]）^ 2 （其中i对应于数组A中的索引i，j对应于数组B中的索引j）。 编辑： 这不是问题的最佳解决方案。Ivo Merchiers提出了更好的解决方案，在效率和简单性方面都更好。我没有删除我的答案的原因是，我的建议解决方案对于Ivo的解决方案不适用的距离度量是有价值的（因为他的方法通过利用欧几里得距离的属性来工作）。
虽然正确，但对于这个问题来说效率不高。请参考Ivo的解决方案。 - Dave
@Dave，感谢您的评论。我已经添加了对Ivo更好的解决方案的引用。 - snakile
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 和 B 按相同顺序排列，则这个乘积为正数，如果您交换它们，则误差将增加。 如果它们不按相同顺序排列，则该乘积为负数，并且如果您交换它们，则误差会降低。
如果您反复交换任何不按顺序排列的对，直到没有这样的对，则您的误差将继续降低，并且您最终将得到第n大的 A 与整个数组中的第n大的 B 相匹配。

仅仅对它们进行排序并匹配是最优的，当然这比匈牙利算法要快得多。

7
构建一个二分图。从向量中找到最小权重的完美匹配。
如何构建图：
1. 设A，B是图的两个部分，每个部分有n个节点。 2. 将A中的i与B中的j连接，边的权重为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) 如果数字来自现实世界并具有一定的随机性，则每对数字之间的差异可能是独特的。您可以通过对输入向量进行实验来验证是否存在这种情况。然后问题就变得容易解决了！
1
谢谢，你的答案是正确的！但是@snakile早些时候回复了一些好的参考资料，所以我决定接受他的答案。 - Wang Duo
1

我需要在Python中实现这个功能，所以我将分享基于Ivo Merchiers答案的解决方案：

target = [12, 14, 4512, 123, 4412]
source = [12, 14, 120, 4413, 5512]

permutationToSortTarget = [i[0] for i in sorted(enumerate(target), key=lambda x: x[1])] # get permutation that would sort target
permutationNeeded = [i[0] for i in sorted(enumerate(permutationToSortTarget), key=lambda x: x[1])] # get needed permutation

source.sort()
source = [source[i] for i in permutationNeeded] # apply permutation to sorted source
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接