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

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

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

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

Обозначим через FF(L) количество ячеек, используемых First-Fit, а через OPT(L) — оптимальное количество ячеек, возможных для списка L. Анализ FF(L) проводился в несколько этапов.

Первая верхняя граница для FF была доказана Ульманом ^[1] в 1971 году. $FF(L)\leq 1.7\mathrm {OPT} +3$
В 1972 году эта верхняя граница была улучшена Гари, Грэхемом и Ульманом ^{[2] , Джонсоном и Демерсом}^[3] . $FF(L)\leq 1.7\mathrm {OPT} +2$
^{В 1976 году Гарей, Грэм, Джонсон, Яо и Чи-Чи [4]} улучшили его до , что эквивалентно ввиду целочисленности и . $FF(L)\leq \lceil 1.7\mathrm {OPT} \rceil$ $FF(L)\leq 1,7\mathrm {OPT} +0,9$ $FF(L)$ $\mathrm {OPT}$
Следующее улучшение, проведенное Ся и Таном ^[5] в 2010 году, снизило границу до . $FF(L)\leq 1,7\mathrm {OPT} +0,7$
Наконец, в 2013 году эта граница была улучшена Досой и Сгаллом. ^[6] Они также представляют пример входного списка , для которого соответствует эта граница. $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ $L$ $FF(L)$

Ниже мы объясняем идею доказательства.

Асимптотическое отношение не более 2

Вот доказательство того, что асимптотическое отношение не более 2. Если есть ячейка FF с суммой меньше 1/2, то размер всех оставшихся элементов больше 1/2, поэтому сумма всех следующих ячеек больше 1/2. Следовательно, все ячейки FF, за исключением не более одной, имеют сумму не менее 1/2. Все оптимальные ячейки имеют сумму не более 1, поэтому сумма всех размеров не более OPT. Следовательно, количество ячеек FF не более 1+OPT/(1/2) = 2*OPT+1

Асимптотическое отношение не более 1,75

Рассмотрим сначала особый случай, в котором все размеры элементов не превышают 1/2. Если есть ячейка FF с суммой меньше 2/3, то размер всех оставшихся элементов больше 1/3. Поскольку размеры не превышают 1/2, все последующие ячейки (кроме, может быть, последней) содержат не менее двух элементов и имеют сумму больше 2/3. Следовательно, все ячейки FF, за исключением не более одной, имеют сумму не менее 2/3, а количество ячеек FF не превышает 2+OPT/(2/3) = 3/2*OPT+1.

«Проблемные» элементы — это те, размер которых больше 1/2. Поэтому, чтобы улучшить анализ, давайте дадим каждому элементу больше 1/2 бонус R. Определим вес элемента как его размер плюс его бонус. Определим вес набора элементов как сумму весов его содержимого.

Теперь вес каждой ячейки FF с одним элементом (кроме максимум одного) составляет не менее 1/2+R, а вес каждой ячейки FF с двумя или более элементами (кроме максимум одного) составляет 2/3. Принимая R=1/6, получаем, что вес всех ячеек FF составляет не менее 2/3.

С другой стороны, вес каждой ячейки в оптимальной упаковке не превышает 1+R = 7/6, поскольку каждая такая ячейка содержит не более одного предмета размером больше 1/2. Таким образом, общий вес всех предметов не превышает 7/6*OPT, а количество ячеек FF не превышает 2+(7/6*OPT/(2/3)) = 7/4*OPT+2.

Асимптотическое отношение не более 1,7

Следующее доказательство адаптировано из ^[6]^{: раздел 1.2} Определим вес входного элемента как размер элемента x некоторый бонус , вычисляемый следующим образом:

$bonus(x):={\begin{cases}0&x\leq 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\leq x\leq 1/2\\1/3&1/2<x\end{cases}}$

$вес(x):=x+бонус(x)$ .

Асимптотическое приближение следует из двух утверждений:

При оптимальной упаковке вес каждого контейнера составляет не более 17/12;
В упаковке First-Fit средний вес каждой ячейки составляет не менее 5/6 = 10/12.

Следовательно, асимптотически количество ячеек в упаковке FF должно быть не более 17/10 * OPT.

Для утверждения 1 достаточно доказать, что для любого множества B с суммой не более 1, bonus( B ) не более 5/12. Действительно:

Если у B нет ни одного предмета больше 1/2, то у него есть не более пяти предметов больше 1/6, и бонус каждого из них не превышает 1/12;
Если у B есть элемент больше 1/2, но нет элемента в [1/3,1/2], то в (1/6,1/3) есть место максимум для двух элементов, а сумма их бонусов составляет максимум (1/2 / 2 - 1/6) = 1/12, поэтому общий бонус равен 4/12+1/12=5/12.
Если у B есть предмет размером больше 1/2 и предмет в диапазоне [1/3,1/2], то у него больше нет места для предметов размером больше 1/6, поэтому общий бонус снова равен 4/12+1/12 = 5/12.

Следовательно, вес B не превышает 1+5/12 = 17/12.

Для утверждения 2 сначала рассмотрим ячейку FF B с одним элементом.

Если сумма ( B )<1/2, то — по принципу работы FF — все элементы, обработанные после B, должны быть больше 1/2 (иначе они были бы вставлены в B ). Таким образом, существует максимум один контейнер FF с суммой <1/2.
Рассмотрим теперь все остальные ячейки B с одним элементом с суммой ( B )>1/2. Для всех этих ячеек вес ( B )>1/2+1/3 = 5/6.

Теперь рассмотрим ячейки FF B с двумя или более элементами.

Если сумма ( B )<2/3, то — кстати, как работает FF — все элементы, обработанные после B, должны быть больше 1/3 (иначе они были бы вставлены в B ). Следовательно, все последующие ячейки с двумя или более элементами больше 2/3. Таким образом, существует максимум одна ячейка FF с двумя или более элементами и суммой <2/3.
Рассмотрим теперь все остальные ячейки с двумя или более предметами и суммой > 2/3. Обозначим их как B[1],B[2],...B[k], в порядке их открытия. Для каждого i из 1,..., k мы докажем, что сумма B[i] плюс бонус B[i+1] составляет не менее 5/6: sum(B[i])+bonus(B[i+1]) ≥ 5/6. Действительно, если sum(B[i]) ≥ 5/6, то неравенство тривиально. В противном случае пусть sum(B[i]) := 1 - x . Обратите внимание, что x находится между 1/6 и 2/6, поскольку sum(B[i]) находится между 2/3 и 5/6. Так как B[i+1] открывается после B[i], B[i+1] содержит по крайней мере два элемента, скажем c 1 и c 2, которые не помещаются в B[i], то есть: c1,c2 > 1-sum(B[i]) = x > 1/6. Тогда бонус каждого из c1 и c2 составляет по крайней мере x/2 - 1/12. Следовательно, бонус B[i+1] составляет по крайней мере x-1/6, поэтому sum(B[i]) + bonus(B[i+1]) ≥ (1-x)+(x-1/6) = 5/6.
Мы можем применить указанное выше неравенство к последовательным парам и получить: сумма(B[1]) + бонус(B[2]) + сумма(B[2]) + бонус(B[3]) + ... + сумма(B[k-1]) + бонус(B[k]) ≥ 5/6*(k-1).

Таким образом, общий вес всех ячеек FF составляет не менее 5/6*(FF - 3) (где мы вычитаем 3 для одной ячейки с одним элементом и суммой <1/2, одной ячейки с двумя элементами и суммой <2/3 и k-1 для ячеек с двумя элементами и суммой ≥ 2/3).

В целом получаем, что 17/12*OPT ≥ 5/6*(FF-3), поэтому FF ≤ 17/10*OPT+3.

Доса и Сгалл ^[6] предлагают более строгий анализ, который избавляется от 3 и получает, что FF ≤ 17/10*OPT.

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

Существуют случаи, когда предел производительности 1.7OPT является жестким. Следующий пример основан на. ^[7]^[8] Емкость ячейки составляет 101, и:

Последовательность такова: 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10).
Оптимальная упаковка содержит 10 ячеек: [51+34+16] (x3), [51+34+10+6] (x7). Все суммы ячеек равны 101.
Упаковка First Fit содержит 17 ячеек: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10).
- Суммы ячеек: 92, 68, 68 (x5), 51 (x10).
- Награды (нормализованные до 101) составляют 0, 0, 16,8 (x5), 33,7 (x10).
- Общие веса (нормализованные к 101) составляют 92, 68, 84,8 (x5), 84,7 (x10). Видно, что почти все веса близки к 101*5/6=84,1.

Производительность с делимыми размерами элементов

Важным частным случаем упаковки в контейнеры является то, что размеры элементов образуют делимую последовательность (также называемую факторизованной ). Частный случай делимых размеров элементов возникает при распределении памяти в компьютерных системах, где все размеры элементов являются степенями 2. Если размеры элементов делимы, и, кроме того, наибольший размер элемента делит размер контейнера, то FF всегда находит оптимальную упаковку. ^[9]^{: Теор.3}

Изысканный первый вариант

Refined-First-Fit (RFF) — это еще один онлайн-алгоритм для упаковки контейнеров , который улучшает ранее разработанный алгоритм FF. Он был представлен Эндрю Чи-Чи Яо. ^[10]

Алгоритм

Предметы делятся на четыре класса в зависимости от их размеров (вместимость контейнера равна 1):

$А$ -штука - размер в . $(1/2,1]$
$B_{1}$ -штука - размер в . $(2/5,1/2]$
$B_{2}$ -штука - размер в . $(1/3,2/5]$
$X$ -штука - размер в . $(0,1/3]$

Аналогично контейнеры делятся на четыре класса: 1, 2, 3 и 4.

Пусть будет фиксированным целым числом. Следующий элемент назначается в ячейку в - $м\дюйм \{6,7,8,9\}$ $i\in L$

Класс 1, если это -часть, $я$ $А$
Класс 2, если это -часть, $я$ $B_{1}$
Класс 3, если это -часть , но не -я -я часть, рассмотренная до сих пор, для любого целого числа . $я$ $B_{2}$ $(мк)$ $B_{2}$ $k\geq 1$
Класс 1, если это та часть, которую мы видели до сих пор, $я$ $(мк)$ $B_{2}$
Класс 4, если это -часть. $я$ $X$

После выбора класса предмета он помещается в контейнеры этого класса с использованием метода первой подходящей упаковки.

Обратите внимание, что RFF не является алгоритмом Any-Fit, поскольку он может открыть новую ячейку, несмотря на то, что текущий элемент помещается в открытую ячейку (из другого класса).

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

RFF имеет гарантию аппроксимации . Существует семейство списков с для . ^[10] $RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ $L_{k}$ $RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3$ $\mathrm {OPT} (L)=6k+1$

Смотрите также

First-Fit-Decreasing (FFD) — это офлайновый вариант First-Fit: он принимает все входные элементы, упорядочивает их по убыванию размера и вызывает First-Fit. Его асимптотическое приближение намного лучше: около 1,222 вместо 1,7.

Реализации

Python: Пакет prtpy содержит реализацию first-fit.

Ссылки

^ Ульман, Дж. Д. (1971). «Производительность алгоритма распределения памяти». Технический отчет 100 Принстонский университет .
^ Garey, M. R; Graham, R. L; Ullman, JD (1972). "Анализ алгоритмов распределения памяти в наихудшем случае". Труды четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72 . С. 143–150. doi :10.1145/800152.804907. S2CID 26654056.
^ Дэвид С. Джонсон, Алан Дж. Демерс, Джеффри Д. Ульман, М. Р. Гэри, Рональд Л. Грэм. Границы производительности в худшем случае для простых алгоритмов одномерной упаковки. SICOMP, том 3, выпуск 4. 1974.
^ Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). «Ресурсно-ограниченное планирование как обобщенная упаковка контейнеров». Журнал комбинаторной теории, серия A. 21 ( 3): 257–298. doi : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165.
^ Ся, Бинчжоу; Тан, Чжии (август 2010 г.). «Более узкие границы алгоритма First Fit для задачи упаковки в контейнеры». Дискретная прикладная математика . 158 (15): 1668–1675. doi : 10.1016/j.dam.2010.05.026 .
^ abc Доса, Дьёрдь; Сгалл, Иржи (2013). «Упаковка контейнера с первой посадкой: тщательный анализ». 30-й Международный симпозиум по теоретическим аспектам информатики (STACS 2013) . 20 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 538–549. дои : 10.4230/LIPIcs.STACS.2013.538 .
^ Garey, MR; Graham, RL; Ullman, JD (1972-05-01). "Анализ алгоритмов распределения памяти в наихудшем случае". Труды четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 143–150. doi :10.1145/800152.804907. ISBN 978-1-4503-7457-6. S2CID 26654056.
^ Джонсон, Д.С.; Демерс, А.; Ульман, Дж.Д.; Гэри, М.Р.; Грэм, Р.Л. (декабрь 1974 г.). «Границы производительности в наихудшем случае для простых алгоритмов одномерной упаковки». Журнал SIAM по вычислениям . 3 (4): 299–325. doi :10.1137/0203025. ISSN 0097-5397.
^ Коффман, Э. Г.; Гарей, М. Р.; Джонсон, Д. С. (1987-12-01). «Упаковка контейнеров с делимыми размерами предметов». Журнал сложности . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN 0885-064X.
^ ab Yao, Andrew Chi-Chih (апрель 1980 г.). «Новые алгоритмы упаковки контейнеров». Журнал ACM . 27 (2): 207–227. doi : 10.1145/322186.322187 . S2CID 7903339.