Sciencemag.cz
Doporučujeme
Už Kepler si položil otázku, jak můžeme koulemi co nejhustěji vyplnit daný prostor (typicky krabici). Řešením je krychlová mřížka, kdy koule v další vrstev dáváme do středu mezi čtyřmi pod nimi. Kepler toto řešení navrhl, ale trvalo ještě přes 400 let, než se podařilo dokázat, že jde opravdu o nejefektivnější způsob.
Obecně je přitom problém optimálního balení různých předmětů velmi složitý. Spadá do kategorie NP-hard, kdy vůbec nemáme k dispozici v rozumném čase pracující algoritmus (nebo jinak, nemáme k dispozici algoritmus, který je schopen fungovat rozumně rychle při růstu velikosti vstupu). Problém je i najít dostatečně rychle nějaké řešení přibližné (nikoliv optimální, ale dost dobré). Problém má přitom řadu variant, v jiné třeba máme u předmětů zadané hmotnosti a u krabice nosnost.
Viz také: Algoritmy pro balení jsou překvapivě složité
A zrovna tahle úloha zdaleka nemá jen teoretický význam.
Tým výzkumníků z MITu a společnosti Inkbit (spinout MITu), který vedl Wojciech Matusik, nyní vypracoval následující metodu, která by měla dávat slušné výsledky v rozumném čase. Prvním krokem je seřadit si předměty podle pořadí, v němž je budeme dávat do krabice. Jedním z možných přístupů je například začít s největšími objekty a skončit s nejmenšími. Dalším krokem je umístění jednotlivých objektů do kontejneru. Pro usnadnění tohoto procesu je kontejner „voxelizován“, což znamená, že je reprezentován 3D mřížkou složenou z voxelů (krychliček). Mřížka ukazuje, které části kontejneru jsou již zaplněny a které jsou volné. Objekt, který má být zabalen, je rovněž voxelizován. Aby algoritmus zjistil, kolik místa je pro tento objekt k dispozici, vypočítá v každém voxelu veličinu nazvanou kolizní metrika. Funguje to tak, že se střed objektu umístí do každého voxelu v kontejneru a poté se spočítá počet obsazených voxelů, se kterými se objekt překrývá („koliduje“). Objekt lze umístit pochopitelně pouze do míst, kde je překryv nulový
Dalším krokem je projít všechna možná („povolená“) umístění a určit nejlepší dostupnou pozici pro umístění objektu. Pro tento úkol vědci vypočítají v každém voxelu další metriku, která je navržena tak, aby lokálně maximalizovala hustotu balení. Tato metrika měří mezery mezi objektem a stěnou kontejneru nebo mezi nově přidávaným objektem a těmi objekty, které se již v kontejneru nacházejí. Cílem je minimalizovat prázdné místo (mezery mezi objekty), a toho lze dosáhnout umístěním objektu tam, kde je hodnota metriky nejnižší. Je to něco jako Tetris.
Tím to však nekončí, objekt lze vložit v různé pozici (orientaci). Příslušnou metriku tedy budeme počítat i pro různé orientace. Poslední podmínka je, aby zabalení, respektive rozbalení, bylo fyzikálně možné. (Dva náramky nedokážeme umístit tak, aby byly spojené jako oka řetězu. Poznámka: Zde je pak ještě možnost, že fyzikálně to půjde, ale budeme muset kus vybalit, malý předmět dát pod velké; ale to průvodní tisková zpráva neřeší, i když v praxi je to důležité, protože potřebujeme zabalit nejen efektivně, ale také rozumně rychle.)
Pro výpočty autoři studie použili rychlou Fourierovu transformaci, což má být v úlohách balení novinka. Výsledkem tohoto přístupu má být zrychlení o několik řádů, kdy se např. mnohé složité operace transformují na násobení apod. V jedné ukázce nový algoritmus efektivně umístil 670 objektů za pouhých 40 sekund a dosáhl hustoty balení přibližně 36 %. Uspořádání 6 596 objektů s hustotou zabalení 37,30 % trvalo dvě hodiny. „Hustota, které dosahujeme, se blíží 40 %, a je tak výrazně lepší než hustota dosahovaná tradičními algoritmy,“ uvádí W. Matusik, „a je také rychlejší.“
„Tato práce představuje průlomové řešení dlouho trvajícího problému,“ komentoval výsledek Bedřich Beneš, profesor informatiky na Purdue University a absolvent ČVUT v Praze. „Navrhované řešení maximalizuje hustotu balení a má potenciál najít uplatnění v mnoha praktických oblastech, od robotiky až po výrobu. Řešení je navíc vhodné pro počítačem řízené prostředí.“
Postup může být samozřejmě užitečný pro skladové a přepravní společnosti, kde se běžně balí různé předměty do krabic různých velikostí. Speciálně jsou zajímavé také aplikace v oblasti 3D tisku. Díly se běžně vyrábějí v dávkách a ukládají se do zásobníků. Současné přístupy však podle W. Matusika mají velmi omezené využití objemu přepravek, obvykle kolem 20 %.
Zůstává zde samozřejmě ještě celá řada otázek. Průvodní tisková zpráva zmiňuje třeba to, jak zefektivnit balení předmětů, které lze částečně stlačovat/ohýbat/kroutit, nebo jak balit objekty s částmi spojenými klouby, které můžeme do krabice vložit ve více podobách.
Click to access spectralPacking_optimized.pdf
„Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects“
Zdroj: Massachusetts Institute of Technology / Phys.org
Jen drobna poznamka. Keplerovo reseni pro vyplneni prostoru koulemi plati pouze pro nekonecny prostor. Pokud mame zabalit koule do konecne krabice, tak jejich optimalni rozmisteni silne zavisi na rozmerech krabice.
Ten popis Keplerova řešení je nesprávný, protože takto by vznikla mřížka kubická prostorově centrovaná (BCC), zatímco nejtěsnější uspořádání koulí v prostoru mají mřížky kubická plošně centrovaná (FCC) a hexagonální těsně uspořádaná (HCP).
Tyty mřížky se prakticky realizují tak, že vyskládáme rovinu koulemi jak nejtěsněji to jde, což bude tehdy, když budou jejich středy ležet ve vrcholech rovnostranných trojúhelníků, a další vrstvy pak klademe nad středy trojúhelníků vrstvy předchozí. Podle toho, jak uložíme třetí vrstvu vůči první, pak vznikne mřížka HCP (koule 3. vrstvy dáme nad koule 1. vrstvy, takže se budou střídat jen 2 vůči sobě posunuté vrstvy) nebo FCC (středy koulí 3. vrstvy dáme do míst, kde jsou v 1. vrstvě díry, takže se nám budou střídat 3 různě posunuté vrstvy).
tak uplne nevim, ale uvadi se, ze to keplerovo reseni plati. v puvodnim textu byl zminen jen ctverec se stredy. ted tedy dal ctu, ze kepler tvrdil, ze ctverec i sestiuhelnik maji tuto vlastnost. a kdyz na ctverec pokladam dalsi vrstvu do nejnizsiho bodu, tak je to totozne se stredem, ne? a pokladam-li do stredu rovnostranneho trojuhelnika, pak by to vlastne – pro nejsnazsi pochopeni – byla trojuhelnikova mrizka se stejnym principem? (teda samozrejme vlastniho clanku se to netyka)
a dekuji za upresneni/opravu. ty mrizky fcc a hcp jsou zde
https://en.wikipedia.org/wiki/Kepler_conjecture#/media/File:Closepacking.svg