Vždy nepolapitelná hádanka, které se vzdali i odborníci na matematiku

V určitém okamžiku života by většina lidí stála nad vyvaleným listem těsta na sušenky a přemýšlela, jak nejlépe vyříznout sušenky s co nejmenším množstvím odpadu. Nyní se dokonce matematici vzdali snahy najít počítačový algoritmus, který by odpověděl na tento typ geometrického problému.

Jak můžeme maximalizovat těsto, když vykrajujeme vánoční cukroví? Jak zabalíme kufr nebo naplníme kuchyňskou skříňku, když využijeme maximum prostoru? Jeden by si mohl pomyslet: „Musí to být nejlepší způsob, jak to udělat.“ Přemýšlet nad takovými otázkami se nyní jeví jako ztráta času. Věda je nyní tady, aby právě teď podpořila nemožné, aby zjistila, co funguje nejlépe pro více než čtyři nebo pět chutných perníčků nebo vánočních cukrovinek.

Odborný asistent Mikkel Abrahamsen z Ústavu výpočetní techniky a dva výzkumní kolegové zkoumali, jak obtížné je najít optimální způsob, jak zabalit objekty do dvou dimenzí bez překrývání – hádanka, se kterou se počítačoví vědci zabývají po celá desetiletí.

“I když dokážeme vyřešit velmi složité problémy pomocí algoritmů, je to pro dnešní počítače příliš ústa.” V současné době není možné optimálně zabalit více než 5–10 objektů. A náš výsledek naznačuje, že je nepravděpodobné, že by se toto číslo prozatím hodně zvýšilo, “vysvětluje Mikkel Abrahamsen.

Dávat věci do pořádku není jen občasný problém v domácnosti, ale v různých průmyslových odvětvích, včetně výroby oděvů a zpracování kovů. V každém případě je důležité vyřezávat materiály s co nejmenším množstvím odpadu. Při přepravě to platí pro balení kontejnerů.

Balení čtverců

Vlevo: Optimální balení pěti čtverců. Vpravo: Aktuálně nejznámější balení jedenácti čtverců jednotek do jednoho většího čtverce. Fotografický kredit: Mikkel Abrahamsen

Pouze čtyři perníčky

Známe velikost nejmenšího čtvercového kontejneru, do kterého můžeme zabalit až 10 čtvercových palet 1 × 1 metr. Pouhé přidání další palety však znemožňuje výpočet optimální velikosti kontejneru. Abrahamsen vysvětluje:

“S přidáváním více palet se doba výpočtu exponenciálně zvyšuje.” Ani ty nejlepší počítače nemohou držet krok. Teoreticky je to možné. Vzhledem k rychlosti, s jakou výpočetní výkon roste, bude pravděpodobně trvat miliony let, než budeme moci optimalizovat zpracování některých dalších objektů. “

Při práci se složitějšími tvary, jako je perník ve tvaru vánočního stromku, říká Mikkel Abrahamsen, že dnes lze najít optimální řešení pouze pro čtyři objekty.

Nekonečné množství možností

Co to dělá tak obtížným Abrahamsen vysvětluje, že problém řešení rovnic pátého nebo vyššího stupně as mnoha neznámými je podobný. Zde je známo, že takové řešení nelze vždy zapsat běžnými aritmetickými operacemi.

“Naše studie dokazuje, že problém má to, co v matematice nazýváme spojité – což v kostce znamená znát všechny souřadnice, kam lze soubory cookie umístit, a všechny úhly, pod kterými je lze umístit lze otáčet, “vysvětluje Abrahamsen.

Vzhledem k tomu, že možné kombinace jsou nekonečné, neexistuje způsob, jak vytvořit seznam všech míst, která by bylo potřeba vyzkoušet a najít optimální řešení balení. Místo toho musí být algoritmy, které optimálně řeší problémy s balením, analytičtější, což je časově náročné. To je na rozdíl od mnoha dalších známých algoritmických problémů, kde můžete vyzkoušet omezený počet kombinací, než najdete optimální. Problémy s balením jsou proto mnohem obtížnější.

V praxi tedy neexistují lepší řešení problémů s balením než ta, která najdeme my lidé.

„V průmyslu i mimo kuchyňskou linku musíme být i nadále spokojeni s našimi neoptimálními řešeními a být si jisti, že my lidé jsme pro tento typ úkolu prozatím stále lepší než počítače,“ uzavírá Mikkel Abrahamsen.

  • V informatice a matematice jsou problémy s balením třídou optimalizačních problémů, které se snaží zabalit sadu objektů co nejpřesněji do dvou nebo tří dimenzí. Matematici se zabývají problémy s balením již stovky let.
  • S novým výsledkem se problém dvojrozměrného balení vyvinul do vyšší třídy výpočetní složitosti, kterou označuje ∃ℝ. Dříve se věřilo, že otázkou, spolu se slavným „problémem obchodního cestujícího“, byla třída NP, která se zabývá výpočtem nejkratší cesty k návštěvě všech měst na daném seznamu.
  • Výzkum provedl Mikkel Abrahamsen z centra BARC v Kodani na katedře výpočetní techniky. Tillmann Miltzow z University of Utrecht v Nizozemsku a Nadja Seiferth z Free University of Berlin v Německu. Výzkum byl mimo jiné financován nadací VILLUM.
  • Studie byla představena na renomované konferenci FOCS 2020 (IEEE symposium on the fundamentals of computer science) ve dnech 16. až 19. listopadu.

Odkaz: „Rámec pro ∃R úplnost problémů s dvojrozměrným obalem“ od Mikkel Abrahamsen, Tillmann Miltzow a Nadja Seiferth, 16. dubna 2020.
arXiv: 2004.07558

Related articles

Comments

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Share article

Latest articles

Kampaň NASA SnowEx kopání hluboko v roce 2021

Měření sněhu se může zdát jednoduché, ale každé prostředí představuje pro přístroje jedinečné výzvy. Například sněžení v lesích se zachytává na větvích nebo...

Agresivní tržní model vývoje energie z jaderné syntézy

Koncept ARC Fusion Pilot Plant byl vyvinut na MIT, aby demonstroval potenciál vysokoteplotních supravodivých magnetů pro nastavení hodnoty rychlosti fúzní energie և. Půjčka:...

LSD může nabídnout udržitelnou léčbu úzkosti a jiných duševních poruch

McGill studoval krok v porozumění mechanismu vlivu psychedelik na mozek a potenciálu pro terapeutické použití. Vědci z McGill University poprvé objevili jeden z možných mechanismů,...

Nenechte si ujít příští úplněk – sníh, bouře a hladový měsíc

Uznání: NASA / Bill Dunford Příští úplněk je měsíc se sněhem, bouří a hladem; měsíc během svátků svátku Puim; festival čínských luceren; Magha Purnima a...

Chytré tetování OLED. Inženýři vytvářejí tetování vyzařující světlo

OLED tetovací zařízení. Půjčka Barsotti - italský technologický institut Vědci z UCL և IIT -Istituto Italiano di Tecnologia (Italský technologický institut) vytvořili dočasné...

Newsletter

Subscribe to stay updated.