最小化点对中的距离总和

Question

我在二维网格上有很多点.我想将点分组成对,同时最小化对之间的欧几里德距离的总和.

例:

Given the points: 

p1: (1,1)
p2: (5,5)
p3: (1,3)
p4: (6,6)

Best solution: 
pair1 = (p1,p3), distance = 2
pair2 = (p2,p4), distance = 1
Minimized total distance: 1+2 = 3

我怀疑这个问题可以通过匈牙利算法的变体解决吗？

解决问题的最快方法是什么？

(小评论:我总是应该少于12分.)

Answer 1

您要解决的问题类似于通过完全连接的（网状）网络的最短路径，在该路径中，您不允许多次访问每个顶点/节点，并且您不必担心连接最小对。

当使用图论，度量空间和计算几何的其他结果的技术时，此问题是可以解决的。

这个问题类似于Wiki文章中关于“ 最近对点” 问题，并且该文章提供了有关Voroni图和Delaunay三角剖分的有用见解，以及使用递归除法和征服算法来解决该问题。

请注意，求解最接近的点对并不是解决方案，因为您可能在一行中有四个点（A，B，C，D），其中d（B，C）最小，但是您也会得到d（ A，D），并且总和将大于d（A，B）和d（C，D）。

这个stackoverflow问题说明了如何找到两点之间的最短距离，并提供了一个有用的提示，可以在比较距离时跳过计算平方根的过程。答案建议使用分而治之的方法（线性），但请注意，同时拆分X和Y坐标可能会更适当地进行分区。

这个数学堆栈交换问题解决了一个类似的问题，并建议使用Prim算法，Kruskal算法，或者注意这是Traveling Salesman问题的特例，它是NP-hard。

我的方法是使用贪心算法解决您的问题（配对最接近的点），以计算最小生成树，然后从生成树中删除1/2的边（保留断开的对）。可能使用第二个（变体）贪婪算法。

Answer 2

对于 12 个或更少的点（大约 10000 个或更少，如评论中指出的），可能的配对非常少，您可以通过强力检查所有配对，即使使用此解决方案，您也可以用 12 个或更少的点每秒解决大约 10000 个问题在现代个人计算机上。如果您想要更快的解决方案，您可以按顺序枚举每个点的最近邻居，然后仅检查每个点使用的最近邻居的最小配对。在最坏的情况下，我不认为这会带来加速，但例如，如果你的 12 个点有 6 对非常接近的点（其中不成对的点相距很远），那么你会很快找到解决方案，因为相对于最近邻居的最小配对会将每个点与其第一个最近邻居匹配在一起。