Перегляд вихідного коду сторінки Задача про пакування в ємності

{{сирий переклад|дата=липень 2020}}
У [[теорія складності обчислень|теорії складності обчислень]] '''задача про [[розміщення]] в ємності (посудини)''' — [[Класс NP|NP-складна]] [[комбінаторика|комбінаторна]] задача. Задача полягає в пакуванні об'єктів визначеної завідомо форми в скінченне число [[ємність|ємностей]] (також кажуть [[контейнер]]ів) - теж завідомо відомої заздалегідь форми у такий спосіб, аби число використаних ємностей було найменшим, або кількість чи об'єм предметів (які розміщують) були якнайбільшими.

== Різновиди та методи розв'язування задач упакування ==
Існує безліч різновидів цієї задачі ([[двомірне пакування]], [[лінійне пакування]], пакування на вагу, за вартістю тощо), що можуть застосовуватись у різних галузях, як власне у питанні якнайвигіднішого наповнення ємностей, навантаження напіввагона чи вантажівки з ваговим обмеженням; створення резервних копій на знімних носіях тощо.

Оскільки задача є [[NP-складність|NP-складною]], то застосування точного перебірного алгоритму припустиме лише за невеликих розмірностей. Зазвичай для розв'язування цієї задачі використовують [[евристика|евристичні]] наближені поліноміальні алгоритми.

== Спрощений підхід ==

Попри те, що математики зараз часто розв'язують нікому не потрібні задачі й уважають повсякденне життя за частинний випадок, не можна забувати про те, що найкращий розв'язок&nbsp;— це той, який нескладний, доступний для нематематиків та підходить для використання у побутових умовах (неможливо вираховувати годинами чи добами ідеальний варіант, коли, на приклад, рішення потрібно було прийняти «ще на тому тижні», комп'ютер старий і повільний, і як на те, ще й вимкнулось світло). '''Ледачий (жадібний) підхід, очевидно, є незамінним при розв'язуванні життєвих задач'''. Алгоритм обробляє речі в довільному порядку. Кожну річ він намагається помістити у першу-ліпшу посудину, куди вона здатна ввійти. Якщо такої не знайде, він дозволить відкрити нову посудину (в житті&nbsp;— сумку або вантажний вагон, або контейнер) і ставить його туди. Точно те саме роблять люди, коли переміщують досить значні речі: ще одну сумку, возик або валізу беруть лише в тому разі, коли неможливо помістити все у ті сумки, які у вас є. А ось вирішити, чи вам їхати поїздом, чи автобусом, чи машиною, а, може, вам взагалі треба відправляти вантаж товарним вагоном, цей алгоритм вам не допоможе, а якщо і допоможе, то неповністю: він не вміє визначити, чи помнуться речі у посудинах в такому положенні, чи можна (а якщо можна&nbsp;— то чи припустимо) їх стиснути або згорнути, наскільки легко їх буде дістати тощо. У цьому і полягає перевага людського мозку над комп'ютером.

Жадібний алгоритм забезпечує коефіцієнт наближення 2, тобто, кількість задіяних посудин не перевищить більш, ніж у два рази ту найвигіднішу їх кількість, яку комп'ютер буде вираховувати неприпустимо довго.

== Задача про розміщення в одновимірні однакові ємності ==

=== Постановка задачі ===
Нехай дана множина ємностей розміру <math>V</math> і множина <math>n</math> предметів розмірів <math>a_1,\dots,a_n</math>. Необхідно знайти ціле число ємностей <math>B</math> і [[розбиття множин]] <math>\{1,\dots,n\}</math> на <math>B</math> таких підмножин <math>S_1 \cup \dots \cup S_B</math>, що <math>\sum_{i \in S_k} a_i \leq V</math> для всіх <math>k=1,\dots,B</math>. Очевидно, що менше <math>B</math>, тим вигідніший розв'язок вдалося знайти. Найменше можливе <math>B</math> надалі позначатимемо '''OPT'''.

=== Пакування як задача [[лінійне програмування|лінійного програмування]] ===
Задача пакування в ємності може бути задана як задача лінійного програмування наступним чином:
{|
|-
|colspan="2"|Мінімізувати <math> B = \sum_{i=1}^n y_i</math>
|
|-
|при обмеженнях
|<math>\sum_{j=1}^n a_j x_{ij} \leq V y_i,</math>
|<math>\forall i \in \{1,\ldots,n\}</math>
|-
|
|<math>\sum_{i=1}^n x_{ij} = 1,</math>
|<math>\forall j \in \{1,\ldots,n\}</math>
|-
|
|<math> y_i \in \{0,1\},</math>
|<math>\forall i \in \{1,\ldots,n\}</math>
|-
|
|<math> x_{ij} \in \{0,1\},</math>
|<math>\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}</math>
|}
де <math> y_i = 1</math>, якщо ємність <math>i</math> використовується, й <math> x_{ij} = 1</math>, якщо предмет <math>j</math> поміщено в ємність <math>i</math>.<ref name=Martello1990>{{cite book|last=Silvano Martello and Paolo Toth|title=Knapsack problems|year=1990|publisher=John Wiley and Sons|location=Chichester, UK|isbn=0471924202|page=[https://archive.org/details/knapsackproblems0000mart/page/221 221]|url=https://archive.org/details/knapsackproblems0000mart/page/221}}</ref>

=== Наближені поліноміальні алгоритми ===
Найпростішими поліноміальними [[алгоритм]]ами пакування вважають алгоритми ''Best Fit Decreasing — BFD '' (Наліпший підходящий за спаданням) і ''First Fit Decreasing — FFD'' (Перший підходящий за спаданням). Предмети упорядковують за незростанням розміру й послідовно розміщують або в ємність, у якій після того залишиться якнайменший вільний об'єм — BFD, або в першу ємність, у які він входить (просторочо та/або за вагою) — FFD. Доведено, що ці алгоритми використають не більш як
 
<math>\frac{11}{9}OPT + 1</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>.

Однак для задачі упакування існують й асимптотично ε -оптимальні поліноміальні алгоритми.

Задача визначити, чи рівне '''OPT''' двом або трьом є NP-складною. Тому для довільного ε > 0 важко розмістити предмети до '''(3/2 − ε)OPT''' ємностей. (Якщо такий поліноміальний алгоритм існує, то за поліноміальний час можна визначити, чи розділиться ''n'' невід'ємних чисел на дві множини з однаковою сумою елементів. Однак відомо, що це питання NP-складне.) Відповідно, якщо P не збігається з NP, то для задачі упакування в ємності немає алгоритму [[Схема наближення до поліноміального часу|схеми наближення до поліноміального часу (PTAS)]]. З іншогобоку, для довільного ε >0  можна знайти рішення, як розмістити у не більш, ніж '''(1 + ε)OPT + 1''' ємностей за поліноміальний час. Такі алгоритми відносять до асимптотичної PTAS.<ref> {{citation
  | last1 = Fernandez de la Vega
  | first1 = W.
  | last2 = Lueker
  | first2 = G. S.
  | contribution = Bin packing can be solved within 1 + ε in linear time
  | journal = Combinatorica
  | publisher = Springer Berlin / Heidelberg
  | volume = 1
  | month = December
  | year = 1981
  | pages = 349–355
  | doi = 10.1007/BF02579456
  | issn = 0209-9683
  | issue = 4
  | title = Bin packing can be solved within 1 + ε in linear time }}</ref> Але оскільки в оцінці склааності цього класу алгоритмів <math> a n^b</math> обидві константи довільно залежать від ε, подібні алгоритми, на відміну від FFD и BFD, насправді зовсім некорисні для життєвих задач.

=== Ймовірнісний підхід ===
Для певного класу [[розподіл ймовірностей|ймовірнісного розподілу]] розмірів розміщених предметів, що включає опуклі вгору та внизу функції розподілу, існує практичний поліноміальний алгоритм пакування, асимптотично оптимальний [[майже напевне]] за необмеженого росту числа предметів. Для розподілів поза цим класом можна будувати власні поліноміальні асимптотичні оптимальні алгоритми.<ref>
{{стаття
|автор=Смирнов А. В.
|заголовок=Оптимізація процесу обробки даних в локальних мережах ЕОМ
|тип=Дис. к.ф.-м.н. Спеціальність 01.01.09 — Математична кібернетика
|рік=1991
|сторінок=80
|ref=Смирнов А.В., дис.
}} </ref>.

== Примітки ==
{{reflist}}

== Див. також ==
* [[Задача упаковки]]
* [[Задача про ранець]]
* [[Задача про суму підмножин]]
* [[Оптимізація]]
* [[Упаковка куль]]

== Бібліографія ==
=== Джерела ===
* Бернард Корте, Єнс Вигон: ''Комбінаторна оптимізація''. - Берлін/Хайдельберг: Спрінгер, 2008, ISBN 978-3-540-76918-7, Стор. 485

=== Мережеві посилання на матеріали ===

*[http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html PHP Class to pack files without exceeding a given size limit] {{Webarchive|url=https://web.archive.org/web/20151227065414/http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html |date=27 грудня 2015 }}
*[http://www.cs.unc.edu/~bbb/#bin-packing An implementation of several bin packing heuristics in Haskell] {{Webarchive|url=https://web.archive.org/web/20200701162822/http://www.cs.unc.edu/~bbb/#bin-packing |date=1 липня 2020 }}, including FFD and MFFD.
*[http://code.google.com/p/caparf/ Cutting And Packing Algorithms Research Framework] {{Webarchive|url=https://web.archive.org/web/20151231213611/https://code.google.com/p/caparf/ |date=31 грудня 2015 }}, including a number of bin packing algorithms and test data.
*[http://dl.acm.org/citation.cfm?id=3833&jmp=abstract&dl=portal&dl=ACM A simple on-line bin-packing algorithm]
*[http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf Optimizing Three-Dimensional Bin Packing] {{Webarchive|url=https://web.archive.org/web/20160305005837/http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf |date=5 березня 2016 }}
*[http://sourceforge.net/projects/fpart/ Fpart : open-source command-line tool to pack files (C, BSD-licensed)] {{Webarchive|url=https://web.archive.org/web/20151201090119/http://sourceforge.net/projects/fpart/ |date=1 грудня 2015 }}
*[http://www.codeproject.com/Articles/706136/Csharp-Bin-Packing-Cutting-Stock-Solver Bin Packing and Cutting Stock Solver Algorithm] {{Webarchive|url=https://web.archive.org/web/20151227010226/http://www.codeproject.com/Articles/706136/Csharp-Bin-Packing-Cutting-Stock-Solver |date=27 грудня 2015 }}

Увага! Бракує посилань на українські сайти. Хто їх знає - додайте їх сюди!

=== Перелік книг ===
# {{citation
  | last = Korf
  | first = Richard E.
  | title = A new algorithm for optimal bin packing.
  | conference = AAAI-02
  | year = 2002
  | url = http://aaaipress.org/Papers/AAAI/2002/AAAI02-110.pdf
  | accessdate = 26 грудня 2015
  | archiveurl = https://web.archive.org/web/20151227014616/http://aaaipress.org/Papers/AAAI/2002/AAAI02-110.pdf
  | archivedate = 27 грудня 2015
  | deadurl = yes
  }}
# {{citation
  | last = Vazirani
  | first = Vijay V.
  | authorlink = Vijay Vazirani
  | title = Approximation Algorithms
  | publisher = Springer
  | year = 2003
  | location = Berlin
  | isbn = 3-540-65367-8 }}
# {{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
  |date=October 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 }}
# {{citation
  | last = Dósa
  | first = György
  | contribution = The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9
  | title = Combinatorics, Algorithms, Probabilistic and Experimental Methodologies
  | publisher = Springer Berlin / Heidelberg
  | volume = 4614/2007
  | year = 2007
  | pages = 1–11
  | isbn = 978-3-540-74449-8
  | doi = 10.1007/978-3-540-74450-4
  | issn = 0302-9743
  | editor1-last = Chen
  | editor1-first = Bo
  | editor2-last = Paterson
  | editor2-first = Mike
  | editor3-last = Zhang
  | editor3-first = Guochuan }}
# {{citation
  | last1 = Xia
  | first1 = Binzhou
  | last2 = Tan
  | first2 = Zhiyi
  | contribution = Tighter bounds of the First Fit algorithm for the bin-packing problem
  | journal = Discrete Applied Mathematics
  | volume = 158
  | year = 2010
  | pages = 1668–1675
  | doi = 10.1016/j.dam.2010.05.026
  | issn = 0166-218X
  | issue = 15
  | title = Tighter bounds of the First Fit algorithm for the bin-packing problem}}
# {{citation
  | last1 = Garey
  | first1 = Michael R.
  | authorlink1 = Michael R. Garey
  | last2 = Johnson
  | first2 = David S.
  | authorlink2 = Девід Джонсон
  | contribution = A 71/60 theorem for bin packing
  | journal = Journal of Complexity
  | volume = 1
  | year = 1985
  | pages = 65–106
  | doi = 10.1016/0885-064X(85)90022-6
  | title = A 71/60 theorem for bin packing*1 }}
# {{citation
  | last1 = Yue
  | first1 = Minyi
  | last2 = Zhang
  | first2 = Lei
  | contribution = A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm
  | journal = Acta Mathematicae Applicatae Sinica
  | volume = 11
  |date=July 1995
  | pages = 318–330
  | doi = 10.1007/BF02011198
  | issn = 0168-9673
  | issue = 3
  | title = A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm }}
# {{citation
  | last1 = Fernandez de la Vega
  | first1 = W.
  | last2 = Lueker
  | first2 = G. S.
  | contribution = Bin packing can be solved within 1 + ε in linear time
  | journal = Combinatorica
  | publisher = Springer Berlin / Heidelberg
  | volume = 1
  |date=December 1981
  | pages = 349–355
  | doi = 10.1007/BF02579456
  | issn = 0209-9683
  | issue = 4
  | title = Bin packing can be solved within 1 + ε in linear time }}
# {{citation
  | last = Lewis
  | first = R.
  | journal = Computers and Operations Research
  | volume = 36
  | year = 2009
  | pages = 2295–2310
  | doi = 10.1016/j.cor.2008.09.004
  | issue = 7
  | title = A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing }}
# 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.&nbsp;226.
# David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. [http://www.math.ucsd.edu/~fan/ron/papers/74_04_one_dimensional_packing.pdf Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms] {{Webarchive|url=https://web.archive.org/web/20161009150556/http://www.math.ucsd.edu/~fan/ron/papers/74_04_one_dimensional_packing.pdf |date=9 жовтня 2016 }}. 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.&nbsp;107-129
# Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
# {{citation
  | last1 = Sindelar
  | first1 = Michael
  | last2 = Sitaraman
  | first2 = Ramesh
  | authorlink2 = Ramesh Sitaraman
| last3 = Shenoy
 | first3 = Prashant
  | journal = Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011
|pages = 367–378
  | year = 2011
  | title = Sharing-Aware Algorithms for Virtual Machine Colocation}}

{{NP-повні задачі}}

[[Категорія:NP-повні задачі]]
[[Категорія:Задачі упаковки]]