Про двумерную упаковку: offline алгоритмы

    Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
    Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

    От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

    В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

    В чем, собственно, проблема?


    Как частный случай задачи двумерной упаковки, 2DSP заключается в упаковке объектов конкретной формы в конечное число контейнеров конкретной формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объем объектов (которые упаковывают) были наибольшими. Разница с двумерной упаковкой состоит в том, что есть только один контейнер, и вместо минимизации количества контейнеров, мы минимизируем высоту заполненности одного. Обеспечиваем максимальную плотность упаковки, если хотите.

    Так как проблема NP-трудная, исследования сфокусированы главным образом на разработке приближенных алгоритмов решения. (На Хабре упоминался генетический алгоритм). Приближенные алгоритмы находят оптимальное решение с определенной точностью, но не гарантируют оптимальной упаковки для любого набора данных. При этом критерий оптимальности зависит от того, что вы пытались оптимизировать.
    Я расскажу о простейших стратегиях и о том, к чему это все применимо в жизни (кроме рюкзака с пивом).

    Итак, имеем набор из n прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон. Условимся, что все прямоугольники должны быть упакованы ортогонально, их нельзя поворачивать.
    Исходные данные
    (начало XX века, кубизм)
    Полуограниченная полоса Вариант упаковки (похуже) Вариант упаковки (получше)

    Видно, что задача имеет идеальное решение, при котором высота упакованных прямоугольников равна их суммарной площади деленной на ширину полосы.

    Зоопарк алгоритмов


    Для offline варианта 2DSP сразу известен размер всех упаковываемых прямоугольников, поэтому их можно отсортировать, выбрать по определенному критерию, сгруппировать или просто натыкать в подходящие места. На этом и основываются большинство алгоритмов:

    1. уровневые (level)
    2. шельфовые (shelf)
    3. плоские (plane)

    Плоские алгоритмы размещают прямоугольники строго вплотную друг к другу, но это не самая удачная стратегия, как может показаться на первый взгляд. Уровневые делят полосу на уровни, равные по высоте одному из выбранных прямоугольников, и помещают все остальные на конкретный уровень по определенному критерию. Шельфовые предопределяют сразу несколько шельфов (полок), и распихивают по ним прямоугольники, такое поведение характерно для online-алгоритмов, а это уже совсем другая история.

    Чем распространяться на общие слова, лучше обо всем по порядку.

    Next Fit Decreasing High


    Алгоритм, что называется, «в лоб». Прямоугольники сортируются по не-возрастанию высоты (Decreasing High намекает), самый высокий располагается в левом нижнем углу полосы, тем самым инициализируя первый уровень, по высоте равный ему. Остальные прямоугольники располагаются слева направо, пока есть место на текущем уровне. Прямоугольник, который не поместился на уровне, помещается сверху, образуя следующий уровень, и так далее.
    Иллюстрации для каждого алгоритма будут производиться для следующих двух примеров: для наглядности, в левом форма прямоугольников тяготеет к вытянутой, в правом — более квадратные.

    Алгоритм NFDH
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles 
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: level = 0; h(level) = 0; w(level) = 0; i = 1
     2: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
     3: Pack rectangle Li left-justifed at the bottom of the strip
     4: h(level) = h(Li); w(level) = w(Li)
     5: for i = 2..n do
     6:   if W - w(level) ≥ w(Li) then
     7:     pack rectangle Li to the right of rectangle Li-1
     8:     w(level) += w(Li)
     9:   else [W - w(level) < w(Li)]
    10:     create a new level above the previous one and pack rectangle Li on the new level
    11:     level++; w(level) = w(Li); h(level) = h(level-1) + h(Li)
    12:   end if
    13: end for
    14: print H = h(level)


    First Fit Decreasing High


    Похожий на предыдущий алгоритм, с той разницей, что для каждого следующего прямоугольника ищется место не только на последнем уровне, а начиная с самого нижнего. Отсюда и «first fit» — прямоугольник помещается на первый подходящий уровень снизу. Интуитивно понятно, что упаковка будет качественнее. Еще одно значительное отличие — в производительности, так как в худшем случае придется рассматривать на каждом шагу все уровни снизу вверх.

    Алгоритм FFDH
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: level = 0; h(level) = 0; i = 1; LevelNum = 1
     2: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
     3: Pack rectangle Li left-justifed at the bottom of the strip; h(level+1) = h(Li)
     4: for i = 2..n do
     5:   search all levels (from the bottom) for the lowest with sufficient space
     6:   if such a level exist then
     7:     pack rectangle Li left justified on that level
     8:   else [there is insufficient space in all existing levels]
     9:     LevelNum++; level = LevelNum; h(level) = h(level-1) + h(Li)
    10:     pack rectangle Li on the new level
    11:   end if
    12: end for
    13: print H = h(level)


    Best Fit Decreasing High


    Модификация предыдущего алгоритма. Суть ее в том, что из уровней, подходящих для упаковки очередного прямоугольника, выбирается не первый, а лучший. Лучший уровень — это такой, на котором останется минимум места после упаковки текущего прямоугольника. Проще говоря, выбирается минимальное подходящее пространство, что способствует лучшему заполнению уровней.

    Алгоритм BFDH
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: level = 0; h(level) = 0; i = 1; LevelNum = 1
     2: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
     3: Pack rectangle Li left-justifed at the bottom of the strip; h(level+1) = h(Li)
     4: for i = 2..n do
     5:   search all levels for the level with sufficient space and has minimum residual space
     6:   if such a level exist then
     7:     pack rectangle Li left justified on that level
     8:   else [there is insufficient space in all existing levels]
     9:     create a new level above the top-most level and pack rectangle Li
    10:     LevelNum++; level = LevelNum; h(level) = h(level-1) + h(Li)
    11:   end if
    12: end for
    13: print H = h(level)


    Knapsack 0-1


    Здесь стоит остановиться подробнее. Knapsack 0-1 — это частный случай задачи о ранце; примечателен тем, что кроме ответа на основной вопрос (нет, не 42, а полученный объем упаковки) дает еще и решение — список предметов, которые нужно упаковать. Порядок действий таков: прямоугольники сортируются по не-возрастанию высоты; упаковывается первый прямоугольник на новый уровень; для этого уровня находится решение задачи Knapsack 0-1, которое дает нам список прямоугольников, максимизированный по площади. Выбранные прямоугольники пакуются и извлекаются из списка неупакованных, уровень закрывается и открывается новый — инициализированный, как водится, первым (самым высоким) из оставшихся. Повторить, пока есть прямоугольники.

    Алгоритм KP01
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
     2: level = 0
     3: while there are unpacked rectangles do
     4:   pack first unpacked rectangle, Li say
     5:   h(level) += h(Li)
     6:   solve KP01 instance
     7:   pack selected rectangles
     8:   level = level + 1
     9: end while
    10: print H = h(level)


    Split Fit


    Алгоритм, призванный улучшить FFDN по принципу «разделяй и властвуй». Для начала отбираются прямоугольники, которые шире чем половина полосы. Они будут упакованы в первую очередь. Из них выбираются еще более широкие — шире, чем 2/3 полосы; они упаковываются алгоритмом FFDH. Над ними, начиная со следующего уровня (назовем его уровень R), упаковываются оставшиеся, те, что все еще шире 1/2, но уже 2/3. Они тоже упаковываются с помощью FFDH. Это разделение создает свободный регион шириной 1/3 справа от только что упакованных, начинающийся на уровне R и заканчивающийся текущей верхней границей упаковки (то есть он не простирается выше прямоугольников 1/2 < width <= 2/3). Все оставшиеся прямоугольники, которые уже, чем 1/2 полосы, упаковываются с помощью того же FFDH в первую очередь в образовавшийся регион, а если не помещаются — то сверху. На словах звучит громоздко, на картинке должно быть понятнее. А для тех, кто уже устал от моих литературных упражнений — псевдокод:

    Алгоритм SF
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
    1: Let m ≥ 1 be the largest integer for which all rectangles in L
       have width at most 1=m
    2: Partition the list of rectangles L into two sublists L1 and L2
       such that L1 is a list of rectangles of width greater than
       1/(m+1), while L2 is a list of rectangles of width at most 1/(m+1)
    3: Pack the L1 rectangles into the strip, using the FFDH algorithm
    4: Rearrange the blocks of this packing such that those of width
       greater than (m+1)/(m+2) are below those of width
       at most (m+1)/(m+2)
    5: Pack rectangles of width at most 1/(m+2) into the region R
       using FFDH algorithm such that no rectangle overlaps the top
       of R and those failing to fit in R are packed above the packing of L1
    6: Output the height of the strip, found by adding the height of each level


    Join


    Судя по всему, этот алгоритм был заточен под определенного характера входные данные, что ж, любая практическая ситуация имеет право на существование. Сейчас сами все поймете. Отсортированные, как водится, по не-возрастанию высоты прямоугольники объединяются в пары так, чтобы разница высоты в паре не превышала заданной доли, обычно 0-10%. Еще одно условие — чтобы их суммарная ширина помещалась в полосу. Полученные «супер-прямоугольники» упаковываются вместе с оставшимися без пары с помощью NFDH и FFDH, выбирается лучшее решение.
    Существует вариация этого алгоритма, когда прямоугольники сортируются по ширине и объединяются вертикально, с тем же условием максимального отклонения ширины в паре на заданное количество процентов.

    Алгоритм Join
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)}, the constant gamma as a
           percentage and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
     2: j = 1
     3: while j+1 ≤ n do
     4:   if (h(Lj) - h(Lj+1))/h(Lj) * 100 < gamma
             and w(Lj) + w(Lj+1) ≤ W then
     5:     w(Lj) += w(Lj+1)
     6:     j += 2
     7:   else
     8:     j++
     9:   end if
    10: end while
    11: Execute the NFDH and FFDH algorithms to pack the rectangles
    12: From the best solution, construct a feasible packing of the original instance
    13: Output the height of the strip, found by adding the height of each level


    Floor Сeiling No Rotation


    Если вы все еще недоумеваете по поводу остающегося на уровнях пространства, то этот алгоритм для вас. Прямоугольники сортируются по не-возрастанию высоты (неожиданно, да?) и применяется алгоритм BFDH с некоторыми модификациями. У каждого уровня есть «пол» (floor) и «потолок» (ceiling). Пока есть возможность, прямоугольники пакуются на «пол» слева направо. Когда место заканчивается, предпринимается попытка упаковать на «потолок» справа налево; если нет места на потолке, то только тогда начинается новый уровень. В лучших традициях BFDH, на каждом шагу просматриваются все уровни — сначала «пол», затем «потолок» — на наличие наиболее подходящего места. Упаковка, как видите, неплохая. Метод удачно упаковывает по «потолкам» самые мелкие прямоугольники.

    Алгоритм FCNR
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
     2: for i = 1..n do
     3:   if Li is ceiling feasible then
     4:     pack Li on ceiling with minimum residual space
     5:   else [Li is not ceiling feasible]
     6:     if Li is floor feasible then
     7:       pack Li on the floor with minimum residual space
     8:     else [Li is not floor feasible]
     9:       level++;
    10:     end if
    11:   end if
    12: end for
    13: Output the height H of the strip, found by adding the height of each level


    Sleator


    Настало время «плоских» алгоритмов, без деления на уровни. Алгоритм Sleator использует интуитивный принцип упаковки рюкзака: сложить на дно самые крупные предметы и засыпать сверху мелкими. Вот как это выглядит. Из прямоугольников выбираются самые широкие, шире половины полосы, как вы уже догадались, и хаотично укладываются друг на друга с выравниванием по левому краю. Оставшиеся сортируются по не-возрастанию высоты и начинают укладываться друг за другом слева направо сверху на уже уложенные. Как только их суммарная ширина превысит половину ширины полосы, оставшиеся раскидываются друг на друга то слева (начиная от левого края полосы), то справа (от середины), по принципу «где на данный момент меньше». Как видно из рисунков, этим методом удобнее укладывать книги, чем коробки.

    Алгоритм Sleator
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: Partition L into two sublists L1 and L2 consisting of rectangles
        of width greater than 1/2 and at most 1/2 respectively.
     2: Stack all the rectangles in L1 left justified on top of
        one another starting at the bottom of the strip. Compute Hstack
     3: Packing will continue above Hstack
     4: Sort the rectangles in L2 according to non-increasing height
        such that h(Li) ≥ h(Li+1) for i < n
     5: Let Htall be the height of the tallest rectangle in list L2.
     6: Pack the rectangles, left justified from the left to the right
        edge of the strip until there is insufficient space to pack
        a rectangle or all of the rectangles have been packed
     7: Partition the strip with a vertical line into two equal segments.
        There is possibly one rectangle whose interior may be intercepted
        by the vertical line.
     8: Let Hright and Hleft be the height of the rectangle on the right
        (resp. left) half of the strip whose left (resp. right) edge
        is adjacent to the vertical line or whose interior is intercepted
        by the vertical line
     9: while there are unpacked rectangles do
    10:   Draw horizontal lines of length half across
          the rectangles whose height is Hleft and Hright
    11:   All subsequent packing will either be on the left
          or right segment of the strip
    12:   Select the segment with minimum height and pack
          rectangles from the edge of the strip to the
          vertical line until all rectangles have been
          packed or there is a rectangles which does not fit
    13: end while
    14: print H = max{Hleft; Hright}


    Burke


    Снова безуровневый алгоритм, для которого вводится дополнительная «карта высот»:
    |               |    |    _   _   ___|
    |               |    |   | |_|_| |   |
    |               |    |_  | |   | |   |
    |_ _ _ _ _ _ _ _| .. |_|_|_|_ _|_|_ _|
     0 0 0 0 0 0 0 0      1 0 3 2 3 0 3 3

    Это массив, по которому по мере заполнения полосы можно отслеживать наименее заполненные области и их ширину. В начале он заполнен нулями. Прямоугольники сортируются по не-возрастанию, внезапно, ширины. Затем, на каждом шаге алгоритма:
    1. Вычисляется позиция самой низкой области — индекс минимального значения массива;
    2. Выбирается наиболее подходящий прямоугольник — во-первых, помещающийся в эту область, во-вторых, максимально ее заполняющий по ширине;
    3. Если подходящий прямоугольник найден, он размещается в этой области одним из способов:
    3.1 По левому краю области;
    3.2 Ближе к более высокому соседу, если один из соседей — край полосы, то ближе к краю;
    3.3 Ближе к менее высокому соседу, если один из соседей — край полосы, то дальше от края. К значениям массива, соответствующим ширине прямоугольника, прибавляется его высота.
    4. Если подходящего прямоугольника нет, область «заполняется» путем выравнивания ее высоты до высоты ближайшего края.
    Вам уже захотелось написать по этому алгоритму бота, играющего в Тетрис?

    Алгоритм Burke
    Input: The number of rectangles to be packed n,
           the dimensions of the rectangles
           {w(Li); h(Li)} and the strip width W.
    Output: The height of a packing obtained in the strip.
     1: Sort the rectangles according to non-increasing width such that w(Li) ≥ w(Li+1) ≥ .. ≥ W(Ln)
     2: for each placement policy
        (leftmost, tallest neighbour, smallest neighbour) do
     3:   while Rectangles not packed do
     4:     find lowest gap
     5:     if w(Li) ≤ GapWidth then
     6:       place best fitting rectangle using placement policy
     7:       raise elements of array to appropriate height
     8:     else
     9:       raise gap to height of the lowest neighbour
    10:     end if
    11:   end while
    12: end for
    13: The elements of the array with greatest entry give the total height of the packing
    14: Compare total packing heights obtained by each placement policy and return the best solution


    Кто лучше?


    Результат работы каждого алгоритма — это уровень заполненности полосы, чем меньше, тем лучше. Его можно оценить отношением к нему оптимального:



    Сравним полученные результаты для двух приведенных наборов исходных данных:
    Оптимальное
    решение
    NFDH FFDH BFDH KP01 SF JOIN FCNR Sleator Bruke
    Набор 1 149 0,65 0,71 0,71 0,71 0,75 0,61 0,83 0,68 0,72
    Набор 2 140 0,66 0,77 0,77 0,78 0,77 0,70 0,84 0,51 0,71

    Видим, что для обоих наборов данных победил алгоритм Floor Ceiling. Можно отметить, что Sleator показал гораздо лучший результат для первого набора, а Join, наоборот, больше подходит для второго. Но все это не более, чем статистика.

    Эпилог


    За счет своей простой формулировки, задача бинарной упаковки может быть подтянута к огромному количеству практических применений: непосредственно к упаковке объектов или раскройке материала, распределению средств, планировке задач на кластерах, etc. В жизни мало рафинированных задач, но, ограничив некоторые условия, можно свести ситуацию к красивой математической модели, имеющей неплохое решение, достижимое за полиномиальное время. А однажды, в результате эффекта бабочки, отброшенные условия возымеют большой вес и решение полетит ко всем Безымянным. Вот из-за таких допущений и несовершенен мир.

    Что-то я отвлеклась. В следующей части надеюсь рассказать об online-версии задачи и шельфовых алгоритмах. Good luck!


    Источники вдохновения:
    Nthabiseng Ntene An Algorithmic Approach to the 2D Oriented Strip Packing Problem
    David Pisinger Knapsack problem
    Survey on two-dimensional packing
    Level Algorithms and Shelf Algorithms (осторожно, дизайн-вырви-глаз)

    Код (Qt):
    Алгоритмы packager.h packager.cpp
    Гуй window.h window.cpp renderarea.h renderarea.cpp main.cpp

    UPD: Online algorithms
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 13

      –3
      Постановка задачи заумная, лучше сказали бы что надо создать атлас картинок для игры или упаковать лайтмапы.
        +3
        Простите, что?
          0
          Такой алгоритм часто используется для создания атласов картинок для игр или упаковки освещения. Нужно для того чтобы драйвер видеокарты не переключался каждый раз на новую текстуру для отрисовки очередного объекта.

          en.wikipedia.org/wiki/Texture_atlas
            +1
            Слишком специфичная задача, домохозяйки не поймут (и не только домохозяйки). Все-таки лучше всего подходит нарезка листа металла с наименьшим количеством отходов. Оно, так же, как и ваш пример, включает в себя описание двумерного пространства, но при этом явно указывает на то, что должно остаться минимальное число отрезков(отходов), имеющих при этом наибольшую площадь.
              –1
              Вы называете читателей хабра домохозяйками?
                +1
                Что-то мне подсказывало, что вы прицепитесь к этому слову )
                Это принцип «проще — лучше», только не в программировании, а в изложении информации. Уровень подготовки у всех разный, а вы попытались объяснить простое явление более сложным, введя сразу кучу понятий малознакомых широкой аудитории, как то: атласы, текстуры и лайтмапы, что не соответствует правилу хорошего примера — он должен быть понятен наибольшему кругу лиц с разнообразной подготовкой и вносить ясность. Зачем плодить сущности в воображении — оперативная память у человека и без того небольшая!
                  0
                  Да домохозяйки и есть, в общем-то.
          0
          Странно, что не описан такой алгоритм: сортируем по невозрастанию. Нарезаем пространство на свободные прямоугольники сортируем их по неубыванию и по наименьшему количеству пересечений. Вставляем.
          Правда он достаточно затратный, но, не о том речь, как я понимаю.
            0
            Можно поподробнее? Свободные прямоугольники — это как? Насколько я понимаю (в чем я вообще сомневаюсь), пространство в данном случае должно быть строго ограничено, тогда да, это уже другие условия.
              0
              Просто поместите в пространство несколько прямоугольников начиная слева снизу, а затем проведите направляющие от границ прямоугольников до края пространства: получите пространство разделенное на прямоугольники.
                0
                Принцип гильотины. Для заранее известного набора прямоугольников это неоправданно трудоемко. Думаю, в следующей статье (для online-варианта) стоит рассмотреть что-то подобное.
            +1
            Есть еще алгоритм MaxRects — тоже неплохо упаковывает.
              +1
              Статья очень интересная. Занимаюсь схожей тематикой. Большинство статей с которыми я знакомился задействовали больше эвристику: генетические алгоритмы, имитация отжига, поиск с запретами и т.д.

              При этом существуют методы поиска глобально-оптимального решения. Самый популярный из мне известных — метод ветвей и границ. Но с ним одна беда — низкая размерность задач. Хотя существуют исключительные ситуации (качественные границы) когда он может реально применяться

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое