Конструирование прямоугольных упаковок: алгоритм “перестройки” на базе блочных структур

Рассматриваются задачи ортогональной упаковки прямоугольников в заданной области. Известны многие однопроходные эвристические методы их решения. Они служат в качестве декодеров в алгоритмах локального поиска оптимума. Некоторые из них применяются в качестве конструктивных эвристик. В том и другом случаях полезно применение гибридных методов с включением приемов, улучшающих качество упаковки. Обоснован и описан один из таких приемов – алгоритм “перестройки”. Для его реализации удалось построить алгоритм с линейной вычислительной сложностью. Приведены результаты численного эксперимента.