Генеральный директор ЗАО "Пакер 3Д" Виктор Псиола выступил на Мехмате МГУ им. М.Ломоносова с докладом «Об одном приближении плотной упаковки»
Аннотация доклада.
Основной целью исследований, результаты которых представляются в докладе, является разработка и программная реализация алгоритма для решения задачи «укладки предметов в контейнеры» в 2- и 3-мерных случаях, основанного на моделировании рассуждений человека при решении этих задач. Задача «укладки предметов» является обобщением одномерных задач «о рюкзаке» и «упаковке в контейнеры» на 2- и 3-мерные случаи. Она включает в себя как нахождение плотной расстановки предметов в одном контейнере, так и распределение предметов по контейнерам с целью минимизации их количества.
Предложен алгоритм, основанный на использовании эвристических функционалов качества объектов исследования для их выбора среди множества других на каждом этапе. Идея заключается в сведении задачи к 2-мерному случаю путем выбора ровной поверхности среди уже установленных предметов и установки туда предметов одной высоты. Эвристические функционалы качества используются для выбора области 2-мерной укладки во всех возможных, выбора набора предметов одной высоты для установки в эту область, выбора предмета для укладки в рамках 2-мерного алгоритма и выбора наилучшей позиции этого предмета.
В докладе будут проведены подробные теоретические и экспериментальные оценки скорости и качества работы предложенного алгоритма. Для 2- и 3-мерных алгоритмов вычислены теоретические оценки времени работы от количества предметов в задаче: O(N4) и O(N5) соответственно. Экспериментальные оценки качества алгоритма продемонстрируют среднюю плотность заполнения контейнеров алгоритмом в 80% - 90%, что является очень хорошим результатом для большинства практических задач.
