Упаковка контейнеров Next-fit

Next-fit — это онлайн-алгоритм для упаковки контейнеров . Его входные данные — список предметов разных размеров. Его выход — упаковка — разбиение элементов на контейнеры фиксированной емкости, так что сумма размеров предметов в каждом контейнере не превышает емкость. В идеале мы хотели бы использовать как можно меньше контейнеров, но минимизация количества контейнеров — это NP-трудная задача. Алгоритм next-fit использует следующую эвристику :

• Он сохраняет текущую ячейку , которая изначально пуста.
• При поступлении товара проверяется, помещается ли он в текущую корзину.
  • Если он подходит, то его помещают внутрь.
  • В противном случае текущая корзина закрывается, открывается новая корзина, и новый предмет помещается в эту новую корзину.

Next-Fit — это алгоритм ограниченного пространства — он требует, чтобы в любой момент времени была открыта только одна частично заполненная ячейка. Алгоритм был изучен Дэвидом С. Джонсоном в его докторской диссертации ^[1] в 1973 году.

Время работы NextFit может быть ограничено , где — количество элементов в списке. ^[2]${\displaystyle {\mathcal {O}}(n)}$${\displaystyle n}$

Обозначим через NF(L) количество ячеек, используемых NextFit, а через OPT(L) — оптимальное количество ячеек, возможных для списка L.

Затем для каждого списка , . Интуиция доказательства следующая. Количество контейнеров, используемых этим алгоритмом, не более чем вдвое превышает оптимальное количество контейнеров. Другими словами, невозможно, чтобы 2 контейнера были заполнены не более чем наполовину, поскольку такая возможность подразумевает, что в какой-то момент ровно один контейнер был заполнен не более чем наполовину, и был открыт новый для размещения элемента размером не более . Но поскольку первый имеет по крайней мере пространство , алгоритм не будет открывать новый контейнер для любого элемента, размер которого не более . Только после того, как контейнер заполнится более чем или если поступит элемент с размером больше, чем , алгоритм может открыть новый контейнер. Таким образом, если у нас есть контейнеры, по крайней мере контейнеры заполнены более чем наполовину. Следовательно, . Поскольку является нижней границей оптимального значения , мы получаем, что и, следовательно , . ^{[3] : 74}${\displaystyle L}$${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle К}$${\displaystyle К-1}$${\displaystyle \sum _{i\in I}s(i)>{\tfrac {K-1}{2}}B}$${\displaystyle {\tfrac {\sum _{i\in I}s(i)}{B}}}$${\displaystyle \mathrm {OPT} }$${\displaystyle K-1<2\mathrm {OPT} }$${\displaystyle K\leq 2\mathrm {OPT} }$

Для каждого существует список такой, что и .${\displaystyle N\in \mathbb {N} }$${\displaystyle L}$${\displaystyle \mathrm {OPT} (L)=N}$${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$

Семейство списков, для которых это выполняется, задается с . Оптимальное решение для этого списка имеет ячейки, содержащие два элемента размером и одну ячейку с элементами размером (т. е. общее количество ячеек), в то время как решение, сгенерированное NF, имеет ячейки с одним элементом размером и одним элементом размером .${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\displaystyle L:=\left({\frac {1}{2}},{\frac {1}{2(N-1)}},{\frac {1}{2}},{\frac {1}{2(N-1)}},\dots ,{\frac {1}{2}},{\frac {1}{2(N-1)}}\right)}$${\displaystyle |L|=4(N-1)}$${\displaystyle N-1}$${\displaystyle 1/2}$${\displaystyle 2(N-1)}$${\displaystyle 1/2(N-1)}$${\displaystyle N}$${\displaystyle 2(N-1)}$${\displaystyle 1/2}$${\displaystyle 1/(2(N-1))}$

Если максимальный размер элемента равен , то асимптотическое отношение аппроксимации удовлетворяет условию:${\displaystyle \alpha }$${\displaystyle R_{NF}^{\infty }}$

• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$для всех ;${\displaystyle \alpha \geq 1/2}$
• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$для всех .${\displaystyle \alpha \leq 1/2}$

Next-Fit упаковывает список и его обратный список в одинаковое количество ячеек. ^[4]

Next-k-Fit — это вариант Next-Fit, но вместо того, чтобы оставлять открытым только один контейнер, алгоритм оставляет открытыми последние контейнеры и выбирает первый контейнер, в который помещается элемент.${\displaystyle k}$

Для , NkF обеспечивает результаты, которые улучшены по сравнению с результатами NF, однако увеличение до постоянных значений, больших, чем не улучшает алгоритм в его худшем случае. Если алгоритм является AlmostAnyFit-алгоритмом и тогда . ^[1]${\displaystyle k\geq 2}$${\displaystyle k}$${\displaystyle 2}$${\displaystyle A}$${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m}$

• Next-fit-decreasing (NFD) — это офлайновый вариант Next-Fit: он принимает все входные элементы, упорядочивает их по убыванию размера и вызывает Next-Fit. Его асимптотическое приближение намного лучше: менее 1,7 вместо 2.