如何找到最佳组合以最小化所有点组中的总距离

Question

给定 4n+k 点，位置为 （x，y）（或 （x，y，z） 表示 3D 情况），其中 n=1,2,3,...; k∈{0,1,2,3}。将点分为 4 个点的 n-k 组和 5 个点的 k 组。组质心是组中 4（或 5）个点的平均位置。

如何有效地得到最佳组合，使每个点到其自身群质心的距离之和最小化？

残酷的枚举是我获得最佳组合的唯一方法。然而，由于计算限制，残酷的武力仅在n非常小时有效。

我也尝试了K-Means聚类和遗传算法，但它们和这两种算法的组合都不能保证最佳组合。

Answer 1

由于问题应该是NP困难的，您将无法找到一种算法来保证找到最佳算法并在可接受的时间内在大数据上运行。

您必须满足于诸如kmeans之类的近似值。