Алгоритм для многомерной упаковки в контейнеры и его вероятностный анализ

Алгоритм для многомерной упаковки в контейнеры и его вероятностный анализ

Лазарев Д.О. (ИСП РАН, Москва, Россия; НИУ МФТИ, Московская. обл., Россия)

Аннотация

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

Ключевые слова

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

Издание

Труды Института системного программирования РАН, том 38, вып. 2, 2026, стр. 35-52.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

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

Для цитирования

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

Полный текст статьи в формате pdf Вернуться к содержанию тома