Один из способов - написать это как задачу математической оптимизации.
Модель оптимизации высокого уровня может выглядеть следующим образом:
Сначала мы определим переменные решения:
r(k,c) = coordinates for k-th box (e.g. c={x,y,w,h})
continuous variable with appropriate bounds
x(i,k) = 1 if point i is assigned to box k
0 otherwise
binary variable
Тогда 2D-модель может выглядеть следующим образом:
minimize sum(k, r(k,w)*r(k,h)) (sum of areas)
sum(k, x(i,k)) = 1 (assign point to one box)
x(i,k) = 1 ==> point i is inside box k (can be formulated as linear big-M constraints
or indicator constraints )
Для тестирования я сгенерировал 30 точек в блоке [0,1] x [0,1].
Используя |k|=5 коробки, мы получаем:
Это может быть непосредственно обобщено для большего количества измерений (построение графика становится более трудным).
По сути, это модель, которая сочетает в себе проблему присваивания (для переменных x) и проблему местоположения (для переменных r). Вероятно, это работает только для относительно небольших наборов данных. Для этого примера я использовал Gurobi (невыпуклый MIQP), и это проверенное глобально оптимальное решение. Отмечено, что даже для задач более высокого измерения мы можем переформулировать вещи в невыпуклую MIQCP (т.е. разрешимую Гуроби).
Для полноты данные и результаты для приведенной выше модели были:
---- 52 PARAMETER p data points
x y
i1 0.806 0.173
i2 0.530 0.149
i3 0.648 0.692
i4 0.352 0.020
i5 0.431 0.554
i6 0.641 0.775
i7 0.235 0.781
i8 0.268 0.082
i9 0.973 0.114
i10 0.874 0.667
i11 0.756 0.968
i12 0.199 0.240
i13 0.220 0.261
i14 0.989 0.172
i15 0.066 0.930
i16 0.806 0.832
i17 0.105 0.029
i18 0.229 0.094
i19 0.130 0.903
i20 0.437 0.728
i21 0.248 0.575
i22 0.360 0.516
i23 0.710 0.746
i24 0.704 0.746
i25 0.185 0.936
i26 0.817 0.673
i27 0.463 0.578
i28 0.089 0.657
i29 0.973 0.691
i30 0.894 0.078
---- 52 VARIABLE x.L assignment variables
k1 k2 k3 k4 k5
i1 1.000
i2 1.000
i3 1.000
i4 1.000
i5 1.000
i6 1.000
i7 1.000
i8 1.000
i9 1.000
i10 1.000
i11 1.000
i12 1.000
i13 1.000
i14 1.000
i15 1.000
i16 1.000
i17 1.000
i18 1.000
i19 1.000
i20 1.000
i21 1.000
i22 1.000
i23 1.000
i24 1.000
i25 1.000
i26 1.000
i27 1.000
i28 1.000
i29 1.000
i30 1.000
---- 52 VARIABLE r.L rectangles
x y w h
k1 0.066 0.575 0.181 0.361
k2 0.105 0.020 0.247 0.241
k3 0.360 0.516 0.103 0.211
k4 0.530 0.078 0.459 0.095
k5 0.641 0.667 0.332 0.301
---- 52 VARIABLE z.L = 0.290 objective