我有K组数据点，我想制作大小为K的组，以最小化组内距离的总和。我熟悉匹配算法与二分图，但我想这两个以上。
有任何想法吗？
编辑：
每组将由每组中的一个元素组成，不允许重复。
例如：您有{a1，a2，a3}，{b1，b2，b3}，{c1，c2，c3}您想要创建组，例如{a1，b3，c3}，{a2，b1，c2}，{a3，b2，c1}最小化组内距离的总和。
这个问题可以简化为另一个类似的问题，我之前已经解决了另一个stackoverflow问题。想法是计算n / k大小的组的所有组合，并根据它们的组内距离对这些组合进行加权。遍历搜索空间以获得有效的组合组合。保留最小总和的记录，并使用它来修剪死端分支。您可以通过生成解决方案的最佳子集来使用动态编程加速搜索，并从中构建最终解决方案（如我在其他帖子中所述），或者您可以使用贪婪的方法和一些手动的浪费技巧来找到近似最佳（或最佳）解决方案（也在所述帖子中描述）。 Here是你可以减少这个问题的子问题的链接。
即使对于k = 3，它也具有NP难问题三维匹配的风味。 （明显的减少不起作用，因为可能存在幻像三元组，其中三对无效三元组中的每一对分别出现在有效三元组中。）
根据实例的大小，我会尝试使用列生成进行本地搜索或整数编程（但是如果没有低维度量空间的结构，内部问题似乎很难，即使这样也是非常重要）。