Оглавление
- 1 Проблема с упаковкой мусорного бака
- 1.1 Задача упаковки в бункер
- 1.2 Алгоритмы аппроксимации
- 1.3 Онлайн-упаковка в бункер
- 1.4 Формулировка задачи
- 1.5 Сложность задачи
- 1.6 Алгоритмы аппроксимации
- 1.7 Примеры алгоритмов
- 1.8 Алгоритмы Next-Fit и Next-k-Fit
- 1.9 Алгоритмы First-Fit и Best-Fit
- 1.10 Алгоритмы Worst-Fit и Almost-Worst-Fit
- 1.11 Алгоритмы AnyFit и Almost-AnyFit
- 1.12 Усовершенствованные алгоритмы
- 1.13 Общие нижние границы
- 1.14 Автономные алгоритмы
- 1.15 Алгоритмы упаковки в ячейки
- 1.16 Точные алгоритмы
- 1.17 Упаковка в ячейки с высокой кратностью
- 1.18 Упаковка в мусорное ведро с фрагментацией
- 1.19 Производительность при разделении размеров изделий
- 1.20 Ограничения на количество элементов в ячейках
- 1.21 Неаддитивные функции
- 1.22 Связанные проблемы
- 1.23 Ресурсы
- 1.24 Описание библиотеки BPPLIB
- 1.25 Основные разделы библиотеки
- 1.26 Полный текст статьи:
- 2 Проблема с упаковкой мусорного бака
Проблема с упаковкой мусорного бака
-
Задача упаковки в бункер
- Задача оптимизации, где предметы разного размера упаковываются в ящики с фиксированной вместимостью.
- Применяется в различных областях, таких как заполнение контейнеров и создание резервных копий файлов.
- NP-сложная задача, но существуют алгоритмы аппроксимации.
-
Алгоритмы аппроксимации
- Алгоритм первой подгонки: быстрое, но неоптимальное решение.
- Алгоритм убывания по первому требованию: более эффективный, но не гарантирует оптимального решения.
- Существует множество вариаций задачи, таких как двумерная упаковка и упаковка по весу.
-
Онлайн-упаковка в бункер
- Товары поступают последовательно, решение принимается до поступления следующего товара.
- Автономная упаковка позволяет переставлять товары для лучшей упаковки.
-
Формулировка задачи
- Конечное множество предметов, емкость ячейки и количество ящиков.
- Задача: разделить множество на непересекающиеся множества с минимальной суммой размеров.
-
Сложность задачи
- Проблема NP-полная, нет алгоритма аппроксимации с коэффициентом аппроксимации меньше 3/2.
- Проблема разрешима за псевдополиномиальное время для фиксированного числа ячеек.
-
Алгоритмы аппроксимации
- Онлайн-эвристика: рассматривает товары в заданном порядке.
- Автономные эвристики: изменяют список элементов, улучшают аппроксимацию.
- Схемы асимптотической аппроксимации: гарантируют аппроксимацию вида (1+ε)OPT(L)+C.
-
Примеры алгоритмов
- Next Fit: всегда остается одна открытая ячейка, коэффициент аппроксимации 2.
- Другие алгоритмы используют общую схему: если товар помещается, положить его в открытую ячейку, иначе открыть новую.
-
Алгоритмы Next-Fit и Next-k-Fit
- Next-Fit оставляет открытой только одну ячейку, Next-k-Fit оставляет открытыми последние k ячеек.
- Next-k-Fit обеспечивает улучшенные результаты по сравнению с Next-Fit, но увеличение k до постоянных значений не улучшает работу в худшем случае.
-
Алгоритмы First-Fit и Best-Fit
- First-Fit оставляет все контейнеры открытыми и помещает каждый новый элемент в первую попавшуюся корзину.
- Best-Fit также оставляет все контейнеры открытыми, но помещает каждый новый элемент в контейнер с максимальной загрузкой.
-
Алгоритмы Worst-Fit и Almost-Worst-Fit
- Worst-Fit пытается поместить каждый новый элемент в корзину с минимальной загрузкой.
- Almost-Worst-Fit пытается поместить каждый новый элемент во вторую по величине пустую открытую ячейку.
-
Алгоритмы AnyFit и Almost-AnyFit
- AnyFit-алгоритмы оставляют открытыми все ячейки, но не помещают элемент в ячейку, если он не помещается ни в одну из открытых ячеек.
- Almost-AnyFit-алгоритмы оставляют открытыми все ячейки, кроме ячейки с наименьшей загрузкой, и помещают элемент в эту ячейку, если он не помещается ни в одну из ячеек слева от нее.
-
Усовершенствованные алгоритмы
- RFF делит размеры изделий на четыре категории и использует first-fit для каждого класса.
- Harmonic-k разбивает интервал размеров на гармоничные куски и использует ограниченное k-е пространство.
- Refined-harmonic сочетает идеи Harmonic-k и Refined-First-Fit для сокращения отходов.
-
Общие нижние границы
- Яо доказал, что не может быть онлайн-алгоритма с асимптотическим коэффициентом аппроксимации меньше 3/2.
- Браун и Лян улучшили нижнюю границу до 1,53635, Влиет до 1,54014, Бекези и Галамбос до 1,54037.
-
Автономные алгоритмы
- Автономные алгоритмы могут просматривать все товары перед размещением их в корзинах, что улучшает коэффициенты аппроксимации.
- FFD упорядочивает товары по убыванию размера и вызывает First-Fit, NFD упорядочивает товары по убыванию размера и вызывает Next-Fit.
- MFFD классифицирует предметы по размеру на четыре класса и улучшает FFD для предметов размером более половины ячейки.
- Фернандес де ла Вега и Люкер представили PTAS для упаковки в мусорные баки с адаптивным округлением входных данных.
-
Алгоритмы упаковки в ячейки
- Алгоритм Кармаркара-Карпа находит решение с максимальным размером OPT + O(log2(OPT)) за многочлен времени от n.
- Ротвосс предложил алгоритм с использованием не более OPT + O(log(OPT)⋅log(OPT)) бункеров.
- Хоберг и Ротвосс усовершенствовали алгоритм до OPT + O(log(OPT)) бункеров.
-
Точные алгоритмы
- Мартелло и Тот разработали точный алгоритм MTP для одномерной задачи.
- Алгоритм заполнения ячейки Korf и его усовершенствования.
- Шрайбер и Корф улучшили алгоритм заполнения ячейки, который на пять порядков быстрее BCP.
-
Упаковка в ячейки с высокой кратностью
- Особый случай упаковки в ячейки с небольшим количеством изделий разного размера.
- Алгоритмы для этого случая более эффективны, чем для общей задачи.
-
Упаковка в мусорное ведро с фрагментацией
- Вариант проблемы упаковки в мусорное ведро, где разрешается разбивать предметы на части.
- BP-SIF и BP-SPF имеют NP-жесткую сложность.
- Бертацци, Голден и Ванг предложили вариант BP-SIF с правилом разделения.
- Шахнай, Тамир и Йехезкели разработали схемы аппроксимации для BP-SIF и BP-SPF.
-
Производительность при разделении размеров изделий
- Важный случай упаковки в ячейки, когда размеры изделий образуют делимую последовательность.
- Эвристические алгоритмы находят оптимальное решение для делимых размеров.
-
Ограничения на количество элементов в ячейках
- Вариант упаковки ячеек с ограничениями по количеству элементов.
- Краузе, Шен и Шветман предложили эвристические алгоритмы для этой задачи.
- Келлерер и Пферши представили алгоритм с временным интервалом O(n2logn).
-
Неаддитивные функции
- Анили, Брамел и Симчи-Леви изучили ситуацию, когда стоимость корзины является функцией количества товаров.
- Коэн, Келлер, Миррокни и Задимогаддам изучили случайную величину размеров предметов.
-
Связанные проблемы
- Задача многоходового разделения по номерам: количество ячеек фиксировано, их размер может быть увеличен.
- Обратная задача об упаковке в бункер: количество контейнеров и их размеры фиксированы, размеры предметов могут быть изменены.
- Задача об упаковке корзины с максимальным количеством ресурсов: цель — максимизировать количество используемых ячеек.
- Двойная задача: количество ячеек фиксировано, цель — минимизировать общее количество или размер предметов.
- Задача о покрытии ячейки: размер ячейки ограничен снизу, цель — максимально увеличить количество используемых ячеек.
- Задача о справедливом неделимом распределении обязанностей: предметы представляют собой работу по дому, цель — распределить задания между людьми.
- Задача гильотинной резки: предметы и ячейки представляют собой двумерные прямоугольники.
- Задача эгоистичной упаковки в мусорное ведро: каждый предмет — игрок, цель — минимизировать его стоимость.
- Другие варианты: двухмерная, трехмерная упаковка в бункер, упаковка в бункер с доставкой.
-
Ресурсы
- BPPLIB: библиотека обзоров, кодов, тестов, генераторов, решателей и библиографии.
-
Описание библиотеки BPPLIB
- Библиотека содержит обзоры, коды, бенчмарки, генераторы, решатели и библиографию.
- Включает ссылки на различные ресурсы.
-
Основные разделы библиотеки
- Обзоры: исследования и анализ данных.
- Коды: программы для решения задач.
- Бенчмарки: тесты для оценки производительности.
- Генераторы: инструменты для создания данных.
- Решатели: программы для решения задач.
- Библиография: список литературы по теме.