Оптимальная упаковка в мусорное ведро

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

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

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

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

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

Худший вариант

Worst-Fit — это «двойной» алгоритм наилучшего соответствия: он пытается поместить следующий элемент в корзину с минимальной загрузкой.

Этот алгоритм может вести себя так же плохо, как Next-Fit , и будет действовать в списке наихудших случаев для этого. $NF(L)=2\cdot \mathrm {OPT} (L)-2$ . ^{[ 6 ]} Кроме того, он утверждает, что $R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )$ .

Поскольку Worst-Fit является алгоритмом AnyFit, существует алгоритм AnyFit такой, что $R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )$ . ^{[ 6 ]}

Ссылки

^ Ульман, 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 .
^ Дьёрдь, Доса; Сгалл, Иржи (2014). «Оптимальный анализ наилучшей подходящей упаковки в контейнеры». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 8572. стр. 429–441. дои : 10.1007/978-3-662-43948-7_36 . ISBN 978-3-662-43947-0 .
^ Jump up to: ^а ^б Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .

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

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

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

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

[DósaSgall14-5] Дьёрдь, Доса; Сгалл, Иржи (2014). «Оптимальный анализ наилучшей подходящей упаковки в контейнеры». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 8572. стр. 429–441. дои : 10.1007/978-3-662-43948-7_36 . ISBN 978-3-662-43947-0 .

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]