寻找最优循环排列，使得两个有序点列表之间的平均距离最小化。

Question

寻找最优循环排列，使得两个有序点列表之间的平均距离最小化。

algorithmoptimization

4

给定两个有序的n个点集A和B，如何找到最小化点之间平均距离（使用您选择的距离）的最佳循环置换。

换句话说，如何算法地找到k，使得sum(||A[i] - B[(i + k) % n||)最小，其中0 <= k < n？（我省略了除以n，因为我相信最小化总距离应该会产生相同的结果）。

一个额外的要求是，该算法应该可用于N维空间，因此我不能只对数组进行排序。

我显然可以计算每个成对距离，但这将产生O(n^2)（n x n成对距离计算+ n累加）复杂度，这是次优的（[编辑]我的意思是，我希望能够比暴力更好）。

应用：其中一个应用是在图形学中，我希望将一个形状的每个点映射到另一个形状的一个点，而不创建交叉边缘。请参见下面的绘图，我们将红色形状的每个点映射到蓝色形状上的一个点。

- Niels

我专门在三维欧几里得空间中工作，但我想算法不会因为你使用的范数而改变太多，对吗？范数就是范数。 - Niels

为什么排列必须是“循环”的要求？例如，如果您上面的二维图片中的点按不同顺序编号，或者形状是三维的，会发生什么？ - stf

更一般地说，独立于我的实现，如果您看一下图纸，现在假设您将点1映射到k+1，将点2映射到k，无论如何定义边缘，您现在都会有交叉的边缘。 - Niels

顺便提一下，如果我可以在不使用循环缓冲区的情况下寻找最佳分配，我可以使用匈牙利算法或者一些图匹配。但是额外的限制让我感到烦恼。 - Niels

那么，我们现在只是在谈论简单闭合多边形链吗？你只是想将两个这样的链匹配在一起吗？ - stf

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

我有两个想法。

如果你愿意优化距离的平方和，那么基于快速卷积的O(n log n)时间算法是可行的。修改后的目标允许我们分别找到每个可能旋转的坐标的贡献，然后逐元素求和并选择最佳结果。

要解决一维的简化问题：我们希望

sum_i (A[i] - B[(i+k) mod n])**2

对于每个k。进行一些代数运算：

sum_i (A[i] - B[(i+k) mod n])**2 =
sum_i (A[i]**2 - 2*A[i]*B[(i+k) mod n] + B[(i+k) mod n]**2) =
sum_i A[i]**2 + sum_i B[i]**2 - 2*sum_i (A[i]*B[(i+k) mod n]).

对于所有的 k，前两个项都相同，所以只需计算它们。对于所有的 k，第三项的向量可以快速批量计算，作为一个常数乘以 A 卷积反转 B。

我的第二个想法是递归启发式。如果 n 很小，就直接暴力求解。否则，通过计算每个列表中相邻点对的中点来生成一个较小的实例。递归地对齐这些点。然后将启发式旋转乘以二，并将其与旋转一次向上和向下的结果进行比较。在恒定维度下，这会产生像 T(n) = T(n/2) + O(n) 这样的递归关系，其时间复杂度为 O(n)。