Impacchettare

Potrebbe esservi capitato qualche volta di dover caricare l’auto di valige, pacchi e pacchettini. E  se avete una moglie come la mia, non vi bastarebbe la monovolume più capiente sul mercato! Però, bisogna anche essere bravi ad impacchettare le cose per bene (cosa che mi toccherà fare tra un paio di giorni). E quasi mai riesce alla prima volta vero? Di solito si comincia a mettere la roba, e dopo un po’ ci si accorge che così non va. E allora bisogna tirare tutto fuori e ricominciare da capo con la santa pazienza.

In effetti, non è (sempre) colpa vostra: i problemi di impacchettamente sono tra i più “difficili” problemi matematico/informatici, fanno infatti parte della classe dei problemi NP-hard.

scatole...

Cominciamo con il più semplice, chiamato Bin-packing. In questo problema avete un certo numero di oggetti di dimensione varia, da mettere dentro delle scatole tutte uguali con una certa capacità. L’obiettivo è di utilizzare il minor numero di scatole. Per semplificare, consideriamo il problema unidimensionale: gli oggetti sono parallelepipedi tutti con la stessa base e con altezza varia, e gli scatoloni hanno la stessa base degli oggetti (che quindi si possono solo impilare uno sul’altro). Ad esempio, consideriamo il problema di avere scatole di altezza pari a 30 cm, e 5 oggetti di altezza pari a 5cm, 10 cm, 12 cm, 13 cm, 15 cm.

Se ci pensate un attimo, troverete che vi bastano 2 scatole: la prima contenente l’oggetto da 15 cm e quello da 13 cm; la seconda contiene tutti gli altri. Poiché gli oggetti non entrano evidentemente in una sola scatola, abbiamo trovato la soluzione minima.

Perché dico che questo problema è difficile? L’abbiamo risolto a mente in pochi secondi!

In informatica, i problemi “difficili” non sono quelli impossibili da risolvere, ma piuttosto quelli che scalano male con la dimensione dell’input. La dimensione dell’input al problema in questo caso è dato dal numero di oggetti da impacchettare. In un problema difficile, il tempo per risolverlo aumenta esponenzialmente con la dimensione dell’input.

Purtroppo il problema del bin-packing è un problema difficile perché per trovare la soluzione ottima dobbiamo per forza analizzare tutte le possibilità. Per essere più precisi: ad oggi non si conosce alcun algoritmo furbo per questo problema, cioè gli unici algoritmi ottimi conosciuti si limitano ad enumerare tutte le combinazioni possibili. E purtroppo, il numero di combinazioni è esponenziale nel numero degli oggetti.

Per capirlo considerate questo semplice ragionamento: supponiamo di avere 20 oggetti e al massimo 10 scatole. Numeriamo le scatole da 0 a 9. A questo punto, ogni possibile combinazione può essere identificata da un numero a 20 cifre: ogni posizione corrisponde a un oggetto, e il suo valore (da 0 a 9) indicherà in quale pacchetto infiliamo l’oggetto in questione. E’ chiaro che il numero di combinazioni corrisponderà a 1.000.000.000.000.000.000.000 (ovvero 10^{21}). Non male, no?

E stiamo parlando del problema unidimensionale. Nella pratica, spesso si ha a che fare con problemi in 3D (quello del bagagliaio dell’automobile ad esempio) o solo in 2D (il piazzamento di circuiti su un chip). Non è che siano più difficili in senso informatico, intendiamoci: anche in quel caso bisogna analizzare tutte le combinazioni di oggetti.

Panico? Ok, panico!

Cioè, aspettate un attimo, spesso non è che ci interessi proprio la soluzione ottimale, anche una abbastanza buona può andare bene, no? Dai, accontentiamoci!

Per questo si usano delle euristiche, ovvero degli algoritmi semplici che magari non ci danno proprio la soluzione ottima, ma per lo meno ci danno una soluzione accettabilmente buona. Per il bin-packing ci sono i seguenti:

  • First fit decreasing: in pratica, ordiniamo gli oggetti in ordine di altezza decrescente, e poi li mettiamo l’uno dopo l’altro nel primo scatolone in cui entrano. E se un oggetto non entra in nessuno di quelli già incignati, ne prendiamo uno nuovo.
  • Best fit decreasing: ordiniamo come prima gli oggetti in ordine di altezza decrescente, e poi mettiamo ogni oggetto nella scatola in cui entra meglio (ovvero quella in cui lascia meno spazio libero). Come prima, se necessario prendiamo uno scatolone nuovo.

Questi algoritmi sono nettamente più semplici di quelli di enumerazione. Innanzitutto, ordinare n elementi in ordine descente si fa in un tempo proporzionale a n log n. Per esempio con 20 oggetti, l’ordinamento si fa più o meno in 24-25 passi. Poi l’inserimento nello scatolone di ogni oggetto si fa in tempo pari a log n, e ci sono n oggetti, quindi anche qui n log n. In informatica teorica, si usa scrivere che la complessità di questi algoritmi è O(n \log{n}). Quindi, con una cinquantina di passi al più abbiamo risolto il problema contro il numero improbabile di cifre di prima.

E infine, quanto sono “buoni” questi algoritmi rispetto all’algoritmo ottimo? Se chiamiamo con OPT il numero minimo di scatole necessarie (calcolate dall’algoritmo ottimo), è stato dimostrato che First-Fit decreasing ne richiede al massimo 11/9 OPT + 6/9. Che non è poi tanto male!!

Perché mi interesso di bin-packing? Perché mi capita tra i piedi piuttosto spesso… infatti, sappiate che la mia specializzazione è nella schedulazione dei processi nei sistemi operativi, e in quest’ambito il bin-packing salta fuori piuttosto spesso.

E adesso a voi: se volete esercitarvi nella programmazione, scrivete una semplice funzioncina che implementi uno dei due algoritmi di cui sopra, per esempio in Python! perché no? o in qualunque altro linguaggio di vostro gradimento, inclusi l’italiano con tutti i suoi dialetti! Qui ad esempio ne trovate uno in Visual Basic (credo). E qui un’intera serie in Haskell dal mio amico Bjorn Brandeburg.

Buona programmazione!

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • juhan  Il 30 agosto 2010 alle 09:04

    Bjoern è davvero un tipo interessante! Ho adottato la sua shell per grep. E sto pensando al suo binomial heap, partendo dall’inno di UNC. Dovresti postare un video di te che lo canti 😉

  • knulp  Il 1 settembre 2010 alle 10:00

    🙂 sono stato a UNC solo 3 mesi, non avevo idea che avessero un inno! Ma a pensarci bene, ce l’hanno, altro che, figurati che sono fortissimi a basket, hanno anche avuto Michael Jordan come freshman!

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: