优化网格聚类

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所以我不认为存在多项式时间算法。