最佳聚類

有一個圖（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

回答