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

{{Завершити переклад|дата=лютий 2023}}
{{Помилки перекладу|дата=лютий 2023|en|Packing problems}}

[[Файл:Seissand.png|міні| [[Сфера|Сфери]] або [[Коло|кола]] розташовані нещільно (вгорі) і щільніше (внизу)]]
&nbsp;{{Головоломки|topics}}<templatestyles src="Module:Sidebar/styles.css"></templatestyles>
'''Проблеми упаковки'''{{Джерело}}&nbsp;— це клас [[Задача оптимізації|задач оптимізації]] в [[Математика|математиці]], які включають спробу пакування об'єктів разом у контейнери. Мета полягає в тому, щоб або упакувати один контейнер якомога щільніше, або упакувати всі об'єкти, використовуючи якомога менше контейнерів.

У [[Задача про пакування в ємності|задачі пакування контейнера]] надається:

* ''Контейнер'', як правило, дво- або тривимірна [[Опукла множина|опукла область]], можливо нескінченного розміру. Залежно від проблеми може бути надано кілька контейнерів.
* Набір може містити різні об'єкти із зазначеними розмірами або один об'єкт фіксованого розміру, який можна використовувати багаторазово.

== Пакування в нескінченному просторі ==
Багато з проблем, коли розмір контейнера збільшується в усіх напрямках, стають еквівалентними проблемі упаковки об’єктів якомога щільніше в нескінченному [[Евклідів простір|евклідовому просторі]] . Ця проблема є актуальною для ряду наукових дисциплін. [[Гіпотеза Кеплера]] постулювала оптимальне рішення для [[Задача про пакування куль|упаковки сфер]] за сотні років до того, як її правильність [[Доведення|довів]] Томас Каллістер Хейлз .<ref>{{Cite journal|last=Hudson|first=T. S.|last2=Harrowell|first2=P.|year=2011|title=Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures|journal=Journal of Physics: Condensed Matter|volume=23|issue=19|pages=194103|bibcode=2011JPCM...23s4103H|doi=10.1088/0953-8984/23/19/194103|pmid=21525553}}</ref>

=== Шестикутна упаковка кіл ===
[[Файл:Circle_packing_(hexagonal).svg|праворуч|міні| Гексагональна упаковка кіл на 2-вимірній евклідовій площині.]]
Найефективніший спосіб пакування кіл, шестикутне пакування, забезпечує приблизно 91% ефективності. <ref>{{Cite web|url=http://mathworld.wolfram.com/CirclePacking.html|title=Circle Packing}}</ref>

=== Сферичні упаковки більших розмірів ===
{{Main|Sphere packing}}
У трьох вимірах [[Щільне пакування рівних сфер|щільно упаковані]] структури пропонують найкращу ''гратчасту'' упаковку сфер і вважаються оптимальною з усіх упаковок. З «простими» сферичними упаковками в трьох вимірах («прості» ретельно визначені) є дев’ять можливих упаковок, які можна визначити. <ref>{{Cite journal|last=Smalley|first=I.J.|year=1963|title=Simple regular sphere packings in three dimensions|url=https://archive.org/details/sim_mathematics-magazine_1963-11_36_5/page/295|journal=Mathematics Magazine|volume=36|issue=5|pages=295–299|doi=10.2307/2688954|jstor=2688954}}</ref>

Тетраедри та [[Октаедр|октаедри]] разом можуть заповнити весь простір у структурі, яка відома як тетраедричні-октаедричні соти .
{| class="wikitable"
!Твердий
! Оптимальна щільність укладання грат
|-
| [[ікосаедр]]
| 0,836357. . . <ref name="Betke">{{Cite journal|last=Betke|first=Ulrich|last2=Henk|first2=Martin|year=2000|title=Densest lattice packings of 3-polytopes|journal=[[Computational Geometry (journal)|Computational Geometry]]|volume=16|issue=3|pages=157–186|arxiv=math/9909172|doi=10.1016/S0925-7721(00)00007-9|mr=1765181|doi-access=free}}</ref>
|-
| додекаедр
| (5&#x2009;+&#x2009;{{Radical|5}} )/8 = 0,904508. . . <ref name="Betke" />
|-
| октаедр
| 18/19 = 0,947368. . . <ref>Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. ''Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II'' 311–355 (1904).</ref>
|}
Моделювання, що поєднує локальні методи вдосконалення з випадковими упаковками, свідчить про те, що ґратчасті упаковки для ікосаедрів, додекаедрів і октаедрів є оптимальними в ширшому класі всіх упаковок. <ref name="Torquato">{{Cite journal|last=Torquato|first=S.|last2=Jiao|first2=Y.|date=Aug 2009|title=Dense packings of the Platonic and Archimedean solids|journal=Nature|volume=460|issue=7257|pages=876–879|arxiv=0908.4107|bibcode=2009Natur.460..876T|doi=10.1038/nature08239|issn=0028-0836|pmid=19675649}}</ref>

== Упаковка в 3-вимірні контейнери ==

=== Сфери в евклідову кулю ===
{{Main|Sphere packing in a sphere}}
Проблема знаходження найменшої кулі такої, що {{Mvar|k}} [[Неперетинні множини|непересічних]] відкритих [[Одинична сфера|одиничних кульок]] може бути упаковано всередині неї, має просту і повну відповідь у {{Mvar|n}} -вимірному евклідовому просторі, якщо <math>k \leq n+1</math>, і в нескінченномірному [[Гільбертів простір|гільбертовому просторі]] без обмежень. З точки зору включень куль, {{Mvar|k}} відкритих одиничних куль з центром <math>a_1, \dots, a_k</math> входять до кулі радіуса <math display="inline"> r_k = 1+\sqrt{2\big(1-\frac{1}{k}\big)}</math>, що є мінімальним для цієї конфігурації.

=== Однакові кулі в циліндрі ===
{{Main|Sphere packing in a cylinder}}
Визначте мінімальну висоту {{Mvar|h}} [[Циліндр|циліндра]] із заданим радіусом {{Mvar|R}}, який упакує {{Mvar|n}} однакових сфер радіуса {{Math|''r'' (< ''R'')}} . <ref>{{Cite journal|last=Stoyan|first=Y. G.|last2=Yaskov|first2=G. N.|year=2010|title=Packing identical spheres into a cylinder|journal=International Transactions in Operational Research|volume=17|pages=51–70|doi=10.1111/j.1475-3995.2009.00733.x}}</ref> Для малого радіуса {{Mvar|R}} сфери утворюють упорядковані структури, які називаються [[Стовпчаста окремість|стовпчастими структурами]] .

=== Багатогранники в сферах ===

== Упакування в 2-вимірні контейнери ==
[[Файл:Disk_pack10.svg|праворуч|міні|120x120пкс|Оптимальна упаковка 10 кружечків у коло]]
Досліджено багато варіантів двовимірних задач пакування.

=== Упакування кіл ===
{{Main|Circle packing}}
Вам дається {{Mvar|n}} [[Одиничне коло|одиничних кіл]], і ви повинні упакувати їх у найменший контейнер. Вивчено кілька типів контейнерів:
* Упакування кіл у <b id="mw3Q">колі</b>&nbsp;— тісно пов'язана з розподілом точок в одиничному колі з метою знаходження найбільшого мінімального відриву {{Mvar|d{{sub|n}}}} між точками. Оптимальні рішення доведено для {{Math|''n'' ≤ 13}} і {{Math|1=''n'' = 19}} .
* Упакування кіл у <b id="mw4w">квадраті</b>&nbsp;— тісно пов'язана з розподілом точок в одиничному квадраті з метою знаходження найбільшого мінімального відриву {{Mvar|d{{sub|n}}}} між точками. Для перетворення між цими двома формулюваннями задачі сторона квадрата для одиничних кіл буде <math>L = 2 + 2/d_n</math> .[[Файл:15_circles_in_a_square.svg|праворуч|міні|120x120пкс| Оптимальна упаковка 15 кружечків в квадраті]] Оптимальні рішення доведено для {{Math|''n'' ≤ 30}} .
* Упакування кіл у <b id="mw7Q">рівнобедреному прямокутному трикутнику</b>&nbsp;— хороші оцінки відомі для {{Math|''n'' < 300}} .
* Упакування кіл у <b id="mw8Q">рівносторонньому трикутнику</b>. Оптимальні рішення відомі для {{Math|''n'' < 13}}, а [[припущення]] доступні для {{Math|''n'' < 28}} .<ref>{{Cite journal|last=Melissen|first=J.|year=1995|title=Packing 16, 17 or 18 circles in an equilateral triangle|url=https://research.utwente.nl/en/publications/packing-16-17-of-18-circles-in-an-equilateral-triangle(b2172f19-9654-4ff1-9af4-59da1b6bef3d).html|journal=Discrete Mathematics|volume=145|issue=1–3|pages=333–342|doi=10.1016/0012-365X(95)90139-C}}</ref>

=== Упакування квадратів ===
Вам дається {{Mvar|n}} [[Одиничний квадрат|одиничних квадратів]], і ви повинні упакувати їх у найменший можливий контейнер, де тип контейнера різний:
* Упакування квадратів у <b id="mw_w">квадрат</b>: доведено оптимальні рішення для {{Mvar|n}} від 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 і будь-якого [[Цілі числа|цілого]] [[Квадратне число|квадрата]]
* Упакування квадратів у <b id="mwAQY">коло</b>: позитивніі рішення відомі для {{Math|''n'' ≤ 35}} .[[Файл:10_kvadratoj_en_kvadrato.svg|праворуч|міні|120x120пкс| Оптимальна упаковка 10 квадратів в квадраті]]

=== Упакування прямокутників ===
{{Main|Rectangle packing}}
* '''Упакування ідентичних прямокутників у прямокутник''' : проблема упакування кількох екземплярів одного [[прямокутник]]а розміром {{Math|(''l'',''w'')}} із можливістю повороту на 90° у більший прямокутник розміром {{Math|(''L'',''W'' )}} має деякі застосування, наприклад завантаження коробок. укладання [[Деревна маса|деревної маси]] . В прямокутник розміром (1600,1230) можна упакувати 147 прямокутників розміром (137,95).

== Пов'язані поля ==
Існують [[Теорема|теореми]] щодо розміщення прямокутників (і паралелепіпедів) у прямокутниках (кубоїдах) без проміжків або накладень:

: Прямокутник ''a'' × ''b'' можна запакувати смужками 1 × ''n'' тоді і тільки тоді, коли ''a'' ділиться на ''n'' або ''b'' ділиться на ''n''.<ref name="Gems2">{{Cite book
|title=Mathematical Gems II |last=Honsberger
|first=Ross
|year=1976
|publisher=[[The Mathematical Association of America]]
|page=67
|isbn=0-88385-302-7
}}</ref><ref name="Klarner">{{Cite journal|last=Klarner|first=D.A.|last2=Hautus|first2=M.L.J|year=1971|title=Uniformly coloured stained glass windows|journal=Proceedings of the London Mathematical Society|series=3|volume=23|issue=4|pages=613–628|doi=10.1112/plms/s3-23.4.613|author-link1=David A. Klarner}}</ref>
: Теорема де Брейна: коробку можна запакувати гармонічною цеглинкою ''a'' × ''ab'' × ''abc'', якщо коробка має розміри ''ap'' × ''abq'' × ''abcr'' для деяких [[Натуральне число|натуральних чисел]] ''p'', ''q'', ''r'' (тобто коробка є кратною цеглинці.)<ref name="Gems2" />

== Упакування нестандартних предметів ==
Упакування нестандартних об'єктів є проблемою, яка не підходить для рішень закритої форми; однак застосування до практичної науки про навколишнє середовище є досить важливою. Наприклад, частинки ґрунту неправильної форми упаковуються по-різному, оскільки розміри та форми змінюються, що призводить до важливих результатів для видів рослин щодо адаптації кореневих утворень і забезпечення руху води в ґрунті. <ref>C.Michael Hogan. 2010. [http://www.eoearth.org/article/Abiotic_factor?topic=49461 ''Abiotic factor''. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment]. Washington DC</ref>

== Див. також ==
* Упакування набору
* [[Задача про пакування в ємності|Проблема з упакування контейнера]]
* Головоломка Слотхаубера–Граатсми
* [[Головоломка Конвея]]
* [[Тетріс]]
* Проблема покриття
* [[Задача пакування рюкзака|Проблема ранця]]
* Тетраедрове упакування
* Еліпсоїдне упакування
* Проблема скорочення запасів
* [[Контактне число|Проблема з числом поцілунків]]
* [[Щільне пакування рівних сфер|Щільне упакування рівних сфер]]
* Випадкове закрите упакування
* Проблема з упакуванням стрічки

== Примітки ==
<references group="" responsive="0"></references>

== Література ==
* {{mathworld|urlname=KlarnersTheorem|title=Klarner's Theorem}}
* {{mathworld|urlname=deBruijnsTheorem|title=de Bruijn's Theorem}}

== Посилання ==
{{Commonscat}}
* [https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf Оптимізація тривимірного пакування контейнерів]{{ref-en}}
* [http://www.3dbinpacking.com API для 3D пакування контейнерів]{{ref-en}}
* [http://mathworld.wolfram.com/Packing.html Посилання на різні статті MathWorld про пакування] | [http://mathworld.wolfram.com/SquarePacking.html Пакування квадратів.]{{ref-en}}
* [https://erich-friedman.github.io/packing/index.html Пакувальний центр Еріха]{{ref-en}}
* [http://www.packomania.com/ www.packomania.com] Сайт з таблицями, графіками, калькуляторами, довідниками тощо.{{ref-en}}
* [http://demonstrations.wolfram.com/BoxPacking/ «Box Packing»] Еда Пегга молодшого, демонстраційний проект Wolfram, 2007.{{ref-en}}
* [http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html#overview Найвідоміші упаковки рівних кіл у колі, до 1100]{{ref-en}}
* [http://www.tlrun.com 3D пакування коробок і циліндрів з телескопіюванням]{{нд|дата=березень 2023}}