Задача об упаковке в контейнеры: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Нет описания правки |
|||
| Строка 6: | Строка 6: | ||
==Задача упаковки в одномерные одинаковые контейнеры== |
==Задача упаковки в одномерные одинаковые контейнеры== |
||
В простейшем случае упаковки в одномерные одинаковые контейнеры полиномиальные [[алгоритм]]ы ''Best Fit Decreasing'' и ''First Fit Decreasing'' используют не более <math>\frac{11}{9}N + 1</math> контейнеров (где <math>N</math> - число контейнеров при наилучшем решении задачи) |
В простейшем случае упаковки в одномерные одинаковые контейнеры обычно используют полиномиальные [[алгоритм]]ы ''Best Fit Decreasing- BFD '' (Наилучший подходящий по убыванию) и ''First Fit Decreasing - FFD'' (Первый подходящий по убыванию). Предметы упорядочивают по невозрастанию размеров и последовательно пакуют либо в контейнер, в котором после упаковки останется наименьший свободный объём - BFT, либо в первый контейнер куда он помещается - FFD. Доказано, что эти алгоритмы используют не более <math>\frac{11}{9}N + 1</math> контейнеров (где <math>N</math> - число контейнеров при наилучшем решении задачи)<ref>{{citation |
||
| last = Yue |
|||
| first = Minyi |
|||
| contribution = A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm |
|||
| journal = Acta Mathematicae Applicatae Sinica |
|||
| volume = 7 |
|||
| month = October |
|||
| year = 1991 |
|||
| pages = 321–331 |
|||
| doi = 10.1007/BF02009683 |
|||
| issn = 0168-9673 |
|||
| issue = 4 |
|||
| title = A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm }}</ref>. |
|||
=== Алгоритмы приближения === |
=== Алгоритмы приближения === |
||
Однако, существуют полиномиальные [[Алгоритм приближения|алгоритмы приближения]], которые могут решить задачу об упаковке со сколь угодно близким к оптимальному наперёд заданным качеством при условии неограниченного возрастания |
Однако, существуют полиномиальные [[Алгоритм приближения|алгоритмы приближения]], которые могут решить задачу об упаковке со сколь угодно близким к оптимальному наперёд заданным относительным качеством при условии неограниченного возрастания суммарного размера объектов в исходных массивах - это алгоритмы асимптотической [[схема приближения полиномиального времени|схемы приближения полиномиального времени]]. |
||
=== Упаковка |
=== Упаковка при вероятностной постановке задачи === |
||
Для некоторого класса [[Распределение вероятностей|вероятностных распределений]] размеров упаковываемых предметов, включая функции распределения выпуклые вверх и вниз, существует простой полиномиальный алгоритм упаковки асимптотически оптимальный [[почти наверное]] при неограниченном росте числа предметов <ref> |
Для некоторого класса [[Распределение вероятностей|вероятностных распределений]] размеров упаковываемых предметов, включая функции распределения выпуклые вверх и вниз, существует простой полиномиальный алгоритм упаковки асимптотически оптимальный [[почти наверное]] при неограниченном росте числа предметов <ref> |
||
{{статья |
{{статья |
||
| Строка 22: | Строка 34: | ||
}} </ref>. |
}} </ref>. |
||
Это выделяет задачу упаковки среди многих других NP-трудных задач, решения которых не могут быть приближены полиномиальными алгоритмами подобным образом. |
|||
== Примечания == |
== Примечания == |
||
Версия от 15:45, 17 апреля 2013
В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.
Разновидности и методы решения задач упаковки
Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т.п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т.д. Так как задача является NP-трудной зачастую используют алгоритмы с эвристическим и метаэвристическим методом решения для получения оптимальных результатов. Также активно используются методы искусственного интеллекта, как, например, нейронные сети.
Задача упаковки в одномерные одинаковые контейнеры
В простейшем случае упаковки в одномерные одинаковые контейнеры обычно используют полиномиальные алгоритмы Best Fit Decreasing- BFD (Наилучший подходящий по убыванию) и First Fit Decreasing - FFD (Первый подходящий по убыванию). Предметы упорядочивают по невозрастанию размеров и последовательно пакуют либо в контейнер, в котором после упаковки останется наименьший свободный объём - BFT, либо в первый контейнер куда он помещается - FFD. Доказано, что эти алгоритмы используют не более контейнеров (где - число контейнеров при наилучшем решении задачи)[1].
Алгоритмы приближения
Однако, существуют полиномиальные алгоритмы приближения, которые могут решить задачу об упаковке со сколь угодно близким к оптимальному наперёд заданным относительным качеством при условии неограниченного возрастания суммарного размера объектов в исходных массивах - это алгоритмы асимптотической схемы приближения полиномиального времени.
Упаковка при вероятностной постановке задачи
Для некоторого класса вероятностных распределений размеров упаковываемых предметов, включая функции распределения выпуклые вверх и вниз, существует простой полиномиальный алгоритм упаковки асимптотически оптимальный почти наверное при неограниченном росте числа предметов [2].
Это выделяет задачу упаковки среди многих других NP-трудных задач, решения которых не могут быть приближены полиномиальными алгоритмами подобным образом.
Примечания
- ↑ Yue, Minyi (1991), "A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm", Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, doi:10.1007/BF02009683, ISSN 0168-9673
{{citation}}:|contribution=игнорируется (справка); Неизвестный параметр|month=игнорируется (справка) - ↑ Смирнов А. В. Оптимизация процесса обработки данных в локальных сетях ЭВМ : Дисс. к.ф.-м.н. Специальность 01.01.09 — Математическая кибернетика. — 1991.
