Как разбить 2D-точки на интервалы (используя только вертикальные линии)? - PullRequest
Новая
       31

Как разбить 2D-точки на интервалы (используя только вертикальные линии)?

5 голосов
/ 22 мая 2019

Итак, у меня есть 2D разброс, заполненный точками (x,y). Я хочу нарисовать k вертикальных линий (x_1 = a, x_2 = b, ..., x_k = k), чтобы разбить точки на k групп.

Оптимальное решение минимизирует среднюю дисперсию для каждой группы y_value.

Какой алгоритм подходит? Это звучало как k-означает, но у меня есть ограничение, что линии должны быть вертикальными.

1 Ответ

4 голосов
/ 22 мая 2019

Вот идея, основанная на динамическом программировании.
Со следующими обозначениями: (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 сокращений для оставшихся точек.

Оттуда вы можете перейти к динамической программе. Вам понадобится трехмерный массив A с размерами 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
}

NB. Я немного быстро определился с диапазоном итерации для l, это может быть чем-то, на что можно обратить внимание.

...