Русская Википедия:Задача об упаковке в контейнеры
Задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.
Разновидности и методы решения задач упаковки
Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т. п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т. д. Так как задача является NP-трудной, то использование точного переборного алгоритма возможно только при небольших размерностях. Обычно для решения задачи используют эвристические приближённые полиномиальные алгоритмы.
Задача упаковки в одномерные одинаковые контейнеры
Постановка задачи
Пусть дано множество контейнеров размера <math>V</math> и множество <math>n</math> предметов размеров <math>a_1,\dots,a_n</math>. Надо найти целое число контейнеров <math>B</math> и разбиение множества <math>\{1,\dots,n\}</math> на <math>B</math> подмножеств <math>S_1 \cup \dots \cup S_B</math> таких, что <math>\sum_{i \in S_k} a_i \leq V</math> для всех <math>k=1,\dots,B</math>. Решение называется оптимальным, если <math>B</math> минимально. Минимальное <math>B</math> далее обозначается OPT.
Упаковка как задача целочисленного программирования
Задача упаковки в контейнеры может быть сформулирована как задача целочисленного программирования следующим образом:
| Минимизировать <math> B = \sum_{i=1}^n y_i</math> | ||
| при ограничениях | <math>\sum_{j=1}^n a_j x_{ij} \leq V y_i,</math> | <math>\forall i \in \{1,\ldots,n\}</math> |
| <math>\sum_{i=1}^n x_{ij} = 1,</math> | <math>\forall j \in \{1,\ldots,n\}</math> | |
| <math> y_i \in \{0,1\},</math> | <math>\forall i \in \{1,\ldots,n\}</math> | |
| <math> x_{ij} \in \{0,1\},</math> | <math>\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}</math> | |
где <math> y_i = 1</math>, если контейнер <math>i</math> используется и <math> x_{ij} = 1</math>, если предмет <math>j</math> помещён в контейнер <math>i</math>.[1]
Приближённые полиномиальные алгоритмы
Простейшими полиномиальными алгоритмами упаковки являются алгоритмы Best Fit Decreasing — BFD (Наилучший подходящий по убыванию) и First Fit Decreasing — FFD (Первый подходящий по убыванию). Предметы упорядочивают по невозрастанию размеров и последовательно пакуют либо в контейнер, в котором после упаковки останется наименьший свободный объём — BFD, либо в первый контейнер куда он помещается — FFD. Доказано, что эти алгоритмы используют не более
<math>\frac{11}{9}OPT + 1</math>
контейнеров[2].
Однако для задачи упаковки существуют и асимптотически ε -оптимальные полиномиальные алгоритмы.
Задача определения, равно ли OPT двум или трем является NP-трудной. Поэтому для любого ε > 0, трудно упаковать предметы в (3/2 − ε)OPT контейнеров. (Если такой полиномиальный алгоритм существует, то за полиномиальное время можно определить разделятся ли n неотрицательных чисел на два множества с одинаковой суммой элементов. Однако известно, что эта проблема NP-трудна.) Следовательно, если P не совпадает с NP, то для задачи упаковки в контейнеры нет алгоритма приближенной схемы полиномиального времени (PTAS). С другой стороны, для всякого ε >0 можно найти решение с не более, чем (1 + ε)OPT + 1 контейнерами за полиномиальное время. Такие алгоритмы относятся к асимптотической PTAS.[3] Но поскольку в оценке сложности этого класса алгоритмов <math> a n^b</math> обе константы произвольно зависят от ε, подобные алгоритмы в отличие от FFD и BFD могут быть практически бесполезными.
Вероятностный подход
Для некоторого класса вероятностных распределений размеров упаковываемых предметов, включающего функции распределения выпуклые вверх и вниз, существует практический полиномиальный алгоритм упаковки асимптотически оптимальный почти наверное при неограниченном росте числа предметов. Для распределений не входящих в этот класс могут строиться индивидуальные полиномиальные асимптотически оптимальные алгоритмы.[4]
Примечания
См. также
Шаблон:Задачи упаковки Шаблон:NP-полные задачи
