Во-первых, 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)) неразрешимо.
Есть ли способ сделать это за полиномиальное время?
Если вы можете показать, что экземпляр k-средств можно преобразовать в экземпляр этой проблемы, тогда обязательно. В противном случае небольшие различия, подобные этим, могут иметь огромное влияние на сложность. –