Сборники трудов ИСП РАН


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

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

Аннотация

В 2012 году М. А. Трушников предложил принципиально новый онлайновый алгоритм упаковки прямоугольников в полосу, а в 2013 году была получена оценка точности алгоритма в среднем, равной математическому ожиданию незаполненной прямоугольниками площади, равная O(√N(lnN)^(3/2)). Ранее известная оценка O(N^(2/3)) была существенно улучшена. В настоящей работе данная оценка улучшена до O(√N lnN), а также алгоритм Трушникова обобщён на случай упаковки N прямоугольников в k полос, k≤√N, с сохранением оценки O(√N lnN).

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

новая эвристика, задача упаковки прямоугольников в полосу, задача упаковки прямоугольников в несколько полос, оценка в среднем

Издание

Труды Института системного программирования РАН, том 29, вып. 6, 2017, стр. 221-228.

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

DOI: 10.15514/ISPRAS-2017-29(6)-13

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