Задача об упаковке в контейнеры

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.

Разновидности и методы решения задач упаковки[править | править вики-текст]

Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т. п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т. д. Так как задача является NP-трудной, то использование точного переборного алгоритма возможно только при небольших размерностях. Обычно для решения задачи используют эвристические приближённые полиномиальные алгоритмы.

Задача упаковки в одномерные одинаковые контейнеры[править | править вики-текст]

Постановка задачи[править | править вики-текст]

Пусть дано множество контейнеров размера V и множество n предметов размеров a_1,\dots,a_n. Надо найти целое число контейнеров B и разбиение множества \{1,\dots,n\} на B подмножеств S_1 \cup \dots \cup S_B таких, что \sum_{i \in S_k} a_i \leq V для всех k=1,\dots,B. Решение называется оптимальным, если B минимально. Минимальное B далее обозначается OPT.

Упаковка как задача линейного программирования[править | править вики-текст]

Задача упаковки в контейнеры может быть сформулирована как задача линейного программирования следующим образом:

Минимизировать  B = \sum_{i=1}^n y_i
при ограничениях \sum_{j=1}^n a_j x_{ij} \leq V y_i, \forall i \in \{1,\ldots,n\}
\sum_{i=1}^n x_{ij} = 1, \forall j \in \{1,\ldots,n\}
 y_i \in \{0,1\}, \forall i \in \{1,\ldots,n\}
 x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}

где  y_i = 1, если контейнер i используется и  x_{ij} = 1, если предмет j помещён в контейнер i.[1]

Приближённые полиномиальные алгоритмы[править | править вики-текст]

Простейшими полиномиальными алгоритмами упаковки являются алгоритмы Best Fit Decreasing — BFD (Наилучший подходящий по убыванию) и First Fit Decreasing — FFD (Первый подходящий по убыванию). Предметы упорядочивают по невозрастанию размеров и последовательно пакуют либо в контейнер, в котором после упаковки останется наименьший свободный объём — BFD, либо в первый контейнер куда он помещается — FFD. Доказано, что эти алгоритмы используют не более

\frac{11}{9}OPT + 1

контейнеров[2].

Однако для задачи упаковки существуют и асимптотически ε -оптимальные полиномиальные алгоритмы.

Задача определения, равно ли OPT двум или трем является NP-трудной. Поэтому для любого ε > 0, трудно упаковать предметы в (3/2 − ε)OPT контейнеров. (Если такой полиномиальный алгоритм существует, то за полиномиальное время можно определить разделятся ли n неотрицательных чисел на два множества с одинаковой суммой элементов. Однако известно, что эта проблема NP-трудна.) Следовательно, если P не совпадает с NP, то для задачи упаковки в контейнеры нет алгоритма приближенной схемы полиномиального времени (PTAS). С другой стороны, для всякого ε >0  можно найти решение с не более, чем (1 + ε)OPT + 1 контейнерами за полиномиальное время. Такие алгоритмы относятся к асимптотической PTAS.[3] Но поскольку в оценке сложности этого класса алгоритмов  a n^b обе константы произвольно зависят от  ε, подобные алгоритмы в отличие от FFD и BFD могут быть практически бесполезными.

Вероятностный подход[править | править вики-текст]

Для некоторого класса вероятностных распределений размеров упаковываемых предметов, включающего функции распределения выпуклые вверх и вниз, существует практический полиномиальный алгоритм упаковки асимптотически оптимальный почти наверное при неограниченном росте числа предметов. Для распределений не входящих в этот класс могут строиться индивидуальные полиномиальные асимптотически оптимальные алгоритмы.[4].

Примечания[править | править вики-текст]

  1. Silvano Martello and Paolo Toth Knapsack problems. — Chichester, UK: John Wiley and Sons, 1990. — P. 221. — ISBN 0471924202
  2. Yue, Minyi (1991), A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm, "«A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm»", Acta Mathematicae Applicatae Sinica Т. 7 (4): 321–331, ISSN 0168-9673, DOI 10.1007/BF02009683 
  3. Fernandez de la Vega, W. & Lueker, G. S. (1981), Bin packing can be solved within 1 + ε in linear time, "«Bin packing can be solved within 1 + ε in linear time»", Combinatorica (Springer Berlin / Heidelberg) . — Т. 1 (4): 349–355, ISSN 0209-9683, DOI 10.1007/BF02579456 
  4. Смирнов А. В. Оптимизация процесса обработки данных в локальных сетях ЭВМ : Дисс. к.ф.-м.н. Специальность 01.01.09 — Математическая кибернетика. — 1991.

См. также[править | править вики-текст]