Hoe plaats je zo veel mogelijk dozen van verschillende grootte in het ruim van een stoomboot? Amsterdamse informatici hebben de Sint dit jaar een handje geholpen door een wiskundig inpakprobleem op te lossen.
De informatici, werkzaam bij de Universiteit van Amsterdam en de Vrije Universiteit, losten een inpakprobleem op uit de categorie perfect rectangle packing problems. Bij dit soort problemen moet je een verzameling rechthoeken van verschillende grootte zodanig naast en op elkaar plaatsen, dat ze samen ook een rechthoek vormen.
In dit geval gaat het om rechthoeken die bijna vierkant zijn. Bij de Asqas-problemen (Almost squares in almost squares) moet je een reeks bijna-vierkanten van opeenvolgende grootte samenvoegen tot wederom een bijna-vierkant (zie afbeelding rechts).
Dit is hoe we wiskundefobie te lijf kunnen gaan
Sarah Hart vertelt hoe we de angst voor getallen en formules weg kunnen nemen.
Duizend supercomputers
Eerder hadden de informatici al bewezen dat er slechts vijf verschillende reeksen bijna-vierkanten zijn waarvoor dit probleem oplosbaar is. Van vier van die reeksen (Asqas-1, -3, -8 en -20) is bovendien bekend hoe je de bijna-vierkanten moet configureren. De vijfde mogelijkheid (Asqas-34) was tot dusver echter onopgelost. Wel had de Italiaan Giovanni Resta naar eigen zeggen in 2007 al een oplossing gevonden, maar niet gepubliceerd.
Hoe Resta aan die oplossing kwam, is volgens onderzoeksleider Daan van den Berg (docententeam IvI / UvA) een raadsel. De Italiaan had zogezegd alleen zijn eigen computer gebruikt om een configuratie voor Asqas-34 te vinden. Van den Berg gebruikte met zijn team maar liefst duizend supercomputers en vond ‘slechts’ vijftien oplossingen. ‘Is Resta briljant, had hij mazzel, of is het probleem minder moeilijk dan wij denken? Ik weet het niet’, aldus Van den Berg op de website waarop hij het inpakprobleem uit de doeken doet.
Octiljoen
De duizend processoren hadden 55 dagen nodig om de vijftien oplossingen te vinden. Op voorhand was het probleem zelfs in die 55.000 computerdagen onoplosbaar. Je kunt 34 bijna-vierkanten namelijk op maar liefst een octiljoen (een 1 met 48 nullen) manieren samenvoegen.
Via een slimme gok brachten de informatici het inpakprobleem terug tot behapbare grootte. Ze gingen ervan uit dat de rand van het resulterende bijna-vierkant uit relatief grote rechthoeken bestaat, net zoals bij de meeste oplossingen van Asqas-20. Die zogeheten heuristische werkwijze leverde 4,4 miljoen kandidaat-randen van 12 rechthoeken op. De supercomputers zochten vervolgens bij elk van deze randen een configuratie waarbij de overgebleven 22 rechthoeken precies in het binnenwerk passen.
Dat leverde uiteindelijk vijftien Mondriaan-achtige oplossingen voor het Asqas-34-probleem. Het resultaat is meer dan een staaltje informatiekundig spierballenwerk. Oplossingen van inpakproblemen worden toegepast bij onder andere het optimaal benutten van opslagruimte, het efficiënt snijden van textiel om kleding te maken en het opstellen van een dienstregeling.
Altijd op de hoogte blijven van het laatste wetenschapsnieuws? Meld je nu aan voor de New Scientist nieuwsbrief.
Lees verder: