Il problema del bin packing
Durante un trasloco riempi uno scatolone dopo l'altro e ti chiedi se un ordine più furbo ne avrebbe richiesti meno. Questo è il problema del bin packing, ed è notoriamente difficile: anche i computer trovano il minor numero di contenitori per input grandi solo con una ricerca ingegnosa. Eppure le regole semplici ci vanno sorprendentemente vicino.
Il problema
Dati degli oggetti con le loro dimensioni e dei contenitori che hanno tutti la stessa capacità, metti ogni oggetto in un contenitore in modo che nessun contenitore trabocchi, usando il minor numero possibile di contenitori. Le dimensioni possono rappresentare pesi, lunghezze, durate o dimensioni di file. Sembra un passatempo per un pomeriggio di pioggia, ma è NP-difficile: non si conosce nessun metodo che trovi velocemente il minor numero di contenitori per ogni input.
Regole veloci
Next Fit riempie un contenitore finché l'oggetto successivo non ci entra più, poi inizia un nuovo contenitore e non torna mai indietro. First Fit tiene aperti tutti i contenitori e mette ogni oggetto nel primo contenitore con spazio sufficiente. Best Fit mette ogni oggetto nel contenitore più pieno che ha ancora spazio. Tutte e tre decidono subito, il che è utile quando gli oggetti arrivano uno alla volta e vanno sistemati immediatamente.
Prima ordinare
Gli oggetti grandi sono quelli difficili, perché hanno bisogno di molto spazio libero. Ordinare gli oggetti dal più grande al più piccolo e poi usare First Fit o Best Fit fa entrare gli oggetti grandi finché i contenitori sono ancora vuoti, e quelli piccoli riempiono i buchi. First Fit Decreasing non usa mai più di 11/9 del numero minimo di contenitori, più una costante, contro 1,7 volte per First Fit su oggetti non ordinati.
Un esempio
Prendi contenitori di dimensione 10 e gli oggetti 2, 3, 2, 1, 3, 4, 5, 6, 7 e 7, che sommano 40. First Fit mette 2, 3, 2 e 1 nel primo contenitore e 3 e 4 nel secondo, poi 5, 6, 7 e 7 hanno bisogno ciascuno di un contenitore tutto suo: 6 contenitori. Con gli oggetti ordinati dal più grande, First Fit Decreasing fa 7 + 3, 7 + 3, 6 + 4 e 5 + 2 + 2 + 1: 4 contenitori pieni, che coincidono con il limite inferiore di 40 / 10 = 4.
Trovare il minor numero di contenitori
Con pochi oggetti, la risposta esatta si può trovare con la programmazione dinamica sui sottoinsiemi: per ogni insieme di oggetti, il minor numero di contenitori e l'ultimo contenitore più vuoto che lo contengono, costruiti a partire dagli insiemi con un oggetto in meno. Servono circa 2ⁿ·n passi per n oggetti. Le istanze più grandi si risolvono con il branch and bound o la programmazione lineare intera, e il limite inferiore dice quanto una sistemazione può essere lontana dalla migliore.
Dove si usa
Caricare camion e container, tagliare tubi o rotoli di carta da lunghezze standard con il minimo scarto (il problema del taglio), distribuire macchine virtuali sui server e sistemare file sui dischi sono tutti problemi di bin packing. In due e tre dimensioni, con scatole al posto dei numeri, il problema è ancora più difficile.
Domande frequenti
Qual è la differenza tra bin packing online e offline?
Online, ogni oggetto va sistemato appena arriva, senza conoscere gli altri; Next Fit, First Fit e Best Fit funzionano così. Offline, tutti gli oggetti sono noti in anticipo, quindi si possono prima ordinare, come fa First Fit Decreasing.
Quanto si avvicina First Fit Decreasing alla soluzione migliore?
Usa al massimo 11/9 del numero minimo di contenitori più 6/9 di contenitore, un limite che György Dósa ha dimostrato essere esatto nel 2007. Sugli input tipici di solito è ottimale o sbaglia di un solo contenitore.
Il bin packing è lo stesso problema dello zaino?
Sono collegati ma diversi. Il problema dello zaino riempie un solo zaino con gli oggetti di maggior valore; il bin packing mette ogni oggetto nel minor numero possibile di zaini. I risolutori esatti del bin packing spesso funzionano risolvendo più e più volte problemi simili a quello dello zaino.
Perché l'app accetta solo 12 oggetti?
Perché la risposta esatta esamina ogni insieme di oggetti, e 12 oggetti formano già 4.096 insiemi. Le regole veloci gestirebbero migliaia di oggetti, ma il disegno e il confronto con la risposta esatta no.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il bin packing