Гармоническая упаковка бункера

Гармоничная упаковка в корзину — это семейство онлайн-алгоритмов для упаковки в корзину . Входными данными для такого алгоритма является список элементов разного размера. На выходе получается упаковка — разбиение предметов на ячейки фиксированной вместимости так, чтобы сумма размеров предметов в каждой ячейке не превышала вместимости. В идеале нам хотелось бы использовать как можно меньше ячеек, но минимизация количества ячеек — NP-сложная задача.

Алгоритмы гармонической упаковки в контейнеры основаны на разделении предметов на категории в зависимости от их размеров в соответствии с гармонической прогрессией . Есть несколько вариантов этой идеи.

Гармоника- к

Алгоритм Harmonic k - разбивает интервал размеров $(0,1]$ гармонично в $k-1$ куски $I_{j}:=(1/(j+1),1/j]$ для $1\leq j<k$ и $I_{k}:=(0,1/k]$ такой, что $\bigcup _{j=1}^{k}I_{j}=(0,1]$ . Предмет $i\in L$ называется $I_{j}$ -предмет, если $s(i)\in I_{j}$ .

Алгоритм делит множество пустых контейнеров на $k$ бесконечные классы $B_{j}$ для $1\leq j\leq k$ , один тип ячейки для каждого типа товара. Тип контейнера $B_{j}$ используется только для контейнеров для упаковки предметов типа $j$ . Каждый контейнер типа $B_{j}$ для $1\leq j<k$ может содержать ровно $j$ $I_{j}$ -предметы. Теперь алгоритм действует следующим образом:

Если следующий элемент $i\in L$ это $I_{j}$ -предмет для $1\leq j<k$ , предмет помещается в первое (только открытое) $B_{j}$ контейнер, содержащий менее $j$ частей или открывает новый, если такого контейнера не существует.
Если следующий элемент $i\in L$ это $I_{k}$ -item, алгоритм помещает его в ячейки типа $B_{k}$ с помощью Next-Fit.

Этот алгоритм был впервые описан Ли и Ли. ^[1] Имеет временную сложность ${\mathcal {O}}(n\log(n))$ где n — количество входных элементов. На каждом шаге существует не более $k$ открытые контейнеры, которые потенциально могут быть использованы для размещения предметов, т. е. это алгоритм с ограниченным k пространством.

Ли и Ли также изучили коэффициент асимптотической аппроксимации. Они определили последовательность $\sigma _{1}:=1$ , $\sigma _{i+1}:=\sigma _{i}(\sigma _{i}+1)$ для $i\geq 1$ и доказал, что для $\sigma _{l}<k<\sigma _{l+1}$ он утверждает, что $R_{Hk}^{\infty }\leq \sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))$ . Для $k\rightarrow \infty$ он утверждает, что $R_{Hk}^{\infty }\approx 1.6910$ . Кроме того, они представили семейство наихудших примеров этого случая. $R_{Hk}^{\infty }=\sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))$

Утонченная гармоника (RH)

Refined-Harmonic сочетает в себе идеи алгоритма Harmonic-k с идеями Refined-First-Fit . Он помещает элементы размером больше, чем $1/3$ аналогично методу Refined-First-Fit, тогда как более мелкие элементы размещаются с использованием Harmonic-k. Идея этой стратегии заключается в том, чтобы уменьшить количество огромных отходов в контейнерах, содержащих куски размером чуть больше $1/2$ .

Алгоритм классифицирует элементы по следующим интервалам: $I_{1}:=(59/96,1]$ , $I_{a}:=(1/2,59/96]$ , $I_{2}:=(37/96,1/2]$ , $I_{b}:=(1/3,37/96]$ , $I_{j}:=(1/(j+1),1/j]$ , для $j\in \{3,\dots ,k-1\}$ , и $I_{k}:=(0,1/k]$ . Алгоритм размещает $I_{j}$ -items, как в Harmonic-k, хотя для элементов в нем используется другая стратегия. $I_{a}$ и $I_{b}$ . Есть четыре возможности упаковки. $I_{a}$ -предметы и $I_{b}$ - вещи в контейнеры.

Ан $I_{a}$ -bin содержит только один $I_{a}$ -элемент.
Ан $I_{b}$ -bin содержит только один $I_{b}$ -элемент.
Ан $I_{a}b$ -bin содержит один $I_{a}$ -предмет и один $I_{b}$ -элемент.
Ан $I_{b}b$ -bin содержит два $I_{b}$ -предметы.

Ан $I_{b}'$ -bin обозначает бункер, предназначенный для хранения второго $I_{b}$ -элемент. Алгоритм использует числа N_a, N_b, N_ab, N_bb и N_b' для подсчета количества соответствующих интервалов в решении. Кроме того, N_c= N_b+N_ab

Алгоритм Refined-Harmonic-k для списка L = (i_1, \dots i_n):1. N_a = N_b = N_ab = N_bb = N_b' = N_c = 02. Если i_j — I_k-кусок       затем используйте алгоритм Harmonic-k для его упаковки3. иначе, если i_j является I_a-элементом           тогда если N_b != 1,                затем упакуйте i_j в любой J_b-bin; Н_б--; Н_аб++;               иначе поместите i_j в новую (пустую) корзину; Н_а++;4. иначе, если i_j является I_b-элементом               тогда если N_b' = 1                   затем поместите i_j в I_b'-bin; Н_б' = 0; Н_бб++;5. иначе, если N_bb <= 3N_c                       затем поместите i_j в новый контейнер и назовите его I_b'-bin; Н_б' = 1                       иначе, если N_a != 0                           затем поместите i_j в любой I_a-bin; Н_а--; N_ab++;N_c++                           иначе поместите i_j в новую корзину; Н_b++;N_c++

Этот алгоритм был впервые описан Ли и Ли. ^[1] Они доказали, что для $k=20$ он утверждает, что $R_{RH}^{\infty }\leq 373/228$ .

Другие варианты

Модифицированная гармоника (MH) имеет асимптотическое соотношение $R_{MH}^{\infty }\leq 538/33\approx 1.61562$ . ^[2]

Модифицированная гармоника 2 (MH2) имеет асимптотическое соотношение $R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217$ . ^[2]

Гармоника + 1 (H+1) имеет асимптотическое соотношение $R_{H+1}^{\infty }\geq 1.59217$ . ^[3]

Гармоника ++ (H++) имеет асимптотическое соотношение $R_{H++}^{\infty }\leq 1.58889$ ^[3] и $R_{H++}^{\infty }\geq 1.58333$ . ^[3]

Ссылки

^ Jump up to: ^а ^б Ли, CC; Ли, DT (июль 1985 г.). «Простой онлайн-алгоритм упаковки в контейнеры» . Журнал АКМ . 32 (3): 562–572. дои : 10.1145/3828.3833 . S2CID 15441740 .
^ Jump up to: ^а ^б Раманан, Пракаш; Браун, Донна Дж; Ли, CC; Ли, DT (сентябрь 1989 г.). «Онлайн-упаковка контейнеров в линейное время». Журнал алгоритмов . 10 (3): 305–326. дои : 10.1016/0196-6774(89)90031-X . hdl : 2142/74206 .
^ Jump up to: ^а ^б ^с Сейден, Стивен С. (2002). «О проблеме онлайн-упаковки корзин». Журнал АКМ . 49 (5): 640–671. дои : 10.1145/585265.585269 . S2CID 14164016 .

[LeeLee1985-1] Jump up to: ^а ^б Ли, CC; Ли, DT (июль 1985 г.). «Простой онлайн-алгоритм упаковки в контейнеры» . Журнал АКМ . 32 (3): 562–572. дои : 10.1145/3828.3833 . S2CID 15441740 .

[RamananBLL1989-2] Jump up to: ^а ^б Раманан, Пракаш; Браун, Донна Дж; Ли, CC; Ли, DT (сентябрь 1989 г.). «Онлайн-упаковка контейнеров в линейное время». Журнал алгоритмов . 10 (3): 305–326. дои : 10.1016/0196-6774(89)90031-X . hdl : 2142/74206 .

[Seiden2002-3] Jump up to: ^а ^б ^с Сейден, Стивен С. (2002). «О проблеме онлайн-упаковки корзин». Журнал АКМ . 49 (5): 640–671. дои : 10.1145/585265.585269 . S2CID 14164016 .

[1]

[2]

[3]