Понимание формата ввода ограничения Geost Minizincs

Глобальное ограничение geost неперекрытия для k размерных объектов требует, чтобы никакие два объекта не перекрывались. Его двоюродный брат geost_bb дополнительно ограничивает объекты, чтобы они вписывались в глобальную k размерную ограничивающую рамку.

Допустим, мы хотим найти подходящее размещение на 2D-плоскости для следующих трех объектов:

Допустим, мы можем повернуть каждый объект на 90 ° (или его кратное количество), тогда наша задача состоит в том, чтобы найти подходящее размещение на 2D-плоскости для 3 объектов, которые могут принимать одну из следующих 10 форм:

(Обратите внимание, что нам нужно учитывать только два возможных поворота для второго объекта.)

Теперь давайте посмотрим на определение geost_bb ограничение:

constraint
    geost_bb(
        k,              % the number of dimensions
        rect_size,      % the size of each box in k dimensions
        rect_offset,    % the offset of each box from the base position in k dimensions
        shape,          % the set of rectangles defining the i-th shape
        x,              % the base position of each object.
                        % (var) x[i,j] is the position of object i in dimension j
        kind,           % (var) the shape used by each object
        l,              % array of lower bounds
        u               % array of upper bounds
    );

Все, кроме x, kind, l, u, является входом для ограничения. Матрица x определяет левую нижнюю координату (наименьшей) прямоугольной выпуклой оболочки, охватывающей каждый объект i. Вектор kind определяет форму данного объекта i. Векторы l и u определяют ограничения нижней и верхней границы для каждого k измерения N-мерной прямоугольной выпуклой оболочки, охватывающей все объекты в задаче.

Форма задается составом набора прямоугольников. Каждый прямоугольник уникально идентифицируется своим размером и смещением относительно него. нижняя левая координата в соответствующей фигуре.

Обратите внимание, что может быть несколько способов разложить коллекцию фигур на коллекцию прямоугольников. Как показывает практика, всегда рекомендуется использовать как можно меньше прямоугольников.

Это возможное разложение для нашего текущего примера (прямоугольники с одинаковым размером и смещением имеют одинаковый цвет):

Закодируем этот пример в Minizinc.

Начнем с объявления входных параметров и выходных переменных нашей задачи:

int: k;
int: nObjects;
int: nRectangles;
int: nShapes; 

set of int: DIMENSIONS = 1..k;
set of int: OBJECTS    = 1..nObjects;
set of int: RECTANGLES = 1..nRectangles;
set of int: SHAPES     = 1..nShapes;

array[DIMENSIONS] of int:             l;
array[DIMENSIONS] of int:             u;
array[RECTANGLES,DIMENSIONS] of int:  rect_size;
array[RECTANGLES,DIMENSIONS] of int:  rect_offset;
array[SHAPES] of set of RECTANGLES:   shape;
array[OBJECTS,DIMENSIONS] of var int: x;
array[OBJECTS] of var SHAPES:         kind;

• Количество размеров для 2D-плоскости равно 2, поэтому k равно 2;
• Количество объектов 3, поэтому nObjects равно 3;
• Количество уникальных прямоугольников, необходимых для создания всех фигур в задаче, равно 13, поэтому nRectangles равно 13;
• Количество фигур равно 10, поэтому nShapes равно 10;

Следовательно, мы пишем:

k = 2;                  % Number of dimensions for a 2D Plane
nObjects = 3;           % Number of objects
nRectangles = 13;       % Number of rectangles
nShapes = 10;           % Number of shapes

Начиная с правого верхнего угла, мы определяем размер и смещение 13 прямоугольников, которые нам нужны, следующим образом:

rect_size = [|
     4, 2|
     2, 4|
     4, 2|
     2, 4|

     1, 2|
     2, 1|
     1, 2|
     2, 1|

     2, 1|
     1, 2|

     1, 1|
     1, 1|
     1, 1|];

rect_offset = [|
     0, 0|
     0, 0|
     0, 2|
     2, 0|

     2, 2|
     2, 1|
     1, 0|
     0, 2|

     0, 0|
     0, 0|

     0, 1|
     1, 1|
     0, 0|];

Теперь мы можем определить 10 формы, которые нам нужны, в терминах данного списка или прямоугольников:

shape = [
    { 1, 5 },
    { 2, 6 },
    { 3, 7 },
    { 4, 8 },

    { 9 },
    { 10 },

    { 9, 11 },
    { 10, 12 },
    { 7, 11 },
    { 7, 13 }
];

Мы требуем, чтобы решение проблемы размещало все объекты в квадрате 4x4, помещенном в начало координат:

l = [0, 0];
u = [4, 4];

Чтобы завершить этот пример, нам нужно дополнительное ограничение, чтобы гарантировать, что каждому объекту назначена допустимая форма из доступных:

array[OBJECTS] of set of SHAPES: valid_shapes;

valid_shapes = [{1, 2, 3, 4}, {5, 6}, {7, 8, 9, 10}];

constraint forall (obj in OBJECTS) (
    kind[obj] in valid_shapes[obj]
);

...

solve satisfy;

Возможное решение этой тривиальной проблемы:

x = array2d(1..3, 1..2, [0, 0, 0, 3, 0, 0]);
kind = array1d(1..3, [4, 5, 7]);
----------

Графически решение:

Ты спрашиваешь:

Эта спецификация верна?

Нет. Очевидным источником путаницы является определение формы. Приведенное выше объяснение должно прояснить этот аспект.