Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.
От задачи о ранце отпочковалась задача об упаковке в контейнеры (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 сразу известен размер всех упаковываемых прямоугольников, поэтому их можно отсортировать, выбрать по определенному критерию, сгруппировать или просто натыкать в подходящие места. На этом и основываются большинство алгоритмов:
- уровневые (level)
- шельфовые (shelf)
- плоские (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
Автор: Wildy
