優化網格聚類

Question

首先是1D情況。給定N個數字的數組，將其切成n個塊，以便將每個元素的平方距離與其塊平均值的總和最小化。例如，如果要求將[0.1,0.3,2,1.2,1.3]分成三部分，最佳解決方案是[[0.1,0.3]，[2]，[1.2,1.3]]。

隨着動態編程這可以很容易在O解決了這個（N * N）

現在2D情況。我們得到一個（N，M）矩陣，並且我們想要以n * m塊來剪切它。解決方案應該看起來像一個不規則間隔的網格 - 它是一組n個水平切割和m個垂直切割。

這似乎更棘手。人們可以通過固定水平切割來動態地找到最佳的垂直切割，但這似乎不會導致任何地方。枚舉所有可能的水平切割O（C（M，m））是棘手的。

有沒有辦法在多項式時間做到這一點？

Answer 1

這聽起來很像NP-Hard問題：http://en.wikipedia.org/wiki/K-means_clustering所以我不認爲存在多項式時間算法。