Задача про пакування в ємності
У теорії складності обчислень задача про розміщення в ємності (посудини) — NP-складна комбінаторна задача. Задача полягає в пакуванні об'єктів визначеної завідомо форми в скінченне число ємностей (також кажуть контейнерів) - теж завідомо відомої заздалегідь форми у такий спосіб, аби число використаних ємностей було найменшим, або кількість чи об'єм предметів (які розміщують) були якнайбільшими.
Різновиди та методи розв'язування задач упакування
Існує безліч різновидів цієї задачі (двомірне пакування, лінійне пакування, пакування на вагу, за вартістю тощо), що можуть застосовуватись у різних галузях, як власне у питанні якнайвигіднішого наповнення ємностей, навантаження напіввагона чи вантажівки з ваговим обмеженням; створення резервних копій на знімних носіях тощо.
Оскільки задача є NP-складною, то застосування точного перебірного алгоритму припустиме лише за невеликих розмірностей. Зазвичай для розв'язування цієї задачі використовують евристичні наближені поліноміальні алгоритми.
Спрощений підхід
Попри те, що математики зараз часто розв'язують нікому не потрібні задачі й уважають повсякденне життя за частинний випадок, не можна забувати про те, що найкращий розв'язок — це той, який нескладний, доступний для нематематиків та підходить для використання у побутових умовах (неможливо вираховувати годинами чи добами ідеальний варіант, коли, на приклад, рішення потрібно було прийняти «ще на тому тижні», комп'ютер старий і повільний, і як на те, ще й вимкнулось світло). Ледачий (жадібний) підхід, очевидно, є незамінним при розв'язуванні життєвих задач. Алгоритм обробляє речі в довільному порядку. Кожну річ він намагається помістити у першу-ліпшу посудину, куди вона здатна ввійти. Якщо такої не знайде, він дозволить відкрити нову посудину (в житті — сумку або вантажний вагон, або контейнер) і ставить його туди. Точно те саме роблять люди, коли переміщують досить значні речі: ще одну сумку, возик або валізу беруть лише в тому разі, коли неможливо помістити все у ті сумки, які у вас є. А ось вирішити, чи вам їхати поїздом, чи автобусом, чи машиною, а, може, вам взагалі треба відправляти вантаж товарним вагоном, цей алгоритм вам не допоможе, а якщо і допоможе, то неповністю: він не вміє визначити, чи помнуться речі у посудинах в такому положенні, чи можна (а якщо можна — то чи припустимо) їх стиснути або згорнути, наскільки легко їх буде дістати тощо. У цьому і полягає перевага людського мозку над комп'ютером.
Жадібний алгоритм забезпечує коефіцієнт наближення 2, тобто, кількість задіяних посудин не перевищить більш, ніж у два рази ту найвигіднішу їх кількість, яку комп'ютер буде вираховувати неприпустимо довго.
Задача про розміщення в одновимірні однакові ємності
Постановка задачі
Нехай дана множина ємностей розміру і множина предметів розмірів . Необхідно знайти ціле число ємностей і розбиття множин на таких підмножин , що для всіх . Очевидно, що менше , тим вигідніший розв'язок вдалося знайти. Найменше можливе надалі позначатимемо OPT.
Пакування як задача лінійного програмування
Задача пакування в ємності може бути задана як задача лінійного програмування наступним чином:
Мінімізувати | ||
при обмеженнях | ||
де , якщо ємність використовується, й , якщо предмет поміщено в ємність .[1]
Наближені поліноміальні алгоритми
Найпростішими поліноміальними алгоритмами пакування вважають алгоритми Best Fit Decreasing — BFD (Наліпший підходящий за спаданням) і First Fit Decreasing — FFD (Перший підходящий за спаданням). Предмети упорядковують за незростанням розміру й послідовно розміщують або в ємність, у якій після того залишиться якнайменший вільний об'єм — BFD, або в першу ємність, у які він входить (просторочо та/або за вагою) — FFD. Доведено, що ці алгоритми використають не більш як
ємностей[2].
Однак для задачі упакування існують й асимптотично ε -оптимальні поліноміальні алгоритми.
Задача визначити, чи рівне OPT двом або трьом є NP-складною. Тому для довільного ε > 0 важко розмістити предмети до (3/2 − ε)OPT ємностей. (Якщо такий поліноміальний алгоритм існує, то за поліноміальний час можна визначити, чи розділиться n невід'ємних чисел на дві множини з однаковою сумою елементів. Однак відомо, що це питання NP-складне.) Відповідно, якщо P не збігається з NP, то для задачі упакування в ємності немає алгоритму наближеної схеми поліноміального часу (PTAS). З іншогобоку, для довільного ε >0 можна знайти рішення, як розмістити у не більш, ніж (1 + ε)OPT + 1 ємностей за поліноміальний час. Такі алгоритми відносять до асимптотичної PTAS.[3] Але оскільки в оцінці склааності цього класу алгоритмів обидві константи довільно залежать від ε, подібні алгоритми, на відміну від FFD и BFD, насправді зовсім некорисні для життєвих задач.
Ймовірнісний підхід
Для певного класу ймовірнісного розподілу розмірів розміщених предметів, що включає опуклі вгору та внизу функції розподілу, існує практичний поліноміальний алгоритм пакування, асимптотично оптимальний майже напевне за необмеженого росту числа предметів. Для розподілів поза цим класом можна будувати власні поліноміальні асимптотичні оптимальні алгоритми.[4].
Примітки
- Silvano Martello and Paolo Toth (1990). Knapsack problems. Chichester, UK: John Wiley and Sons. с. 221. ISBN 0471924202.
- Yue, Minyi (October 1991). A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm. 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. ISSN 0168-9673. doi:10.1007/BF02009683.
- Fernandez de la Vega, W.; Lueker, G. S. (December 1981). Bin packing can be solved within 1 + ε in linear time. Bin packing can be solved within 1 + ε in linear time. Combinatorica (Springer Berlin / Heidelberg) 1 (4): 349–355. ISSN 0209-9683. doi:10.1007/BF02579456.
- Смирнов А. В. Оптимізація процесу обробки даних в локальних мережах ЕОМ. — 1991.
Див. також
- Задача упаковки
- Задача про ранець
- Задача про суму підмножин
- Оптимізація
- Упаковка куль
Бібліографія
Джерела
- Бернард Корте, Єнс Вигон: Комбінаторна оптимізація. - Берлін/Хайдельберг: Спрінгер, 2008, ISBN 978-3-540-76918-7, Стор. 485
Мережеві посилання на матеріали
- PHP Class to pack files without exceeding a given size limit
- An implementation of several bin packing heuristics in Haskell, including FFD and MFFD.
- Cutting And Packing Algorithms Research Framework, including a number of bin packing algorithms and test data.
- A simple on-line bin-packing algorithm
- Optimizing Three-Dimensional Bin Packing
- Fpart : open-source command-line tool to pack files (C, BSD-licensed)
- Bin Packing and Cutting Stock Solver Algorithm
Увага! Бракує посилань на українські сайти. Хто їх знає - додайте їх сюди!
Перелік книг
- Korf, Richard E. (2002). A new algorithm for optimal bin packing. AAAI-02. Архів оригіналу за 27 грудня 2015. Процитовано 26 грудня 2015.
- Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8.
- Yue, Minyi (October 1991). A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm. 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. ISSN 0168-9673. doi:10.1007/BF02009683.
- Dósa, György (2007). The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9. У Chen, Bo; Paterson, Mike; Zhang, Guochuan. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. 4614/2007. Springer Berlin / Heidelberg. с. 1–11. ISBN 978-3-540-74449-8. ISSN 0302-9743. doi:10.1007/978-3-540-74450-4.
- Xia, Binzhou; Tan, Zhiyi (2010). Tighter bounds of the First Fit algorithm for the bin-packing problem. Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Applied Mathematics 158 (15): 1668–1675. ISSN 0166-218X. doi:10.1016/j.dam.2010.05.026.
- Garey, Michael R.; Johnson, David S. (1985). A 71/60 theorem for bin packing. A 71/60 theorem for bin packing*1. Journal of Complexity 1: 65–106. doi:10.1016/0885-064X(85)90022-6.
- Yue, Minyi; Zhang, Lei (July 1995). A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm. A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica 11 (3): 318–330. ISSN 0168-9673. doi:10.1007/BF02011198.
- Fernandez de la Vega, W.; Lueker, G. S. (December 1981). Bin packing can be solved within 1 + ε in linear time. Bin packing can be solved within 1 + ε in linear time. Combinatorica (Springer Berlin / Heidelberg) 1 (4): 349–355. ISSN 0209-9683. doi:10.1007/BF02579456.
- Lewis, R. (2009). A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing. Computers and Operations Research 36 (7): 2295–2310. doi:10.1016/j.cor.2008.09.004.
- Silvano Martello and Paolo Toth (1990), Knapsack Problems Algorithms and Computer Implementations.
- Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.
- David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
- Lodi A., Martello S., Monaci, M., Vigo, D. (2010) Two-Dimensional Bin Packing Problems. In V.Th. Paschos (Ed.), “Paradigms of Combinatorial Optimization”, Wiley/ISTE, p. 107-129
- Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
- Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011). Sharing-Aware Algorithms for Virtual Machine Colocation. Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367–378.