DOI: 10.15514/ISPRAS-2026-38(2)-3

^1,2 Д.О. Лазарев, ORCID: 0000-0002-6253-6447 <lazarev@ispras.ru>

¹ А.В. Шокуров, ORCID: 0000-0002-6801-7728 <shok@ispras.ru>

¹ Институт системного программирования им. В.П. Иванникова РАН,

Россия, 109004, г. Москва, ул. А. Солженицына, д. 25.

² НИУ Московский физико-технический институт,

Россия, 141701, Московская область, г. Долгопрудный, Институтский переулок, д.9.

Аннотация. Проводится анализ в среднем задачи упаковки $d$-мерных прямоугольных параллелепипедов в контейнеры. Для решения задачи, предложен алгоритм увеличения размерности, позволяющий эффективно строить алгоритм упаковки в (d+1)-мерные контейнеры, используя алгоритм упаковки в d-мерные контейнеры. При упаковке, стремимся минимизировать ожидаемый объем незаполненного пространства использованных контейнеров. Ранее известные результаты верхней оценки числа упаковываемых параллелепипедов улучшены. Уменьшение объема незаполненного пространства подтверждают проведенные вычислительные эксперименты. При анализе алгоритмов в среднем, может возникать переобучение. Связано оно с тем, что минимальный ожидаемый объем незаполненного пространства может достигаться для одного конкретного распределения, или для семейства распределений входных параметров алгоритма, в решаемой задаче входные параметры – длины сторон параллелепипедов. Для борьбы с данным нежелательным эффектом, предложенный алгоритм увеличения размерности был обобщен на случай произвольного заранее известного распределения длин сторон параллелепипедов. Эффективность обобщенного алгоритма подтверждена вычислительными экспериментами.

Ключевые слова: упаковка в контейнеры; многомерная задача упаковки в контейнеры; вероятностный анализ; переобучение; алгоритм увеличения размерности.

Для цитирования: Лазарев Д.О., Шокуров А.В. Алгоритм для многомерной упаковки в контейнеры и его вероятностный анализ. Труды ИСП РАН, том 38, вып. 2, 2026 г., стр. 35–52. DOI: 10.15514/ISPRAS-2026-38(2)-3.

Благодарности: Исследования поддержаны фондом отдела теоретической информатики Института системного программирования им. В.П. Иванникова РАН. Результаты получены с использованием услуг Центра коллективного пользования Института системного программирования им. В.П. Иванникова РАН – ЦКП ИСП РАН.

1. Введение

Задача упаковки многомерных объектов в контейнеры имеет многочисленные практические приложения. Так, одномерная задача упаковки в контейнеры, в англоязычной литературе известная как “bin packing problem”, возникла в силу потребности решения задач форматирования таблиц или аллокации файлов [1]. Также, одномерная задача упаковки в контейнеры, позволяет оптимизировать погрузку грузовых автомобилей с заданным ограничением веса [2]. Двумерная задача упаковки в контейнеры, моделирует проблему раскроя и перевозки материалов, задачу оптимизации размещения объектов на плоскости, а также проблему пакетной обработки вычислительных задач [3]. Трехмерная задача упаковки учитывает еще одно измерение и позволяет моделировать многие промышленные приложения: оптимизацию размещения трехмерных объектов на складах, в вагонах и самолетах [4].

В настоящее время, в силу быстрого роста популярности распределенных вычислений, широкого распространения вычислительных кластеров, грид-технологий, а также облачных вычислений, интерес к задачам упаковки возрастает в связи с новыми приложениями: задачами управления ресурсами распределенных вычислительных систем и развитием техники облачных вычислений [5-7].

1.1 История исследования задачи упаковки в контейнеры и классические результаты

Задача упаковки в контейнеры является одной из первых известных NP-трудных в сильном смысле задач [8]. Для ее решения было предложено множество приближенных алгоритмов и получены оценки их качества в наихудшем и в среднем случаях. В настоящей работе рассматриваются алгоритмы, работающие в режиме онлайн, для которых размер и положение очередного упаковываемого объекта неизвестны в момент упаковки предыдущего.

Опишем два важных алгоритма упаковки объектов в одномерные контейнеры:

• First fit (FF). При упаковке алгоритмом first fit, каждый следующий объект размещается в последний созданный подходящий контейнер. Если же для него не подходит ни один из существующих контейнеров, то для его размещения создается новый контейнер.
• Best fit (BF). Каждый следующий объект размещается в наиболее плотно заполненный подходящий контейнер. Если для него не подходит ни один из существующих контейнеров, то для его упаковки создается новый.

Оба приведенных выше алгоритма принадлежат классу алгоритмов any fit, в который входят все алгоритмы, работающие в режиме онлайн и размещающие очередной объект в один из уже созданных контейнеров в том случае, если имеется хотя бы один подходящий из созданных контейнеров.

Приведем лучшие известные результаты для задачи упаковки в контейнеры при анализе в среднем и в худшем случаях. При исследовании алгоритма $A$ упаковки в худшем случае, исследуем асимптотическую точность $R^{\infty }$, или минимальное по всем существующим наборам упаковываемых объектов отношение числа контейнеров, необходимых для упаковки с использованием алгоритма $A$ к числу контейнеров, в которые оптимальный алгоритм может упаковать эти же наборы параллелепипедов при стремлении к бесконечности числа упаковываемых объектов. При анализе в среднем случае, исследуется математическое ожидание $W$ объема незаполненного пространства контейнеров после упаковки в случае, когда длины сторон упаковываемых параллелепипедов принадлежат известному распределению или семейству распределений.

При анализе в худшем случае одномерной задачи, было показано [1], что асимптотическая точность работающего в режиме онлайн алгоритма first fit составляет $1.7$, и что асимптотическая точность любого алгоритма из any fit не превосходит асимптотической точности алгоритма first fit. Для алгоритмов не из класса any fit, алгоритм с лучшей из известных верхних оценок асимптотической точности $R^{\infty }\le 1.541$ был предложен в работе [9]. Наилучшая известная нижняя оценка была получена в [10]. Было доказано, что для любого алгоритма, работающего в режиме онлайн, $R^{\infty }\ge 1.536$.

При анализе худшего случая алгоритмов, работающих в режиме онлайн, для многомерной задачи упаковки в контейнеры, лучшие известные нижние оценки [11] для асимптотической точности, полученные в случае двумерной задачи, равны $1.802,$ а в случае трехмерной задачи составляют $1.974$. Лучший из известных алгоритм [12] для двумерной задачи имеет асимптотическую точность $2.554$, для случая $d$-мерной задачи в [13] был предложен алгоритм с $R_d^{\infty }={\Pi }_{\infty }^d$, где ${\Pi }_{\infty }\approx 1.691$.

При анализе в среднем случае алгоритмов, работающих в режиме онлайн, для задачи упаковки в контейнеры выделяют постановки с незаданным завершением (англ. open-end), когда точное число объектов неизвестно до выпадения символа останова после упаковки последнего объекта, и постановку с известным завершением (англ. closed-end), когда число объектов известно до начала упаковки объектов в контейнеры (подробнее – в разделе “Постановка задачи упаковки в контейнеры”).

В [14] был предложен алгоритм для одномерной задачи c известным завершением с ожидаемым объемом незаполненного пространства контейнеров $W_N\left(N\right)=\Theta \left(\sqrt{N}\right)$, сначала упаковывающий первые $\lfloor \frac{N}{2}\rfloor$ объектов в отдельный контейнер каждый, а затем – упаковывающий оставшиеся объекты с использованием алгоритма BF. (Здесь $W_N\left(N\right)$ – математическое ожидание объема контейнеров, незаполненного объектами после упаковки $N$ объектов). Для алгоритмов с незаданным завершением, также имеется алгоритм [15], достигающий нижней оценки [14], равной $\Omega \left(\sqrt{N\ln N}\right)$. Отметим также, что алгоритм BF упаковки с незаданным завершением, согласно [16], имеет качество $W_N\left(N\right)=\Theta \left(\sqrt{N}{\ln }^{\frac{3}{4}}N\right)$, близкое к оптимальному.

При анализе в среднем, для $d$-мерной задачи упаковки в контейнеры, был предложен алгоритм [17] с незаданным завершением с $W_{d,N}\left(N\right)=\Theta \left(N^{\frac{d+1}{d+2}}\right)$. Данный результат улучшен в настоящей работе до $W_{d,N}\left(N\right)=O\left(N^{\frac{d}{d+1}}{\ln }^{\frac{3}{2\left(d+1\right)}}N\right)$.

2. Постановка задачи упаковки в контейнеры

Приведем необходимые определения. Определим, следуя работе [13], многомерную задачу упаковки в контейнеры (англ. multi-dimensional bin packing problem) в постановке упаковки в гиперкубы (англ. box packing). Дан набор, состоящий из $N$ $d$-мерных открытых прямоугольных параллелепипедов, которые в дальнейшем для краткости будем называть параллелепипедами. Требуется упаковать параллелепипеды без вращений и попарных пересечений в как можно меньшее число контейнеров. Контейнер – это $d$-мерный гиперкуб со стороной единица. Стороны параллелепипедов и контейнеров параллельны осям прямоугольной декартовой системы координат.

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

Проводится вероятностный анализ алгоритмов упаковки в предположении, что длины сторон, расположенных по $i$-ой координате каждого из параллелепипедов, независимы в совокупности между собой и с другими длинами сторон и имеют равномерное на $\left[\mathrm{0,1}\right]$ распределение $\forall i\in \left\{1,...,d\right\}$. Также приведено естественное обобщение предложенного алгоритма на случай общего распределения длин сторон параллелепипедов.

Рассматриваются онлайновые алгоритмы с незаданным завершением. В работе [14] приведено следующее описание работы алгоритма с незаданным завершением:

1. Выберем случайно равновероятно $k$ из набора $\left\{1,...,N\right\}$.
2. Подадим на вход алгоритму последовательность из $k$ случайных параллелепипедов, которые алгоритм должен упаковать в режиме онлайн.
3. Подадим алгоритму на вход символ останова.

Здесь $N$ – натуральное число, известное алгоритму до начала работы.

Обозначим через $A_{d,N}$ алгоритм упаковки в $d$-мерные контейнеры, упаковки с заранее известным максимальным количеством $N$ параллелепипедов, поступающих на вход. Для алгоритма $A_{d,N}$ за $W_{d,N}\left(k\right)$ обозначим объем незаполненного параллелепипедами пространства частично заполненных контейнеров после упаковки $k\le N$ параллелепипедов с использованием алгоритма $A_{d,N}$. Плотность заполнения $d$-мерных контейнеров в работе [14] исследуется с использованием целевой функции $V_{d,N}$:

$V_{d,N}=\frac{\sum _{k=1}^N{\mathbb{E}W}_{d,N}\left(k\right)}{N}$,

где математическое ожидание вычисляется по распределению длин сторон параллелепипедов.

Онлайновые алгоритмы, работающие по данному принципу и имеющие данную целевую функцию, будем называть алгоритмами с незаданным завершением с целевой функцией типа $1$. В настоящей работе, будем также использовать следующую целевую функцию для оценки плотности заполнения контейнеров:

Данную целевую функцию будем называть целевой функцией типа $2$. Оценка плотности заполнения контейнеров по целевой функции типа $1$ никогда не превышает оценку по целевой функции типа $2$. Таким образом, наиболее строгая оценка получается с использованием целевой функции типа $2$.

В работе [17] был предложен алгоритм упаковки параллелепипедов в контейнеры с оценкой целевой функции типа $1$:

В настоящей работе, предложен алгоритм $d$-мерной упаковки параллелепипедов в контейнеры, работающий в режиме онлайн, с оценкой целевой функции второго типа

$W_{d,N}=O\left(N^{\frac{d}{d+1}}{\ln }^{\frac{3}{2\left(d+1\right)}}N\right)$,

что асимптотически улучшает оценку из работы [17].

3. Алгоритм увеличения размерности и верхние оценки $W_{d,N}$

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

3.1 Алгоритм увеличения размерности

Пусть для $d$-мерной задачи упаковки параллелепипедов в контейнеры, имеется множество алгоритмов $A_{d,M}\forall M\in \mathbb{N}$, работающих в режиме онлайн с незаданным завершением с оценкой целевой функции типа $2$:

Построим для каждого $N\in \mathbb{N}$ алгоритм $A_{d+1,N}$, также работающий в режиме онлайн, с незаданным завершением с

Идея алгоритма заключается в разбиении пространства контейнеров на области и в последующей упаковке в одну область в контейнерах одного типа параллелепипедов с близкими длинами сторон по первой координате. Пространство контейнера разбивается на $2$ области или, только для контейнеров последнего, $s+1$-го типа, контейнеры содержат единственную область.

Число типов областей составляет $2s+1$, эти области расположены в контейнерах одного из $s+1$ типов. Внутри области параллелепипеды размещаются с использованием алгоритма упаковки $A_{d,N_d\left(N\right)}$ меньшей размерности, где параметр $N_d\left(N\right)$, равный верхней оценке числа упаковываемых параллелепипедов размерности $d$, будет введен в дальнейшем.

Аналог алгоритма из [17] можно построить также по индукции. Большее асимптотическое значение объема $W_{d,N}$ незаполненного пространства для $d$-мерной задачи упаковки в контейнеры с использованием алгоритма из [17], по сравнению с предложенным в настоящей работе алгоритмом, возникает из-за более высокой асимптотики незаполненного пространства контейнеров для одномерной задачи упаковки в контейнеры: $W_{1,N}=\Theta \left(N^{\frac{2}{3}}\right)$ для алгоритма hash packing из [17], тогда как для алгоритма BF, $W_{1,N}=\Theta \left(\sqrt{N}{\ln }^{\frac{3}{4}}N\right)$.

Алгоритм увеличения размерности ${\mathit{A}}_{\mathit{d}+\mathit{1},\mathit{N}}={\mathit{A}}_{\mathit{d}+\mathit{1},\mathit{N}}\left({\mathit{A}}_{\mathit{d},N_d\left(N\right)}\right)$:

1. Зафиксируем $s=\lfloor N^{\frac{1}{d+2}}{\ln }^{-\frac{m\left(d+1\right)}{d+2}}N\rfloor$.
2. Если выпал параллелепипед $R$, длина $b_1\left(R\right)$ которого по первой координате принадлежит полуинтервалу $\left(\frac{i-1}{2s+1},\frac{i}{2s+1}\right]$, то говорим, что параллелепипед $R$ – типа $i$.
3. Размещение параллелепипеда по первой координате.

• Если тип $i$ параллелепипеда $R$ не превосходит $s$, то по первой координате, сторону параллелепипеда длиной $b_1\left(R\right)$ размещаем на интервале ${(0,b}_1\left(R\right))$ в контейнере $i$-го типа. Областью $i$-го типа назовем подмножество контейнеров $i$-го типа, значение первой координаты которых принадлежит отрезку $\left[0,\frac{i}{2s+1}\right]$.
• Если тип $i$ параллелепипеда $R$ принадлежит множеству $\left\{s+1,...,2s\right\}$, то по $1$-ой координате, сторону параллелепипеда $R$ длиной $b_1\left(R\right)$ размещаем на интервале $\left(1-\frac{2s-i}{2s+1},1-\frac{2s-i}{2s+1}+b_1\left(R\right)\right)$ в контейнере $\left(2s+1-i\right)$-го типа. Областью $i$-го типа назовем подмножество контейнеров $\left(2s+1-i\right)$-го типа, значение первой координаты которых принадлежит полуинтервалу ($\frac{2s-i}{2s+1},1]$.
• Если $i=2s+1$, то по $1$-ой координате, сторону параллелепипеда $R$ длиной $b_1\left(R\right)$ размещаем на интервале ${(0,b}_1\left(R\right))$ в контейнере $s+1$-го типа. Областью $(2s+1)$-го типа назовем множество контейнеров $(s+1)$-го типа.

Таким образом, для всех$i\in \{1,...,2s+1\}$, ширина $i$-ой области составляет $\frac{i}{2s+1}$.

4. Размещение параллелепипеда по последним $d$ координатам.

Проекцию параллелепипеда типа $i$ на последние $d$ координат, где $i\in \{1,...,2s\}$, размещаем в контейнер типа $\min \{i,2s+1-i\}$, а параллелепипед типа $2s+1$ – в контейнер типа $s+1$, используя при этом алгоритм $A_{d,N_d\left(N\right)}$ упаковки $d$-мерных параллелепипедов, которому известно, что нужно упаковать не более, чем $N_d\left(N\right)=\left(1+4N^{-\frac{d}{2\left(d+2\right)}}\sqrt{\ln N}\right)\frac{N}{2s+1}$ параллелепипедов.

Параллелепипеды различных типов упаковываем в попарно непересекающиеся области. Если алгоритм $A_{d,N_d\left(N\right)}$ для размещения проекции параллелепипеда $R$ типа $i,i\le 2s$ на последние $d$ координат $b_2\left(R\right),...,b_{d+1}\left(R\right)$, требует создания нового $d$-мерного контейнера, и при этом существует $d+1$-мерный контейнер $B$ типа $\min \{i,2s+1-i\}$ в который упакованы лишь параллелепипеды $(2s+1-i$)-го типа, то для размещения $R$ используется контейнер $B$.

На рис. 1 приведен пример построения алгоритма двумерной упаковки в контейнеры-квадраты с помощью одномерного алгоритма упаковки в контейнеры в виде отрезков с использованием алгоритма увеличения размерности.

Рис. 1. Пример построения алгоритма $A_{2,N}$ двумерной упаковки в контейнеры на основе алгоритма $A_{1,N_1\left(N\right)}$ для одномерной упаковки.

3.2 Оценка ожидаемого объема ${\mathit{W}}_{\mathit{d},\mathit{N}}$ незаполненного пространства для алгоритма увеличения размерности

В приложении 1, доказана следующая теорема, позволяющая связать плотность заполнения при упаковке с помощью алгоритма $A_{d+1,N}$ с плотностью заполнения с помощью алгоритма $A_{d,N_d\left(N\right)}$ упаковки прямоугольников в контейнеры меньшей размерности:

Теорема 1. Пусть $A_{d,M}\forall M\in \mathbb{N}$ – семейство алгоритмов с незаданным завершением для d-мерной задачи упаковки в контейнеры с оценкой целевой функции типа $2$, равной

$W_{d,M}\left(A_{d,m}\right)=O\left(M^{\frac{d}{d+1}}{\ln }^{m}M\right)\forall M\in \mathbb{N},m\ge 0$.

Тогда алгоритм $A_{d+1,N}=A_{d+1,N}\left(A_{d,N_d\left(N\right)}\right)$ для $d+1$-мерной задачи, полученный в результате применения алгоритма увеличения размерности к алгоритму $A_{d,N_d\left(N\right)}$, работает в режиме с незаданным завершением и имеет оценку целевой функции типа $2$, равную

$W_{d+1,N}\left(A_{d+1,N}\right)=O\left(N^{\frac{d+1}{d+2}}{\ln }^{\frac{m\left(d+1\right)}{d+2}}N\right)$.

Как следствие, применяя последовательно $d-1$ раз алгоритм увеличения размерности $A_{d,N}\left(A_{d-1,N_{d-1}\left(N\right)}\left(A_{d-2,N_{d-2}\left(N_{d-1}\left(N\right)\right)}\left(...\right)\right)\right)$ к алгоритму $A_1$ для одномерной задачи упаковки в контейнеры, получаем следующую теорему:

Теорема 2. Пусть для одномерной задачи упаковки в контейнеры, существует алгоритм $A_{1,N}$ с незаданным завершением, целевая функция типа $2$ для которого равна $W_{1,N}\left(A_{1,N}\right)=O\left(\sqrt{N}{\ln }^{m}N\right),m\ge 0$ при упаковке не более $N$ объектов случайного размера, имеющего равномерное на $\left(\mathrm{0,1}\right]$ распределение.

Тогда для каждого натурального $d\ge 1$, существует алгоритм $A_{d,N}$ с незаданным завершением для $d$-мерной задачи упаковки в контейнеры, полученный в результате применения алгоритма увеличения размерности $d-1$ раза к алгоритму $A_1$, со следующей асимптотической оценкой целевой функцией типа $2$:

Как показано в работе [16], для стандартной онлайновой эвристики с незаданным завершением BF упаковки в одномерные контейнеры, верна оценка для целевой функции второго типа:

$W_1^{\mathrm{BF}}=W_{1,N}^{\mathrm{BF}}=O\left(\sqrt{N}{\ln }^{\frac{3}{4}}N\right)\forall N$,

причем верхняя оценка числа упаковываемых объектов $N$ алгоритму BF неизвестна. Следовательно, по теореме $2$, на основе одномерного алгоритма BF, можно построить алгоритм с незаданным завершением $d$-мерной упаковки $A_{d,N}\left(A_{d-1,N_{d-1}\left(N\right)}\left(...\left(\mathrm{BF}\right)...\right)\right)$ с оценкой целевой функции типа $2$:

Такие алгоритмы будем называть алгоритмами увеличения размерности от BF (алгоритмами увеличения размерности (BF), или а.у.р.(BF)) размерности $d$.

3.3 Обобщение алгоритма увеличения размерности

Основным недостатком анализа алгоритмов упаковки в среднем случае является ограниченная практическая применимость, возникающая вследствие предположения о фиксированном распределении, или семействе распределений длин сторон параллелепипедов. Данное предположение может не выполняться на практике.

Алгоритм увеличения размерности может легко быть обобщен на случай любого заранее известного распределения длин сторон $d$-мерных параллелепипедов в том случае, когда длины сторон параллелепипедов независимы в совокупности. Для этого, аналогично случаю равномерного распределения длин сторон параллелепипедов, сначала выберем количество областей для упаковки параллелепипедов по первой координате, равное $2s+1$ в зависимости от верхней оценки $N$ числа упаковываемых параллелепипедов. Ширина $i$-ой области изменится с $\frac{i}{2s+1}$ до значения $i$-ого $2s+1$-квантиля распределения $1$-ой стороны параллелепипедов (т.е. такого значения, которое первая координата параллелепипеда не превосходит с вероятностью $\frac{i}{2s+1}$) при изменении этого распределения с равномерного на общий случай распределения. Заметим также, что $\frac{i}{2s+1}$ является $i$-ым $2s+1$-квантилем равномерного на $\left(\mathrm{0,1}\right]$ распределения. Данные квантили упакуем в режиме оффлайн в как можно меньшее количество контейнеров единичного размера. После чего, аналогично алгоритму увеличения размерности в случае равномерного распределения длин сторон параллелепипедов, в каждую из получившихся областей упаковываем параллелепипеды по оставшимся $d-1$ сторонам, используя алгоритм для упаковки объектов меньшей на $1$ размерности.

В следующем разделе приведены результаты вычислительных экспериментов, позволяющие сравнить алгоритмы увеличения размерности от BF с алгоритмом из работы [17] для многомерной задачи упаковки в контейнеры. Также, на примере двумерной задачи, покажем, что предложенный алгоритм увеличения размерности позволяет эффективно упаковывать в контейнеры объекты параллелепипеды с неравномерным распределением длин сторон.

4. Результаты вычислительных экспериментов

В приложении 1 при доказательстве теоремы 1, были выделены $3$ типа незаполненного пространства контейнеров. При росте числа упаковываемых параллелепипедов $n\in \left\{1,...,N\right\}$, математическое ожидание объема незаполненного пространства контейнеров каждого из $3$ типов не убывает. Поэтому, при численном моделировании, достаточно вместо $W_{d,N}=\underset{1\le n\le N}{\max }\mathbb{E}{W}_{d,N}\left(n\right)$, вычислять $\mathbb{E}{W}_{d,N}\left(N\right)$.

Проведем численные эксперименты.

Вычислим математическое ожидание $W_{2,N}\left(N\right)$ для алгоритма двумерной упаковки $A_{2,N}=A_{2,N}\left(\mathrm{BF}\right)$ и для алгоритма трехмерной упаковки $A_{3,N}=A_{3,N}\left(A_{2,N_2\left(N\right)}\left(\mathrm{BF}\right)\right)$, полученных применением алгоритма увеличения размерности к алгоритму BF для одномерной упаковки, и сравним результаты с $\mathbb{E}{W}_{d,N}\left(N\right)$ для алгоритмов hash packing из [17] соответствующей размерности $d\in \left\{2,3\right\}$. Также сравним адаптивную версию алгоритма увеличения размерности с алгоритмом hash packing при упаковке двумерных параллелепипедов, имеющих гауссовское распределение длин сторон.

4.1 Анализ алгоритма увеличения размерности для двумерной задачи

Проведем численный анализ алгоритма а.у.р.(BF), полученного в результате однократного применения алгоритма увеличения размерности к алгоритму BF для одномерной задачи упаковки в контейнеры. Сравним плотность заполнения контейнеров после применения алгоритма увеличения размерности от BF и после применения алгоритма hash packing.

Из теоретических результатов следует, что асимптотика $\mathbb{E}{W}_{2,N}^{\mathrm{HP}}\left(N\right)$ алгоритма hash packing для двумерной задачи составляет $\mathbb{E}{W}_{2,N}^{\mathrm{HP}}\left(N\right)=\Theta \left(N^{\frac{3}{4}}\right)$, а асимптотика алгоритма увеличения размерности от BF составляет $\mathbb{E}{W}_{2,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)=O\left(N^{\frac{2}{3}}\sqrt{\ln N}\right)$. Таким образом, $\mathbb{E}{W}_{2,N}^{\mathrm{HP}}\left(N\right)/\mathbb{E}{W}_{2,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)=\Omega \left(\frac{N^{\frac{1}{12}}}{\sqrt{\ln N}}\right)$, причем $\frac{N^{\frac{1}{12}}}{\sqrt{\ln N}}=0.85$ при $N=10^6$.

В результате вычислительных экспериментов установлено (рис. 2), что при числе параллелепипедов $N$ из отрезка $\left[50,10^6\right]$, величина $\frac{\mathbb{E}{W}_{2,N}^{\mathrm{HP}}\left(N\right)}{\mathbb{E}{W}_{2,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)}$ изменяется от $1.60$ при $N=50$ до $1.95$ при $N=10^6$, причем при $N=10^4$, данная величина составляет $1.69$. Для всех $N$, а.у.р.(BF) позволяет получить меньшее математическое ожидание объема незаполненного пространства, чем алгоритм hash packing.

4.2 Анализ алгоритма увеличения размерности для трехмерной задачи

Сравним алгоритм увеличения размерности от BF и алгоритм hash packing для упаковки параллелепипедов в трехмерные контейнеры.

Из теоретических результатов следует, что асимптотика $\mathbb{E}{W}_{3,N}^{\mathrm{HP}}\left(N\right)$ алгоритма hash packing для трехмерной задачи составляет $\mathbb{E}{W}_{3,N}^{\mathrm{HP}}\left(N\right)=\Theta \left(N^{\frac{4}{5}}\right)$, а асимптотика алгоритма увеличения размерности от BF составляет $\mathbb{E}{W}_{3,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)=O\left(N^{\frac{3}{4}}{\ln }^{\frac{3}{8}}N\right)$. Таким образом, $\mathbb{E}{W}_{3,N}^{\mathrm{HP}}\left(N\right)/\mathbb{E}{W}_{3,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)=\Omega \left(N^{\frac{1}{20}}{\ln }^{-\frac{3}{8}}N\right)$, причем $N^{1/20}{\ln }^{-3/8}N=0.75$ при $N=10^6$.

В результате вычислительных экспериментов установлено (рис. 3), что при числе параллелепипедов $N$ из отрезка $\left[50,10^6\right]$, величина $\frac{\mathbb{E}{W}_{3,N}^{\mathrm{HP}}\left(N\right)}{\mathbb{E}{W}_{3,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)}$ изменяется от $2.81$ при $N=50$ до $2.55$ при $N=10^6$, причем при $N=10^4$, данная величина составляет $2.47$.

Рис. 2. Сравнение а.у.р.(BF) и hash packing для двумерной задачи упаковки в контейнеры.

Рис. 3. Сравнение а.у.р.(BF) и hash packing для трехмерной задачи упаковки в контейнеры.

4.3 Анализ алгоритма увеличения размерности в случае неравномерного распределения длин сторон параллелепипедов

При анализе алгоритмов упаковки в среднем случае, делается предположение о том, что входные данные имеют равномерное распределение. Это может вызывать “переобучение” алгоритма, когда малый объем незаполненного пространства достигается лишь в случае фиксированного распределения, или семейства распределений длин сторон параллелепипедов. Это, в свою очередь, может ограничивать практическое применение алгоритмов упаковки, показывающих высокую плотность упаковки при анализе в среднем.

Проведем численные эксперименты для двумерной задачи упаковки в контейнеры, в которых параллелепипеды имеют гауссовское распределение длин сторон. Сравним алгоритм увеличения размерности и hash packing в этом случае.

В результате вычислительных экспериментов установлено (рис. 4), что при числе параллелепипедов $N$ из отрезка $\left[50,10^6\right]$, величина $\frac{\mathbb{E}{W}_{2,N}^{\mathrm{HP}}\left(N\right)}{\mathbb{E}{W}_{2,N}^{а.у.р.\left(\mathrm{BF}\right)}\left(N\right)}$ изменяется от $2.56$ при $N=50$ до $21.5$ при $N=10^6$, причем при $N=10^4$, данная величина составляет $11.8$. Это показывает, что а.у.р.(BF) был эффективно обобщен на случай неравномерного распределения длин сторон параллелепипедов, и в этом случае а.у.р.(BF) на порядок превосходит алгоритм hash packing по плотности упаковки.

Рис. 4. Сравнение а.у.р.(BF) и hash packing в случае неравномерного распределения длин сторон параллелепипедов.

5. Заключение

Была рассмотрена задача многомерной упаковки параллелепипедов в контейнеры. Лучшая из известных асимптотических оценок математического ожидания $d$-мерного объема не заполненной параллелепипедами части частично заполненных контейнеров при анализе в среднем для алгоритмов, работающих в режиме онлайн с незаданным завершением для d-мерной задачи, улучшена с $\Theta \left(N^{\frac{d+1}{d+2}}\right)$ до $O\left(N^{\frac{d}{d+1}}{\ln }^{\frac{3}{2\left(d+1\right)}}N\right)$.

Численные эксперименты подтверждают теоретический результат. Показано, что предложенный алгоритм, названный алгоритмом увеличения от алгоритма BF размерности $d$, имеет меньшее математическое ожидание незаполненного объема контейнеров, чем лучший ранее известный алгоритм hash packing для размерностей $2$ и $3$ при числе испытаний от $50$ до $10^6$. Также показано, что предложенный алгоритм увеличения размерности может быть эффективно обобщен со случая равномерного распределения длин сторон параллелепипедов на случай общего распределения, позволяя получить меньшее математическое ожидание объема незаполненного пространства, чем алгоритм hash packing.

Список литературы

1. Johnson, David S., et al. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on computing 3.4, 1974, pp. 299-325. DOI: 10.1137/0203025. ↩1 ↩2
2. Coffman Jr, Edward G., Michael R. Garey, and David S. Johnson. Approximation algorithms for bin-packing—an updated survey. Algorithm design for computer system design. Springer Vienna, 1984, pp. 49-106. DOI: 10.1007/978-3-7091-4338-4. ↩
3. Li, Xueping, and Kaike Zhang. Single batch processing machine scheduling with two-dimensional bin packing constraints. International Journal of Production Economics 196, 2018, pp. 113-121. DOI: 10.1016/j.ijpe.2017.11.015. ↩
4. Paquay, Célia, Michael Schyns, and Sabine Limbourg. A mixed integer programming formulation for the three‐dimensional bin packing problem deriving from an air cargo application. International Transactions in Operational Research 23.1-2, 2016, pp. 187-213. DOI: 10.1111/itor.12111. ↩
5. Tchernykh, Andrei, et al. On-line hierarchical job scheduling on grids with admissible allocation. Journal of Scheduling 13.5, 2010, pp. 545-552. DOI: 10.1007/s10951-010-0169-x. ↩
6. Tchernykh, Andrei, et al. Two level job-scheduling strategies for a computational grid. International Conference on Parallel Processing and Applied Mathematics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 774-781. DOI: 10.1007/11752578_93.
7. Gohil, Bhavesh, et al. A comparative analysis of virtual machine placement techniques in the cloud environment. International Journal of Computer Applications 156.14, 2016, pp. 12-18. DOI: 0.5120/ijca2016912530. ↩
8. Garey, Michael R., and David S. Johnson. Computers and intractability. Vol. 29. New York: wh freeman, 2002. 338 pp. ↩
9. Brown, Donna J. A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms. No. ACT19. 1979, pp. 1-21. DOI: 10.1016/S0020-0190(80)90077-0. ↩
10. van Vliet, André. An improved lower bound for on-line bin packing algorithms. Information processing letters 43.5, 1992, pp. 277-284. DOI: 10.1016/0020-0190(92)90223-I. ↩
11. Galambos, Gabor, and André van Vliet. Lower bounds for 1-, 2-and 3-dimensional on-line bin packing algorithms. Computing 52.3, 1994, pp. 281-297. DOI: 10.1007/BF02246509. ↩
12. Han, Xin, et al. A new upper bound 2.5545 on 2d online bin packing. ACM Transactions on Algorithms (TALG) 7.4, 2011, pp. 1-18. DOI: 10.1145/2000807.2000818. ↩
13. Csirik, János, and André Van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters 13.3, 1993, pp. 149-158. DOI: 10.1016/0167-6377(93)90004-Z. ↩1 ↩2
14. Shor, Peter W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6.2, 1986, pp. 179-200. DOI: 10.1007/BF02579171. ↩1 ↩2 ↩3 ↩4
15. Shor, Peter W. How to pack better than best fit: tight bounds for average-case online bin packing. Proceedings 32nd Annual Symposium of Foundations of Computer Science, IEEE Computer Society, 1991, pp. 752-759, DOI: 10.1109/SFCS.1991.185444. ↩
16. Leighton, Frank Thomson, and Peter Shor. Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms. Proceedings of the eighteenth Annual ACM symposium on theory of computing, 1986, pp. 91-103, DOI: 10.1145/12130.12140. ↩1 ↩2
17. Chang, Ee-Chien, Weiguo Wang, and Mohan S. Kankanhalli. Multidimensional on-line bin-packing: An algorithm and its average-case analysis. Information Processing Letters 48.3, 1993, pp. 121-125. DOI: 10.1016/0020-0190(93)90253-6. ↩1 ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8
18. Chung, Fan, and Linyuan Lu. Connected components in random graphs with given expected degree sequences. Annals of combinatorics 6.2, 2002, pp. 125-145. DOI: 10.1007/PL00012580. ↩

Приложение 1. Доказательство теоремы 1

Докажем теорему 1. Для этого, приведем и докажем несколько лемм.

В работе [18] было доказано следующее ограничение сверху отклонения суммы биномиальных случайных величин от ее математического ожидания:

Лемма 1 (Chung, Lu, 2002). Пусть $X_1,...,X_n$ – независимые в совокупности случайные величины, имеющие распределение Бернулли. Принимаемые значения принадлежат множеству {0, 1}, $\mathrm{Pr}\left(X_i=1\right)=p_i$, а $\mathrm{Pr}\left(X_i=0\right)={1-p}_i$. Выберем значения ${\alpha }_i\ge 0\forall i\in \left\{1,2,...,n\right\}$. Определим значения $X=\sum _{i=1}^n{\alpha }_i{X}_i$ и $\nu =\sum _{i=1}^n{\alpha }_i^2{p}_i$. Тогда для каждого $\lambda \ge 0$, выполняется следующее неравенство:

Для доказательства теоремы 1, требуется следующее следствие леммы 1:

Следствие 1. Для каждого $\epsilon \in \left[0,1\right]$, для случайной биномиально распределенной величины $\mathrm{Bin}(n,p)$, выполняется

Доказательство. Биномиальная случайная величина $\mathrm{Bin}\left(n,p\right)$ представима в виде суммы $n$ независимых в совокупности случайных величин, имеющих распределение Бернулли: $\mathrm{Bin}\left(n,p\right)=\sum _{i=1}^n{X}_i$, где $\mathrm{Pr}\left(X_i=1\right)=p$, $\mathrm{Pr}\left(X_i=0\right)=1-p$ для всех $i\in \left\{1,...,n\right\}$.

Используя лемму 1 при значениях параметров ${\alpha }_i=1,p_i=p\forall i\in \{1,...,n\}$, и при значении $X=\mathrm{Bin}\left(n,p\right),\mathbb{E}X=\mathrm{np},\lambda =\mathrm{\epsilon np},\nu =\mathrm{np}$, получим

Лемма 2. Пусть $X$ – случайная величина, $\mathbb{E}X$ – ее математическое ожидание и $\mathrm{Var}\left(X\right)$ – ее дисперсия. Тогда

Доказательство. $\mathrm{Var}\left(\left|X-\mathbb{E}X\right|\right)=\mathbb{E}(X-\mathbb{E}X{)}^2-{\mathbb{E}}^2\left|X-\mathbb{E}X\right|\ge 0$.

Следовательно, ${\mathbb{E}}^2|X-\mathbb{E}X|\le \mathbb{E}(X-\mathbb{E}X{)}^2=\mathrm{Var}(X)⎕$

Лемма 3. Обозначим за $V_i\left(k\right)$ сумму $d$-мерных объемов проекций $d+1$-мерных параллелепипедов на подпространство, образованное последними $d$ координатами тех из $k$ случайных параллелепипедов, которые имеют тип $i$ для фиксированного типа $i\in \left\{1,...,2s+1\right\}$ (см. алгоритм увеличения размерности). Тогда верно следующее неравенство:

$\mathrm{Var}\left(V_i\left(k\right)\right)\le 2\mathrm{pk}$,

где $p=\frac{1}{2s+1}$ – вероятность того, что случайный параллелепипед имеет тип $i$.

Доказательство. $V_i\left(1\right)=\mathrm{Bin}\left(1,p\right)\prod _{i=1}^d{\xi }_i=\mathrm{Bin}\left(1,p\right)U_d$, где $\mathrm{Bin}\left(n,p\right)$ – случайная величина, имеющая биномиальное распределение с параметрами $n$ и $p$, равными числу экспериментов и вероятности успешности каждого эксперимента соответственно, ${\xi }_i$ – случайная величина, имеющая равномерное на $\left[\mathrm{0,1}\right]$ распределение, $U_d=\prod _{i=1}^d{\xi }_i$ – случайная величина, равная объему $d$-мерного параллелепипеда.

Так как $\mathbb{E}\mathrm{Bin}\left(1,p\right)=p$, $0\le U_d\le 1$, и длины сторон параллелепипедов – независимые в совокупности случайные величины, то

Используя формулу для дисперсии произведения двух независимых случайных величин, $\mathrm{Var}\left(\mathrm{XY}\right)=\mathrm{Var}\left(X\right)\mathrm{Var}\left(Y\right)+\mathrm{Var}\left(X\right){\mathbb{E}}^{2}Y+\mathrm{Var}\left(Y\right){\mathbb{E}}^{2}X$, и соотношения $\mathrm{Var}\left(\mathrm{Bin}\left(1,p\right)\right)=p\left(1-p\right),\mathbb{E}\mathrm{Bin}\left(1,p\right)=p$ и $\mathrm{Var}\left(U_d\right)\le \mathrm{1,0}\le \mathbb{E}{U}_d\le 1$, получим

В силу независимости в совокупности длин сторон параллелепипедов, получим требуемое неравенство:

Теорема 1. Пусть $A_{d,M},\forall M\in \mathbb{N}$ – семейство алгоритмов с незаданным завершением для $d$-мерной задачи с оценкой целевой функции типа 2, равной

Тогда алгоритм $A_{d+1,N}=A_{d+1,N}\left(A_{d,N_d\left(N\right)}\right)$ для $d+1$-мерной задачи, полученный в результате применения алгоритма увеличения размерности к алгоритму $A_{d,N_d\left(N\right)}$, где $N_d\left(N\right)$ – параметр, введенный в разделе 3.1. настоящей работы в алгоритме увеличения размерности. Алгоритм $A_{d+1,N}$ работает в режиме с незаданным завершением и имеет оценку целевой функции типа 2

$W_{d+1,N}\left(A_{d+1,N}\right)=O\left(N^{\frac{d+1}{d+2}}{\ln }^{\frac{m\left(d+1\right)}{d+2}}N\right)$.

Введем обозначения в предположении, что выпало $k\le N$ параллелепипедов:

• $w_i=w_i\left(k\right)$ – $d$-мерный объем незаполненного пространства контейнеров при упаковке параллелепипедов типа $i$ алгоритмом $A_{d,N_d\left(N\right)}$ в $d$-мерные контейнеры,
• $n_i=n_i\left(k\right)$ – число $d$-мерных контейнеров, заполненных проекциями параллелепипедов типа $i$ на последние $d$ координат при размещении проекций с помощью алгоритма $A_{d,N_d\left(N\right)}$,
• $m_i=m_i\left(k\right)$ – число выпавших параллелепипедов типа $i$,
• $W_{d+1,N}\left(k\right)$ – $d+1$-мерный объем незаполненной части контейнеров после упаковки $k$ параллелепипедов алгоритмом $A_{d+1,N}$,
• $K_k$ – количество $d+1$-мерных контейнеров, использованных алгоритмом $A_{d+1,N}$ для упаковки $k$ параллелепипедов,
• $V_i\left(k\right)$ – сумма $d$-мерных объемов проекций на подпространство, образованное последними $d$ координатами тех из $k$ случайных параллелепипедов, которые имеют тип $i$ для некоторого фиксированного типа $i\in \left\{1,...,2s+1\right\}$.

Доказательство.

В формуле (1), первое слагаемое $\frac{2K_k}{2s+1}$ (потери типа 1), ограничивает сверху объем незаполненной части частично заполненных $d+1$-мерных контейнеров, связанный с тем, что у $d+1$-мерного параллелепипеда $R$ типа i, длина $b_1\left(R\right)$ первой стороны принадлежит полуинтервалу $\left(\frac{i-1}{2s+1},\frac{i}{2s+1}\right]$ длиной $\frac{1}{2s+1}$.

Также из определения $K_k$, следует следующее неравенство:

Множитель $2$ в первом слагаемом формулы (1) возникает, т.к. каждый контейнер разбит не более, чем на $2$ области (см. рис. 1).

Слагаемое$\sum _{i=1}^{2s+1}{w}_i$ (потери типа 2) – ограничивает сверху суммарный объем незаполненного пространства контейнеров, заполненных параллелепипедами типа $i$ без учета потерь типа 1.

Слагаемое $\sum _{i=1}^s|n_i-n_{2s+1-i}|$ (потери типа 3) – ограничивает сверху объем частей контейнеров, заполненных параллелепипедами типа $i$, но не заполненных параллелепипедами типа $2s+1-i$, $i\in \left\{1,...,s\right\}$.

Примеры различных типов потерь для пары соседних областей в $2$-мерном случае изображены на рис. 5.

Рис.5. Пример различных типов незаполненного пространства контейнеров.

Из формулы (1) с применением формул (2) и (3), получаем:

Следовательно,

1. Оценим первое слагаемое формулы 4, учитывая, что $s=\lfloor N^{1/(d+2)}{\ln }^{-m(d+1)/(d+2)}N\rfloor$:

2. Оценим второе слагаемое: При достаточно больших $N$, $4\sqrt{\ln N}{N}^{-d/2(d+2)}\le 1$. Таким образом, согласно следствию 1 леммы 1,

для достаточно больших $N$. Следовательно, вклад в мат. ожидание ${\mathbb{E}W}_{d,N}\left(k\right)$ тех случаев, когда хотя бы одного типа $i$, число выпавших параллелепипедов $m_i$ этого типа больше, чем $\left(1+4\sqrt{\ln N}{N}^{-\frac{d}{2\left(d+2\right)}}\right)\frac{N}{2s+1}$, равен $o\left(1\right)$. При достаточно больших $N$, выполняется $4\sqrt{\ln N}{N}^{-d/2(d+2)}\le 1$. Таким образом,

в предположении, что для алгоритма $A_{d,N_d\left(N\right)}$, количество упаковываемых параллелепипедов $N_d\left(N\right)=\left(1+4\sqrt{\ln N}{N}^{-\frac{d}{2\left(d+2\right)}}\right)\frac{N}{2s+1}$, не превышает $2N/(2s+1)$.

3. Оценим третье слагаемое формулы (4). Так как $i\in \{1,...,2s+1\}$, $\mathbb{E}{V}_i\left(k\right)=\frac{k}{2s+1}$,

Таким образом,

Значит, каждое слагаемое имеет асимптотическую оценку $O\left(N^{\frac{d+1}{d+2}}{\ln }^{\frac{m\left(d+1\right)}{d+2}}N\right)$. Следовательно, выполняется искомое соотношение

Информация об авторах

Денис Олегович ЛАЗАРЕВ является специалистом отдела теоретической информатики Института системного программирования им. В.П. Иванникова РАН. Научные интересы включают машинное обучение, вероятностный метод и алгоритмы упаковки.

Александр Владимирович ШОКУРОВ – кандидат физико-математических наук, доцент, заведующий отделом теоретической информатики Института системного программирования им. В.П. Иванникова РАН с 2019 года. Сфера научных интересов: алгебраические структуры в полях Галуа, базисы Гребнера, модулярная арифметика, нейрокомпьютерные технологии, цифровая обработка сигналов, криптографические методы защиты информации.