algorithm - 最优网格聚类

Question

首先，一维情况。给定一个包含 N 个数字的数组，将其分成 n 个 block ，使每个元素与其 block 平均值的平方距离之和最小。例如，如果要求将 [0.1,0.3,2,1.2,1.3] 切成三 block ，则最佳解决方案是 [[0.1,0.3],[2],[1.2,1.3]]。

通过动态规划，这可以很容易地在 O(N * n) 中解决

现在是二维案例。我们给定了一个 (N,M) 矩阵，我们想将它分成 n*m block 。该解决方案应该看起来像一个不规则间隔的网格 - 它是一组 n 个水平切割和 m 个垂直切割。

这似乎更棘手。人们可以通过固定水平切割来动态地找到最佳垂直切割，但这似乎并没有导致任何地方。枚举所有可能的水平切割 O(C(M,m)) 是棘手的。

有没有办法在多项式时间内做到这一点？

Answer 1

这听起来很像 NP-Hard 问题:http://en.wikipedia.org/wiki/K-means_clustering所以我认为不存在多项式时间算法。