Bin packing-problemet
Når du flytter, fylder du den ene kasse efter den anden og spekulerer på, om en klogere rækkefølge ville have krævet færre. Det er bin packing-problemet, og det er berygtet for at være svært: selv computere finder kun det mindste antal kasser for store input ved hjælp af snedig søgning. Enkle regler kommer dog overraskende tæt på.
Problemet
Givet genstande med størrelser og kasser, der hver kan rumme det samme, skal hver genstand i en kasse, uden at nogen kasse løber over, og med så få kasser som muligt. Størrelserne kan stå for vægte, længder, varigheder eller filstørrelser. Det lyder som en hjernevrider til en regnvejrseftermiddag, men det er NP-svært: der kendes ingen metode, som hurtigt finder det mindste antal kasser for alle input.
Hurtige regler
Next Fit fylder én kasse, indtil den næste genstand ikke passer, starter så en ny kasse og ser aldrig tilbage. First Fit holder alle kasser åbne og lægger hver genstand i den første kasse med plads. Best Fit lægger hver genstand i den fyldeste kasse, der stadig har plads. Alle tre beslutter med det samme, hvilket er nyttigt, når genstandene kommer én ad gangen og skal placeres med det samme.
Sortér først
De store genstande er de svære, fordi de kræver meget fri plads. Sorterer man genstandene fra største til mindste og bruger derefter First Fit eller Best Fit, kommer de store i, mens kasserne stadig er tomme, og de små fylder hullerne. First Fit Decreasing bruger aldrig mere end 11/9 af det mindste antal kasser plus en konstant, mod 1,7 gange for First Fit på usorterede genstande.
Et eksempel
Tag kasser med størrelsen 10 og genstandene 2, 3, 2, 1, 3, 4, 5, 6, 7 og 7, som tilsammen giver 40. First Fit lægger 2, 3, 2 og 1 i den første kasse og 3 og 4 i den anden, og så skal 5, 6, 7 og 7 hver have deres egen kasse: 6 kasser. Sorteret med de største først laver First Fit Decreasing 7 + 3, 7 + 3, 6 + 4 og 5 + 2 + 2 + 1: 4 fulde kasser, præcis den nedre grænse på 40 / 10 = 4.
Find det mindste antal kasser
For et lille antal genstande kan det eksakte svar findes med dynamisk programmering over delmængder: for hver mængde af genstande det mindste antal kasser og den tommeste sidste kasse, der rummer den, bygget op fra mængderne med én genstand mindre. Det tager omkring 2ⁿ·n trin for n genstande. Større instanser løses med branch and bound eller heltalsprogrammering, og den nedre grænse fortæller, hvor langt en pakning højst kan være fra det bedste.
Hvor det bruges
Læsning af lastbiler og containere, tilskæring af rør eller papirruller fra standardlængder med så lidt spild som muligt (tilskæringsproblemet), fordeling af virtuelle maskiner på servere og pakning af filer på diske er alle bin packing-problemer. I to og tre dimensioner, med kasser i stedet for tal, er problemet endnu sværere.
Ofte stillede spørgsmål
Hvad er forskellen på online og offline bin packing?
Online skal hver genstand placeres, så snart den ankommer, uden at man kender resten; sådan arbejder Next Fit, First Fit og Best Fit. Offline kendes alle genstande på forhånd, så de kan sorteres først, som First Fit Decreasing gør.
Hvor tæt kommer First Fit Decreasing på det bedste?
Den bruger højst 11/9 af det mindste antal kasser plus 6/9 kasse, en grænse, som György Dósa i 2007 beviste er skarp. På typiske input er den som regel optimal eller én kasse fra.
Er bin packing det samme som rygsækproblemet?
De er beslægtede, men forskellige. Rygsækproblemet fylder én taske med de mest værdifulde genstande; bin packing lægger alle genstande i så få tasker som muligt. Eksakte bin packing-løsere arbejder ofte ved at løse rygsæklignende problemer igen og igen.
Hvorfor tillader appen kun 12 genstande?
Fordi det eksakte svar ser på hver mængde af genstande, og 12 genstande giver allerede 4.096 mængder. De hurtige regler kunne klare tusindvis af genstande, men tegningen og sammenligningen med det eksakte svar kunne ikke.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv bin packing