21 dec. 2020
2 minuten
Wat is de optimale manier om uit een rechthoekig vel koekjesdeeg zoveel mogelijk kerstboomvormige koekjes te snijden? Dat is een voorbeeld van een packing problem (pakkingsprobleem), een notoir moeilijke opgave in de theoretische informatica. Informaticus Tillmann Miltzow (UU), Mikkel Abrahamsen (Københavns Universitet) en Nadja Seiferth (Freie Universität Berlin) leggen uit:
Een pakkingsprobleem is eigenlijk een puzzel waarbij je een set stukken probeert in een bepaalde vorm te plaatsen zonder dat ze elkaar overlappen, of om te bepalen dat er niet genoeg ruimte beschikbaar is om dit te doen. Zulke problemen komen overal in het dagelijks leven voor. Je lost bijvoorbeeld een pakkingsprobleem op als je bepaalt waar in de kamer je je meubels neerzet, als je naaipatronen zo efficiënt mogelijk ordent op een stuk stof, of als je zoveel mogelijk kerstkoekjes uit een lap deeg probeert te snijden.
In veel takken van industrie is het cruciaal om ingewikkelde pakkingsproblemen efficiënt op te lossen. Naast kledingproductie geldt dat bijvoorbeeld ook voor het snijden van leer, glas, hout en plaatwerk, selectief lasersinteren, logistiek (om zoveel mogelijk goederen te verpakken in laadcontainers) en 3D-printen (om zoveel mogelijk te printen onderdelen te ordenen in het printvolume); zie figuur 1.
Figuur 1. Echte voorbeelden van ‘nesting’ (het ordenen van vormen) op een dierenhuid (boven) en een stuk stof (onder), geproduceerd door de software van MIRISYS.
Toepassingen
Verschillende toepassingen leiden tot verschillende pakkingsproblemen. Bij het rangschikken van naaipatronen op een rol stof is het belangrijk dat elk patroondeel op de juiste manier geörienteerd is ten opzichte van het weefpatroon of op de stof gedrukte patronen. Dat betekent dat de patroondelen niet mogen worden gedraaid. Bij andere toepassingen, zoals het snijden van leer, glas of plaatwerk, zijn er meestal geen beperkingen, zodat de stukken kunnen worden gedraaid om afval te minimaliseren. Weer andere versies van het probleem ontstaan wanneer de vorm van de stof of de stukken beperkt is.
Moeilijkheid
Van de meeste versies van pakkingsproblemen was het al bekend dat deze NP-moeilijk zijn. In de publicatie laten de onderzoekees zien dat veel problemen waarschijnlijk nog moeilijker zijn, door te bewijzen dat ze ∃R-compleet zijn. Dat geldt in ieder geval voor het pakken van polygonen in een vierkant met toegestane rotaties. Dat wil zeggen dat deze problemen in wezen net zo moeilijk zijn als de vraag of een systeem van polynomiale vergelijkingen en ongelijkheden een echte oplossing heeft – een probleem dat naar verwachting van de meeste onderzoekers moeilijker zal zijn dan NP-complete problemen, hoewel dit nog steeds een openstaande vraag is. Houd dit in gedachten de volgende keer dat u kerstkoekjes bakt!
Anderen lazen ook
