最佳聚类

有一个图（E，V）。对于每个边（i，j），有一个支付P [i，j]，可能是正数，零或负数。我们按聚类划分顶点。每次两个相邻顶点v1和v2属于不同的聚类，我们收到付款P [v1，v2]。如何最大化总付款？这个问题是NP难吗？最佳聚类

2016-12-13 user31264

你正在寻找一个[多切（http://www.cs.cmu.edu/~anupamg/adv-approx/lecture18.pdf）。 –

如果没有进一步的限制（例如，给定的M所产生的集群的数量必须），那么是什么阻止我迭代边缘并通过正向支付来切断所有边界？诚然，它可能会产生一个仍然连续的图（不分区），但是，由于问题没有施加任何限制，因此单个集群作为结果是可以接受的，不是吗？ –

@Adrian Colomitchi我们不能任意削减一些边缘而不能削减其他边缘。我们只能从不同的群集中剪切边缘。如果我们削减A-B，但不削减B-C，我们也应该削减A-C。 – user31264

不要寻找群集，而是为削减。

最大化边缘切割的重量通常称为“最大切割”。最常见的问题是最小切割，并且有一些聚类算法用最小切割问题表示。切割也与流动网络有关。

正如评论中指出的那样，您需要指定一些边界条件。例如，必须将这些点切成两个标签，并且只切割具有不同标签的边缘。

是的，这类削减通常是NP-hard。

2016-12-13 22:21:21

回答