我有一个n点集的集合，其中每个点集最多包含m个点。
我想从每个点集中选择一个点，以便得到的点选择尽可能靠近。（其中“接近度”有一个合理的定义，例如与所选点集的质心的距离平方和。）
例如，输入集合可以是：
Point Set A: [(2, 1), (1, 2), (6, 5)]
Point Set B: [(1, 1), (7, 3)]
Point Set C: [(3, 7), (5, 3)]
我想选择三个点，每个点集中一个，这些点最接近。在此示例中，左下角的三个点最接近，但它们不包括来自 C 的点。这里的解决方案是右侧的点：(6, 5)、(7, 3) 和(5, 3)。它们聚集在 (6, 3⅔) 处的质心周围。
蛮力算法尝试从集合中点的所有可能组合并跟踪“接近”函数的最小值（即O(m^n)算法），但我想知道是否有更有效的缩放n和m的大值的方式——如果不是在最坏的情况下，那么至少对于大多数输入。
更新：这些点将具有实际值作为坐标；上面使用整数来简化示例。
首先，我们可以考虑对蛮力算法进行改进。
O(m^n)是一个巨大的数字！我们如何增强这种搜索？您不是在搜索保证最小值的集合的全球覆盖范围。此外，每组的一个点需要在解决方案中。你是新的蛮力算法看起来像这样：
对于 S0 中的每个点p，在S1中找到离 p 最近的点... S ( n-1)
该算法的计算复杂度为O(m n m)
我们可以进一步改进我们的算法吗？是的。
我们可以采用Kd-Tree来加速邻居搜索。基本上，您需要在 O(m log(m)) 中构建n Kd-Tree并使用它们将平均情况下的复杂性降低到O(m n*log(m))
这个算法总能找到最小值吗？不
看看这个例子：
如您所见，使用先前算法获得的集群间距离不是最优的，它只是最近邻启发式。好消息是您将接近解决方案。您可以采用随机重启爬山算法来找到全局最小值
您可以使用点的 Delaunay 三角剖分。该三角剖分图对邻近信息进行编码：每个顶点通过 Delaunay 三角剖分的边连接到其最近的邻居。您可以使用该 Delaunay 三角剖分和联合查找来创建您的点集。
它可以看作是一个组合优化问题。解决它的一种方法是构建一棵树并对树的每个分支（称为Branch and Bound）进行 DFS 检查，方法是保持当前的最佳点集。这是您的示例的说明：
你沿着最左边的分支走，找到第一个结果。那么每次你下一个分支时，如果在某个时候你计算的距离优于你的实际结果，你可以停止对该分支的探索——你不会通过下下去得到更好的结果。
可能对几个点没有关系，但是如果你有10组10个点，这是一个好方法。加速该过程的一种简单方法是将最小的集合放在树的顶部（更少的节点和分支）。
显然，在最坏的情况下，最右边的分支是最好的。但是每个连续的分支都比前一个更好的可能性很小，所以你仍然应该获得一些时间。
注意：计算时不要忘记存储两点之间的距离，这样以后就不必重做微积分了。