Первичная упаковка в контейнер

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

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

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

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

Первая верхняя граница $FF(L)\leq 1.7\mathrm {OPT} +3$ для FF было доказано Ульманом ^{[ 1 ]} в 1971 году.
В 1972 году эта верхняя граница была улучшена до $FF(L)\leq 1.7\mathrm {OPT} +2$ Гэри, Грэм и Уллман, ^{[ 2 ]} Джонсон и Демерс. ^{[ 3 ]}
В 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 году эта граница была улучшена до $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ Доса и Сгалл. ^{[ 6 ]} Они также представляют пример списка ввода. $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}}$

$weight(x):=x+bonus(x)$ .

Коэффициент асимптотической аппроксимации следует из двух утверждений:

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

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

Для утверждения 1 достаточно доказать, что для любого множества B с суммой не более 1 бонус( 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 рассмотрим сначала корзину B FF с одним предметом.

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

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

Если sum( 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-сумма(B[i]) = x > 1/6. Тогда бонус каждого из c1 и c2 составляет не менее x/2 – 1/12. Следовательно, бонус B[i+1] равен как минимум x-1/6, поэтому sum(B[i]) + бонус(B[i+1]) ≥ (1-x)+(x-1/ 6) = 5/6.
Мы можем применить приведенное выше неравенство к последовательным парам и получить: sum(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 (х7), 10 (х7), 16 (х3), 34 (х10), 51 (х10).
Оптимальная упаковка содержит 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 (х5), 84,7 (х10). Видно, что почти все веса близки к 101*5/6=84,1.

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

RFF имеет гарантию аппроксимации $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$ . ^{[ 10 ]}

См. также

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

Реализации

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

Ссылки

^ Ульман, JD (1971). «Производительность алгоритма распределения памяти». Технический отчет 100 Принстонского университета .
^ Гэри, MR; Грэм, Р.Л.; Ульман, доктор медицинских наук (1972). «Анализ алгоритмов распределения памяти наихудшего случая». Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72 . стр. 143–150. дои : 10.1145/800152.804907 . S2CID 26654056 .
^ Дэвид С. Джонсон, Алан Дж. Демерс, Джеффри Д. Уллман, М. Р. Гэри, Рональд Л. Грэм. Границы производительности для наихудшего случая для простых одномерных алгоритмов упаковки . SICOMP, том 3, выпуск 4. 1974.
^ Гэри, MR; Грэм, Р.Л.; Джонсон, Д.С.; Яо, Эндрю Чи-Чи (1976). «Планирование с ограниченными ресурсами как обобщенная упаковка контейнеров» . Журнал комбинаторной теории, серия А. 21 (3): 257–298. дои : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165 .
^ Ся, Биньчжоу; Тан, Чжии (август 2010 г.). «Более жесткие границы алгоритма First Fit для задачи упаковки контейнеров» . Дискретная прикладная математика . 158 (15): 1668–1675. дои : 10.1016/j.dam.2010.05.026 .
^ Jump up to: ^а ^б ^с Доса, Дьёрдь; Сгалл, Иржи (2013). «Упаковка контейнера с первой подгонкой: тщательный анализ» . 30-й Международный симпозиум по теоретическим аспектам информатики (STACS 2013) . 20 . Замок Дагштуль – Центр информатики Лейбница: 538–549. дои : 10.4230/LIPIcs.STACS.2013.538 .
^ Гэри, MR; Грэм, РЛ; Ульман, доктор медицинских наук (1 мая 1972 г.). «Анализ алгоритмов распределения памяти наихудшего случая» . Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 143–150. дои : 10.1145/800152.804907 . ISBN 978-1-4503-7457-6 . S2CID 26654056 .
^ Джонсон, Д.С.; Демерс, А.; Ульман, доктор медицинских наук; Гэри, MR; Грэм, Р.Л. (декабрь 1974 г.). «Границы производительности для наихудшего случая для простых одномерных алгоритмов упаковки» . SIAM Journal по вычислительной технике . 3 (4): 299–325. дои : 10.1137/0203025 . ISSN 0097-5397 .
^ Коффман, Э.Г.; Гэри, MR; Джонсон, Д.С. (1 декабря 1987 г.). «Корзинная упаковка с предметами, делящимися по размеру» . Журнал сложности . 3 (4): 406–428. дои : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .
^ Jump up to: ^а ^б Яо, Эндрю Чи-Чи (апрель 1980 г.). «Новые алгоритмы упаковки контейнеров» . Журнал АКМ . 27 (2): 207–227. дои : 10.1145/322186.322187 . S2CID 7903339 .

[Ullman713-1] Ульман, JD (1971). «Производительность алгоритма распределения памяти». Технический отчет 100 Принстонского университета .

[GareyGU723-2] Гэри, MR; Грэм, Р.Л.; Ульман, доктор медицинских наук (1972). «Анализ алгоритмов распределения памяти наихудшего случая». Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72 . стр. 143–150. дои : 10.1145/800152.804907 . S2CID 26654056 .

[3] Дэвид С. Джонсон, Алан Дж. Демерс, Джеффри Д. Уллман, М. Р. Гэри, Рональд Л. Грэм. Границы производительности для наихудшего случая для простых одномерных алгоритмов упаковки . SICOMP, том 3, выпуск 4. 1974.

[GareyGJY3-4] Гэри, MR; Грэм, Р.Л.; Джонсон, Д.С.; Яо, Эндрю Чи-Чи (1976). «Планирование с ограниченными ресурсами как обобщенная упаковка контейнеров» . Журнал комбинаторной теории, серия А. 21 (3): 257–298. дои : 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165 .

[5] Ся, Биньчжоу; Тан, Чжии (август 2010 г.). «Более жесткие границы алгоритма First Fit для задачи упаковки контейнеров» . Дискретная прикладная математика . 158 (15): 1668–1675. дои : 10.1016/j.dam.2010.05.026 .

[DósaSgall2-6] Jump up to: ^а ^б ^с Доса, Дьёрдь; Сгалл, Иржи (2013). «Упаковка контейнера с первой подгонкой: тщательный анализ» . 30-й Международный симпозиум по теоретическим аспектам информатики (STACS 2013) . 20 . Замок Дагштуль – Центр информатики Лейбница: 538–549. дои : 10.4230/LIPIcs.STACS.2013.538 .

[7] Гэри, MR; Грэм, РЛ; Ульман, доктор медицинских наук (1 мая 1972 г.). «Анализ алгоритмов распределения памяти наихудшего случая» . Материалы четвертого ежегодного симпозиума ACM по теории вычислений - STOC '72 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 143–150. дои : 10.1145/800152.804907 . ISBN 978-1-4503-7457-6 . S2CID 26654056 .

[8] Джонсон, Д.С.; Демерс, А.; Ульман, доктор медицинских наук; Гэри, MR; Грэм, Р.Л. (декабрь 1974 г.). «Границы производительности для наихудшего случая для простых одномерных алгоритмов упаковки» . SIAM Journal по вычислительной технике . 3 (4): 299–325. дои : 10.1137/0203025 . ISSN 0097-5397 .

[9] Коффман, Э.Г.; Гэри, MR; Джонсон, Д.С. (1 декабря 1987 г.). «Корзинная упаковка с предметами, делящимися по размеру» . Журнал сложности . 3 (4): 406–428. дои : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .

[Yao1980-10] Jump up to: ^а ^б Яо, Эндрю Чи-Чи (апрель 1980 г.). «Новые алгоритмы упаковки контейнеров» . Журнал АКМ . 27 (2): 207–227. дои : 10.1145/322186.322187 . S2CID 7903339 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]