如何快速均匀分割一个实数集 (浮点数集) ？

[feng32]

先上图：

split1  split2   split3  split4
  |        |    xx  |      |
  |        |    x   |      |
  |     x  |x    x  x      |
  | x      |   xxxx |x x   x
  |        x  x x x |      |
  x   x  x |     x  |x  x  x
--+--------+--------+------+--->
                        x axis

假定在 x 轴上，有 N 个点 (N >= 3)，如上图所示 (图中为了表示方便 y 方向有分布，实际上 y 轴是不存在的，只是为了方便表示点的密度分布)

然后我们需要在这些点中，挑出 K 个作为分割点 (N >= K >= 3)，其中第一个分割点是 N 个点中的最小值，最后一个分割点是 N 个点中的最大值；除了这两个点之外的其它分割点，需要使用一些方法来挑选

挑选的目标是：这些分割点的分割效果越均匀越好 (相邻的分割点之间的距离最好都差不多)，上图就展示了一个不错的分割效果

如果这些点是在一个固定区间内随机分布的，那么随机挑 K - 2 个点作为分割点，效果也不会差太多。但是如果有一个区间的点密度特别高，随机采样就可能都落到这个高密度区间，效果就会非常差

请教一下，这个算法有一个正式的名称吗？求精确解和近似解分别有什么比较有效率的方法吗？

[geelaw]

首先你要定义什么叫“均匀”，比如各个区间长度之方差更小、极差更小什么的。

如果要求方差小，比较简单，Var(X) = E[X^2] - E^2[X]，其中 E[X] 是固定的数，所以问题是最小化 E[X^2]，也就是最小化 X^2 求和，因为 k 是固定的。

令 x[] 以递增或者递减的方式存放各数，令 F(i, j) 表示前 i 个点搞 j 个分点最佳结果的 X^2 求和，显然

F(i, j) = min { F(i - t, j - 1) + (x[i] - x[i - t])^2 } for t > 1，或者什么类似的公式

初值什么的自己看着算，最后答案大概是 F(n, k) 什么的。

至于这个算法怎么优化你也可以自己慢慢想，现在已经是多项式时间的算法了。

[geelaw]

哦，极差其实也可以做。

令 G(x) 为最大组距 <= x 的时候的可能的最大最小组距，那么只要考虑 O(n^2) 种 x 的取值，然后对每个要考虑的 x 计算 G(x)（用动态规划法，类似上面的）。

虽然这个算法是多项式算法了，但是感觉还是比较慢，你慢慢想怎么优化吧，G(x) 看起来是递增函数，不知道有没有用。