Sciencemag.cz
Doporučujeme
V obecném případě neexistuje žádný rychlý algoritmus. A co když nám jde i o to, kolik času balení zabere?
Úloha s balením v minulé kapitole byla pěkná a jednoduchá. Prostě jsme začali s největšími předměty a pokračovali k menším. Ve skutečnosti může ale řešení tohoto problému vyžadovat víc důmyslu. Kromě daného spektra předmětů k zabalení však můžeme mít i větší počet různě velkých beden. Jak potom zboží rozmístit, abychom potřebovali co nejméně přepravních obalů? Ještě obecněji – „balení“ nemusí znamenat jen naskládání věcí do určitého prostoru; podobnou úlohou je třeba řazení úkonů v čase. Dejme tomu, že jste vedoucím velkého kopírovacího centra, které nabízí kopie mnoha různých formátů. Otevřeno máte celý den. Jak to zařídit, abyste mohli plnit požadované zakázky, ale přitom potřebovali co nejméně kopírek?
Problémy tohoto typu jsou pro počítačové řešení velmi náročné, množství výpočetního času rychle roste spolu s tím, jak úloha zahrnuje víc a víc položek.
Zkusme třeba následující úlohu. Do krabic o objemu 10 jednotek máme co nejhospodárněji zabalit 25 různých balíčků, jejichž objemy jsou (ve stejných jednotkách – řekněme kusech knih) tyto:
6, 6, 5, 5, 5, 5, 4, 3, 2, 2, 3, 7, 6, 5, 4, 3, 2, 2, 4, 4, 5, 8, 2, 7, 1.
Nejprve uvažujme případ, že tyto balíčky přijíždějí na běžícím pásu, takže je nemůžete všechny předem roztřídit podle velikosti. Nejjednodušší postup je umisťovat balíčky do první krabice, dokud nepřijde takový, který se tam už nevejde. Pak začneme s další krabicí, a tak dále. V úloze tohoto typu před sebou máme opravdu kontinuální provoz. Vracet se a doplňovat prázdná místa v předchozích krabicích tudíž nemůžete, protože se nepřetržitě odvážejí i ony.
Podívejme se, jak dopadne plnění krabic v našem příkladu, když začnete zleva a přidáváte další balíčky popsaným způsobem. Šestikusový balíček přijde do prvního zásobníku. Ten šestikusový druhý se tam už nevejde, a tak načneme další krabici. Následující pětikusový se k němu opět nevejde, a tak s ním načneme třetí krabici. Dalším pětikusovým balíčkem ji naplníme a další dva pětikusové balíčky naplní další krabici – a tak dál. Budeme-li se řídit popsaným pravidlem, zaplníme jednotlivé krabice následujícím způsobem:
Použilo se 14 krabic a z toho jen tři jsou plné ([5, 5] a [8, 2]). Součet nevyužitého místa v krabicích je 4 + 4 +1 + 5 + 3 + 4 + 1 + 3 + 2 + 5 + 2 = 34 kusů knih.
Velký podíl nevyužitého prostoru je dán hlavně tím, že jsme se nemohli vracet a doplňovat předchozí poloprázdné krabice. Jak by se zvýšila efektivita, kdyby to šlo? Postup by začal stejně jako v předešlém případě: dvakrát po šesti kusech v samostatných krabicích a poté naplníme další dva pětikusovými balíčky. Ale pak následuje čtyřkusový balíček, který můžeme dát do první krabice ke stávajícímu šestikusovému. Pak přijde tříkusový balíček, který umístíte do druhé krabice, kde už je jeden šestikusový; pak dáme do páté oba následující dvoukusové s dalším tříkusovým a tak dál, až nakonec udáme poslední, jednokusový balíček do druhé krabice, která se tím zaplní. A takto vypadá konečné rozmístění:
V tomto případě jsme si vedli mnohem lépe, spotřebovali jsme jen 12 krabic a objem nevyužitého prostoru se snížil na 1 + 1 + 2 + 5 + 2 + 3 = 14 kusů knih. Šest krabic se podařilo naplnit úplně.
Teď si můžeme zkusit rozmyslet, zda by si nešlo počínat ještě lépe. Nevyužitý prostor má sklon vznikat hlavně tehdy, když je třeba pokračovat samými velkými balíčky. Místa, která zbývají v předešlých krabicích, jsou příliš malá, a pro každý nový balíček musíme proto načínat novou krabici. K lepšímu výsledku by očividně vedlo, kdybychom balíčky mohli předtím sestupně roztřídit podle velikosti. Takovou možnost ovšem vždy nemáme, představte si třeba zavazadla, která přicházejí na letištním zavazadlovém běžícím pásu; podívejme se ale, jak by nám pomohlo, kdybychom takto postupovat mohli. Roztřídíme-li balíčky sestupně podle velikosti, dostaneme následující seznam:
8, 7, 7, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1
Nejdříve použijme postup jako v první verzi úlohy, tedy bez vracení krabic. Prvních šest balíčků obsadí samostatné krabice, další dvě se naplní dvojicemi o pětikusových balíčcích a tak dál. Zde je výsledek:
[8], [7], [7], [6], [6], [6], [5, 5], [5, 5], [5, 5], [4, 4], [4, 4], [3, 3, 3], [2, 2, 2, 2, 2], [1]Smůla! Museli jsme použít novou krabici, aby bylo kam dát poslední jednokusový balíček. Postup s tříděním balíčků bez vracení krabic vede nakonec opět ke čtrnácti krabicím – jak tomu bylo bez třídění – a místa se vyplýtvalo také za 34 kusů. Kdybychom vyřadili ze zadání úlohy poslední jednokusový balíček, při prvním postupu bychom stále potřebovali 14 krabic a při jeho verzi s tříděním balíčků jen o jednu méně.
Promysleme si teď, k čemu povede postup s tříděním balíčků a vracením krabic. Prvních šest balíčků skončí každý ve své vlastní krabici a po nich šest pětikusových balíčků naplní další tři, ale pak se náležitě uplatní výhoda roztřídění. Tři čtyřkusová balení naplní krabice se šestikusovými balíčky, další načne novou krabici a zbylé balíčky pak pěkně doplní mezery v ostatních krabicích, přičemž nezaplněná zbude jen ta poslední:
Spotřebovali jsme 11 krabic a promarnil se jen čtyřkusový prostor v té poslední. To je ve srovnání se všemi předchozími postupy zdaleka nejlepší výsledek. Můžeme se ptát, zda je to současně i nejlepší možný výsledek. Šlo by nějakým postupem vecpat naše balíčky do méně než jedenácti krabic? Snadno nahlédneme, že nikoli: zabalených kusů máme celkem 1 x 8 + 2 x 7 + 3 x 6 + … + 5 x 2 + 1 x 1 = 106. Ježto každá krabice pojme nejvýš deset kusů, potřebujeme prostor 106/10 = 10,6 krabic, tedy celkem jedenácti krabic. Nikdy nemůže zbývat méně nevyužitého místa než právě na 4 kusy knih.
Pro tento příklad jsme našli nejlepší možné řešení postupem, při kterém balíme od největších předmětů a každý vkládáme na první místo, do kterého se vejde. Podíváte-li se na velmi snadnou úlohu, jíž jsme se zabývali v předešlé kapitole, když jsme dávali do sklenice tenisové míčky, kuličky a písek, zjistíte, že to byl vlastně týž postup: prostě jsme vždy vkládali dřív větší předměty a pak ty menší. Úlohy optimálního balení nebývají bohužel vždy takhle snadné. V obecném případě neexistuje žádný rychlý algoritmus, který by vedl k nalezení nejlepšího způsobu uložení jakékoliv směsi předmětů do nejmenšího možného počtu krabic. Roste-li jejich velikost nebo pestrost rozměrů ukládaných předmětů, stává se úloha výpočetně stále obtížnější a nakonec ji současné počítače prostě v rozumném čase vyřešit nedokážou. Uvážit je třeba i další faktor, který může problematizovat vhodnost našeho favorizovaného postupu s tříděním balíčků a vracením krabic: třídění předmětů, na němž je tento postup založen, totiž také nějakou dobu trvá. Pokud nám nejde jen o co nejefektivnější naplnění krabic, ale i o to, kolik času balení zabere, nemusí být nejefektivnější ani řešení s předběžným tříděním.
Tento text je úryvkem z knihy: John D. Barrow
Sto důležitých věcí, které nevíte (a ani nevíte, že je nevíte)
Matematika všedního dne
Dokořán 2013
O knize na stránkách vydavatele
