WikiSort.ru - Не сортированное

Постановка задачи

Пусть дано множество контейнеров размера ${\displaystyle V}$ и множество ${\displaystyle n}$ предметов размеров ${\displaystyle a_{1},\dots ,a_{n}}$ . Надо найти целое число контейнеров ${\displaystyle B}$ и разбиение множества ${\displaystyle \{1,\dots ,n\}}$ на ${\displaystyle B}$ подмножеств ${\displaystyle S_{1}\cup \dots \cup S_{B}}$ таких, что ${\displaystyle \sum _{i\in S_{k}}a_{i}\leq V}$ для всех ${\displaystyle k=1,\dots ,B}$ . Решение называется оптимальным, если ${\displaystyle B}$ минимально. Минимальное ${\displaystyle B}$ далее обозначается OPT.

Упаковка как задача целочисленного программирования

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

Минимизировать ${\displaystyle B=\sum _{i=1}^{n}y_{i}}$
при ограничениях	${\displaystyle \sum _{j=1}^{n}a_{j}x_{ij}\leq Vy_{i},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}}$
	${\displaystyle \sum _{i=1}^{n}x_{ij}=1,}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle y_{i}\in \{0,1\},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}\,\forall j\in \{1,\ldots ,n\}}$

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

Приближённые полиномиальные алгоритмы

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

${\displaystyle {\frac {11}{9}}OPT+1}$

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

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

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

Вероятностный подход

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

См. также

• Задачи упаковки
• Задача о ранце
• Задача о сумме подмножеств
• Оптимизация
• Упаковка шаров