Упаковка следующего контейнера

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

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

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

Время выполнения

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

Коэффициент аппроксимации

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

Верхняя граница

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

Нижняя граница

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

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

Ограниченный размер элемента

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

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

Другие объекты недвижимости

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

Next- k -Fit (NkF)

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

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

См. также

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

Ссылки

^ Jump up to: ^а ^б Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .
^ Сури, Субхаш. «Бин-упаковка» . UCSB Информатика . Проверено 7 октября 2021 г.
^ Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, ISBN 3-540-65367-8
^ Фишер, Дэвид К. (1 декабря 1988 г.). «Next-fit упаковывает список и его обратную сторону в одинаковое количество ячеек» . Письма об исследованиях операций . 7 (6): 291–293. дои : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

[johnson73-1] Jump up to: ^а ^б Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .

[2] Сури, Субхаш. «Бин-упаковка» . UCSB Информатика . Проверено 7 октября 2021 г.

[3] Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, ISBN 3-540-65367-8

[:0-4] Фишер, Дэвид К. (1 декабря 1988 г.). «Next-fit упаковывает список и его обратную сторону в одинаковое количество ячеек» . Письма об исследованиях операций . 7 (6): 291–293. дои : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]