最小化点对间距离之和

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个点。)

- Sebastian Schmitz

---

你尝试过按照边长排序，贪心地选择最短的边，直到选出n/2条边吗？无论如何都不能找到全局最小值，但也许这个近似已经足够了？你有实时限制吗？12个点并不是很多，一个简单的回溯方法可能就足够了（如果计算只需执行一次）。 - Nico Schertler

只需检查10,395种组合，就可以得到12分。参见http://math.stackexchange.com/questions/35684/combination-of-splitting-elements-into-pairs。 - Lior Kogan

这正是最大权匹配问题，但你不需要多项式时间解决方案，因为n！足够小。 - Niklas B.

有关通用n，请参见A new implementation of a minimum cost perfect matching algorithm。 - Joseph O'Rourke

@NicoSchertler：是的，但是当4个点位于1、3、4、6时会失败，因为你会得到(3,4)和(1,6)这两对。由于这在我的程序中应该相当常见，我不想冒险。 - Sebastian Schmitz

Answer 1

你试图解决的问题类似于在完全连接（网状）网络中找到最短路径，其中不允许多次访问每个顶点/节点，而且你不关心连接最小对。使用图论、度量空间等计算几何学的技术可以解决这个问题。

这个问题类似于最近点对问题的维基百科文章，该文章提供了一些关于沃罗诺伊图和德劳内三角化的有用见解，以及使用递归分治算法来解决问题。请注意，解决最近点对问题并不是解决方案，因为你可能会有四个点（A、B、C、D）在一条直线上，其中d（B,C）最小，但然后你也会有 d（A,D），而且和会比d（A,B）和d（C,D）还大。

这个 stackoverflow问题 解释了如何找到两点之间的最短距离，并提供了一个有用的提示，可以在比较距离时跳过计算平方根。答案建议使用分治法（线性），但观察到分割X和Y坐标可能会更适当地划分。

这个 math stackexchange问题 解决了类似的问题，并建议使用Prim算法，Kruskal算法，或指出这是旅行商问题的特殊情况，该问题是NP-hard。

我的方法是使用贪心算法来计算最小生成树，然后从生成树中删除一半的边（留下不相连的点对），以解决您的问题（配对最近的点）。可能需要使用第二个（变种）贪心算法。

- ChuckCottrill

---

此外，仅仅修剪最小生成树并不能保证结果。对于某些情况，您将被迫创建单例，这取决于节点的度数。 - GregoirePelegrin

Answer 2

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

- user2566092