Позволять быть набором прямоугольные формы. За а также , описывает длину в измерении , То же обозначение используется для контейнера, задача об ортогональной упаковке (OPP-) решить, помещается в контейнер без перекрытия. Формально говоря, проблема состоит в том, чтобы выяснить, существует функция такой, что а также , , ,
Задача является NP-полной (см. Fekete SP, Schepers J. "О многомерной упаковке I: моделирование". Технический отчет 97–288, University of zu Köln, 1997). Проблема является NP-полной даже для, Мне интересно, является ли проблема ортогональной упаковки для ограниченного числа типов (т.е. размеров в каждом измерении) предметов до сих пор NP-полной или нет. До сих пор я нашел результат в какой-то статье о NP-полноте упаковки квадратов в квадрат (см. ДЖОЗЕФ Ю.Т. ЛЕНГ, ТОММИ В. ТАМ И С.С. ВОНГ, «Упаковка квадратов в квадрат», Журнал параллельных и распределенных вычислений, Том 10, выпуск 3, ноябрь 1990 г.), который уже является ограничением, но я до сих пор не знаю, что происходит, когда количество типов элементов ограничено.
Спасибо за ваш ответ,
Ответы:
Я думаю, что статья Клауса Янсена и Роберто Солис-Обы « Алгоритм OPT + 1 для решения проблемы режущего материала с постоянным числом длин объекта » частично отвечает на ваш вопрос. Они рассматривают особый случай вашей проблемы, известный как проблема Cutting Stock, когда число различных типов объектов постоянно и определяется следующим образом:
Авторы утверждают, что
И они предлагаютOPT+1 аппроксимационный алгоритм полиномиального времени, когда d фиксированный.
Поскольку не доказано, что этот особый случайP это доказательство того, что ваша проблема NP -жесткий.
Приложение: это известно , что в случае с двумя типами объектов (d=2 ) полиномиально разрешима, но для d=3 там известно только OPT+1 -приближение.
источник