如何在具有最大平均子集大小的等距子集上拆分集？

Question

我有一组N个对象，它们之间有N * N个距离。我想在子集上聚集这个集合，这样在每个集群中，所有对象都具有相同的距离，并且所有集群上的均值（cluster_size）都被最大化。

我尝试通过这样的算法解决这个任务：

1. 让我们枚举对象之间的所有唯一距离。
2. 对于每个唯一距离，X允许基于对象构建图形作为节点和邻接矩阵，其中如果对象A和B之间的距离恰好为X，则存在A和B之间的边缘
3. 让我们在此图中找到最大团。如果此团的大小大于当前最大值 - 更新最大值并将clique存储为Result
4. 从一组对象中删除存储在Result中的对象
5. 重复直到对象集不为空

有没有更有效的[近似]解决方案？

Answer 1

平均值（簇大小）=总点数/簇数

最大化这一点的唯一方法是最小化群集的数量。这似乎是一个相当糟糕的选择作为优化目标。您可能想重新考虑这个目标。

除此之外，我认为你的算法是相当明智的。由于问题可能是NP难，你确实想要使用贪婪的近似。

我建议在重新计算时更加懒惰，并添加一些界限。

1. 为每个唯一距离构建子图。
2. 按大小对子图进行排序，降序。
3. 除非您具有上一次迭代的缓存值，否则请在每个子图中找到最大的clique。记住整体最大的集团。如果当前最大值大于其余子图则停止。
4. 找到输出最佳子图。
5. 从所有图中删除包含的节点，并忘记那些包含刚找到的任何节点的最佳集团。回到2。