如何将2D点划分为间隔（仅使用垂直线）？

Question

所以我有一个充满点的2D散点图(x,y)。我想绘制k条垂直线(x_1 = a, x_2 = b, ..., x_k = k)，以便将点划分为k组。

最佳解决方案将使每个组的平均方差最小y_value。

什么是合适的算法？听起来像k均值，但我的约束是线条必须垂直。

Answer 1

这是一个基于动态规划的想法。
带有以下符号： (x_1, y_1), ..., (x_n, y_n)点，用于x_1 <= x_2 <= ... <= x_n分组K。
Var(i, j)的方差y：y_i, ..., y_j.
F_K((x_1,y_1), ..., (x_n, y_n)) = F_k(1,n)问题最佳解决方案的价值。

然后我们有以下内容：
F_k(i,j) = min for l in i...j-k+1 of (Var(i,l) + F_(k-1)(l+1, j)和
F_1(i,j) = Var(i,j)。

上面的属性只是意味着将点分成“k”组的最佳方法是选择最左边的切割（选择），以及其余点的 l最佳切割选择。k-1

从那里您可以选择动态程序。您需要一个 3DA维度数组n*n*K来存储所有 的 F_k(i,j) 值i,j,k。该程序看起来像：

function get_value(P: points, A: 3D array, i, j, k){
  if A[i][j][k] is defined{
    result = A[i][j][k]
  } else if k == 1 {
    A[i][j][k] = get_var(P, i, j)
    result = A[i][j][k] 
  } else {
    result = +INF
    for l in i ... j-k+1 {
      tmp = get_value(P, A, i, l, 1) + get_value(P, A, l+1, j, k-1)
      if tmp < result {
        result = tmp
      }
    }
  }
  return result
}

注意：我对迭代的范围有点快l，这可能是值得研究的事情。