Het bin-packingprobleem
Bij een verhuizing vul je de ene doos na de andere en vraag je je af of een slimmere volgorde minder dozen had gekost. Dat is het bin-packingprobleem, en het staat bekend als lastig: zelfs computers vinden het kleinste aantal bakken voor grote invoer alleen met slim zoeken. Eenvoudige regels komen er wel verrassend dicht bij.
Het probleem
Gegeven zijn voorwerpen met een grootte en bakken die allemaal evenveel kunnen bevatten. Stop elk voorwerp in een bak zonder dat een bak overloopt, en gebruik zo weinig mogelijk bakken. De groottes kunnen staan voor gewichten, lengtes, tijdsduren of bestandsgroottes. Het klinkt als een puzzel voor een regenachtige middag, maar het is NP-lastig: er is geen methode bekend die voor elke invoer snel het kleinste aantal bakken vindt.
Snelle regels
Next Fit vult een bak tot het volgende voorwerp niet meer past, begint dan een nieuwe bak en kijkt nooit meer terug. First Fit houdt alle bakken open en stopt elk voorwerp in de eerste bak met genoeg ruimte. Best Fit stopt elk voorwerp in de volste bak die nog ruimte heeft. Alle drie beslissen meteen; dat is handig als de voorwerpen een voor een binnenkomen en direct geplaatst moeten worden.
Eerst sorteren
Grote voorwerpen zijn de lastige, omdat ze veel vrije ruimte nodig hebben. Als je de voorwerpen van groot naar klein sorteert en dan First Fit of Best Fit gebruikt, gaan de grote erin terwijl de bakken nog leeg zijn, en vullen de kleine de gaten. First Fit Decreasing gebruikt nooit meer dan 11/9 van het kleinste aantal bakken, plus een constante, tegenover 1,7 keer voor First Fit op ongesorteerde voorwerpen.
Een voorbeeld
Neem bakken van grootte 10 en de voorwerpen 2, 3, 2, 1, 3, 4, 5, 6, 7 en 7, samen 40. First Fit stopt 2, 3, 2 en 1 in de eerste bak en 3 en 4 in de tweede, en daarna hebben 5, 6, 7 en 7 elk een eigen bak nodig: 6 bakken. Gesorteerd van groot naar klein maakt First Fit Decreasing 7 + 3, 7 + 3, 6 + 4 en 5 + 2 + 2 + 1: 4 volle bakken, precies de ondergrens van 40 / 10 = 4.
Het kleinste aantal bakken vinden
Bij weinig voorwerpen is het exacte antwoord te vinden met dynamisch programmeren over deelverzamelingen: voor elke verzameling voorwerpen het kleinste aantal bakken en de leegste laatste bak waar ze in passen, opgebouwd uit de verzamelingen met één voorwerp minder. Dat kost ongeveer 2ⁿ·n stappen voor n voorwerpen. Grotere instanties worden opgelost met branch-and-bound of geheeltallig programmeren, en de ondergrens vertelt hoe ver een indeling hoogstens van het beste af zit.
Waar het gebruikt wordt
Vrachtwagens en containers laden, buizen of papierrollen uit standaardlengtes zagen met zo weinig mogelijk afval (het snijprobleem), virtuele machines over servers verdelen en bestanden op schijven zetten: het zijn allemaal bin-packingproblemen. In twee en drie dimensies, met dozen in plaats van getallen, is het probleem nog moeilijker.
Veelgestelde vragen
Wat is het verschil tussen online en offline bin packing?
Online moet elk voorwerp geplaatst worden zodra het binnenkomt, zonder de rest te kennen; zo werken Next Fit, First Fit en Best Fit. Offline zijn alle voorwerpen vooraf bekend, zodat je ze eerst kunt sorteren, zoals First Fit Decreasing doet.
Hoe dicht komt First Fit Decreasing bij het beste?
Het gebruikt hoogstens 11/9 van het kleinste aantal bakken plus 6/9 bak, een grens waarvan György Dósa in 2007 bewees dat die precies klopt. Bij gewone invoer is het meestal optimaal of zit het er één bak naast.
Is bin packing hetzelfde als het knapzakprobleem?
Ze zijn verwant, maar verschillend. Bij de knapzak vul je één tas met de waardevolste voorwerpen; bij bin packing gaat elk voorwerp in zo weinig mogelijk tassen. Exacte bin-packingoplossers werken vaak door steeds opnieuw knapzakachtige problemen op te lossen.
Waarom staat de app maar 12 voorwerpen toe?
Omdat het exacte antwoord naar elke verzameling voorwerpen kijkt, en 12 voorwerpen geven al 4.096 verzamelingen. De snelle regels kunnen duizenden voorwerpen aan, maar de tekening en de vergelijking met het exacte antwoord niet.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer bin packing