Задача пакування

Сфери або кола розташовані нещільно (вгорі) і щільніше (внизу)

Проблеми упаковки^{[джерело?]} — це клас задач оптимізації в математиці, які включають спробу пакування об'єктів разом у контейнери. Мета полягає в тому, щоб або упакувати один контейнер якомога щільніше, або упакувати всі об'єкти, використовуючи якомога менше контейнерів.

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

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

Пакування в нескінченному просторі

Багато з проблем, коли розмір контейнера збільшується в усіх напрямках, стають еквівалентними проблемі упаковки об’єктів якомога щільніше в нескінченному евклідовому просторі . Ця проблема є актуальною для ряду наукових дисциплін. Гіпотеза Кеплера постулювала оптимальне рішення для упаковки сфер за сотні років до того, як її правильність довів Томас Каллістер Хейлз .^[1]

Шестикутна упаковка кіл

Найефективніший спосіб пакування кіл, шестикутне пакування, забезпечує приблизно 91% ефективності. ^[2]

Сферичні упаковки більших розмірів

Докладніше: Sphere packing

У трьох вимірах щільно упаковані структури пропонують найкращу гратчасту упаковку сфер і вважаються оптимальною з усіх упаковок. З «простими» сферичними упаковками в трьох вимірах («прості» ретельно визначені) є дев’ять можливих упаковок, які можна визначити. ^[3]

Тетраедри та октаедри разом можуть заповнити весь простір у структурі, яка відома як тетраедричні-октаедричні соти .

Твердий	Оптимальна щільність укладання грат
ікосаедр	0,836357. . . ^[4]
додекаедр	(5 + √5 )/8 = 0,904508. . . ^[4]
октаедр	18/19 = 0,947368. . . ^[5]

Моделювання, що поєднує локальні методи вдосконалення з випадковими упаковками, свідчить про те, що ґратчасті упаковки для ікосаедрів, додекаедрів і октаедрів є оптимальними в ширшому класі всіх упаковок. ^[6]

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

Сфери в евклідову кулю

Докладніше: Sphere packing in a sphere

Проблема знаходження найменшої кулі такої, що $k$ непересічних відкритих одиничних кульок може бути упаковано всередині неї, має просту і повну відповідь у $n$ -вимірному евклідовому просторі, якщо $k\leq n+1$ , і в нескінченномірному гільбертовому просторі без обмежень. З точки зору включень куль, $k$ відкритих одиничних куль з центром $a_{1},\dots ,a_{k}$ входять до кулі радіуса ${\textstyle r_{k}=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ , що є мінімальним для цієї конфігурації.

Однакові кулі в циліндрі

Докладніше: Sphere packing in a cylinder

Визначте мінімальну висоту $h$ циліндра із заданим радіусом $R$ , який упакує $n$ однакових сфер радіуса $r (< R)$ . ^[7] Для малого радіуса $R$ сфери утворюють упорядковані структури, які називаються стовпчастими структурами .

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

Упакування в 2-вимірні контейнери

Досліджено багато варіантів двовимірних задач пакування.

Упакування кіл

Докладніше: Circle packing

Вам дається $n$ одиничних кіл, і ви повинні упакувати їх у найменший контейнер. Вивчено кілька типів контейнерів:

Упакування кіл у колі — тісно пов'язана з розподілом точок в одиничному колі з метою знаходження найбільшого мінімального відриву $d n$ між точками. Оптимальні рішення доведено для $n \leq 13$ і $n = 19$ .
Упакування кіл у квадраті — тісно пов'язана з розподілом точок в одиничному квадраті з метою знаходження найбільшого мінімального відриву $d n$ між точками. Для перетворення між цими двома формулюваннями задачі сторона квадрата для одиничних кіл буде $L=2+2/d_{n}$ .
Оптимальна упаковка 15 кружечків в квадраті
Оптимальні рішення доведено для $n \leq 30$ .
Упакування кіл у рівнобедреному прямокутному трикутнику — хороші оцінки відомі для $n < 300$ .
Упакування кіл у рівносторонньому трикутнику. Оптимальні рішення відомі для $n < 13$ , а припущення доступні для $n < 28$ .^[8]

Упакування квадратів

Вам дається $n$ одиничних квадратів, і ви повинні упакувати їх у найменший можливий контейнер, де тип контейнера різний:

Упакування квадратів у квадрат: доведено оптимальні рішення для $n$ від 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 і будь-якого цілого квадрата
Упакування квадратів у коло: позитивніі рішення відомі для $n \leq 35$ .
Оптимальна упаковка 10 квадратів в квадраті

Упакування прямокутників

Докладніше: Rectangle packing

Упакування ідентичних прямокутників у прямокутник : проблема упакування кількох екземплярів одного прямокутника розміром $(l, w)$ із можливістю повороту на 90° у більший прямокутник розміром $(L, W)$ має деякі застосування, наприклад завантаження коробок. укладання деревної маси . В прямокутник розміром (1600,1230) можна упакувати 147 прямокутників розміром (137,95).

Пов'язані поля

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

Прямокутник a × b можна запакувати смужками 1 × n тоді і тільки тоді, коли a ділиться на n або b ділиться на n.^[9]^[10]

Теорема де Брейна: коробку можна запакувати гармонічною цеглинкою a × ab × abc, якщо коробка має розміри ap × abq × abcr для деяких натуральних чисел p, q, r (тобто коробка є кратною цеглинці.)^[9]

Упакування нестандартних предметів

Упакування нестандартних об'єктів є проблемою, яка не підходить для рішень закритої форми; однак застосування до практичної науки про навколишнє середовище є досить важливою. Наприклад, частинки ґрунту неправильної форми упаковуються по-різному, оскільки розміри та форми змінюються, що призводить до важливих результатів для видів рослин щодо адаптації кореневих утворень і забезпечення руху води в ґрунті. ^[11]

Див. також

Упакування набору
Проблема з упакування контейнера
Головоломка Слотхаубера–Граатсми
Головоломка Конвея
Тетріс
Проблема покриття
Проблема ранця
Тетраедрове упакування
Еліпсоїдне упакування
Проблема скорочення запасів
Проблема з числом поцілунків
Щільне упакування рівних сфер
Випадкове закрите упакування
Проблема з упакуванням стрічки

Примітки

↑ Hudson, T. S.; Harrowell, P. (2011). Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures. Journal of Physics: Condensed Matter. 23 (19): 194103. Bibcode:2011JPCM...23s4103H. doi:10.1088/0953-8984/23/19/194103. PMID 21525553.
↑ Circle Packing.
↑ Smalley, I.J. (1963). Simple regular sphere packings in three dimensions. Mathematics Magazine. 36 (5): 295—299. doi:10.2307/2688954. JSTOR 2688954.
↑ ^а ^б Betke, Ulrich; Henk, Martin (2000). Densest lattice packings of 3-polytopes. Computational Geometry. 16 (3): 157—186. arXiv:math/9909172. doi:10.1016/S0925-7721(00)00007-9. MR 1765181.
↑ Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II 311–355 (1904).
↑ Torquato, S.; Jiao, Y. (Aug 2009). Dense packings of the Platonic and Archimedean solids. Nature. 460 (7257): 876—879. arXiv:0908.4107. Bibcode:2009Natur.460..876T. doi:10.1038/nature08239. ISSN 0028-0836. PMID 19675649.
↑ Stoyan, Y. G.; Yaskov, G. N. (2010). Packing identical spheres into a cylinder. International Transactions in Operational Research. 17: 51—70. doi:10.1111/j.1475-3995.2009.00733.x.
↑ Melissen, J. (1995). Packing 16, 17 or 18 circles in an equilateral triangle. Discrete Mathematics. 145 (1–3): 333—342. doi:10.1016/0012-365X(95)90139-C.
↑ ^а ^б Honsberger, Ross (1976). Mathematical Gems II. The Mathematical Association of America. с. 67. ISBN 0-88385-302-7.
↑ Klarner, D.A.; Hautus, M.L.J (1971). Uniformly coloured stained glass windows. Proceedings of the London Mathematical Society. 3. 23 (4): 613—628. doi:10.1112/plms/s3-23.4.613.
↑ C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC