Torna alla pagina di Algoritmi e strutture dati

 :: Bin Packing ::

Problema

Il problema del Bin Packing è il seguente:

Il problema è più o meno simile a quello dello zaino, con la differenza che se in quest'ultimo dovevo portar via il maggior numero di oggetti in uno spazio limitato, nel Bin Packing devo traslocare tutto utilizzando il minor numero di contenitori possibili.

Questo problema può essere risolto progettando un algoritmo Greedy.

Soluzione

Primo passo

Come prima cosa devo definire la struttura delle variabili P che definiscono il problema e la struttura della soluzione S.

P è una struct composta da:

• n : numero degli oggetti (intero)
• p_i : peso dell'oggetto i, con i che va da 1 a n (vettore di interi)
• C : capacità del singolo contenitore (intero)

Da notare che se n non fosse noto a priori, non potrei definire p_i come vettore perché non saprei con quante posizioni dichiararlo. In questo caso dovrei utilizzare una lista.

S è una struct composta da:

• k : numero dei contenitori utilizzati (intero)
• bin[i] = h : un vettore in cui ad ogni oggetto i è associato il pacchetto h in cui esso è contenuto (con h compreso tra i e k) (vettore di interi)

Secondo passo

Per risolvere un problema di tipo Greedy bisogna utilizzare due criteri:

1. il criterio di ottimo (o ottimalità), che indica come deve avvenire la selezione degli oggetti in modo che si ottimizzi la soluzione;
2. costruzione della soluzione, che tiene conto solo di quei risultati che rispettano i vincoli del problema, che siano cioè ammissibili.

Criterio di ottimo
Considero gli oggetti per peso decrescente.
Il principio è che scegliendo per ultimi gli oggetti più piccoli, questi si collocheranno più facilmente negli spazi ancora liberi.

Costruzione soluzione
In generale, mentre costruisco la soluzione all'i-simo oggetto dovrò sapere:

S:

• k^' : numero dei contenitori utilizzati fino a questo momento
• B_h = C - ∑p_i : la capacità residua del contenitore, calcolata come differenza tra la capacità totale e la sommatoria dei pesi degli oggetti ivi già collocati

Quindi, indipendentemente dal criterio di ottimo utilizzato, dovrò selezionare il contenitore h^' con B_h^' ≥ p_i (ovvero un contenitore con spazio sufficiente per metterci dentro l'oggetto). Posso avere ora tre casi:

1. h^' = NULL : se non c'è posto nei contenitori considerati, ne apro uno nuovo
2. esiste un unico h^' : allora metto l'oggetto in quel contenitore (Bin[i] = h^')
3. ho tanti h^' tra cui scegliere : allora
   1. scelgo di prediligere l'aspetto computazionale (quindi l'efficienza dell'algoritmo), disinteressandomi del risultato migliore ma seguendo la logica del "fai più in fretta possibile". Soluzione: algoritmo NFD (vedi dopo)
   2. scelgo di prediligere l'efficacia dell'algoritmo, in modo che rispetti la funzione obiettivo, applicando ancora il criterio di ottimo. Soluzione: algoritmo BFD
   3. scelgo una via di mezzo tra le due soluzioni precedenti. Soluzione: algoritmo FFD.

Terzo passo

Ecco ora le implementazioni in pseudocodice degli algoritmi elencati prima.

NFD

NFD sta per Next Fit Decreasing, e prevede la scelta del contenitore k^' corrente per metterci dentro l'oggetto. Se ci sta, bon. Se non ci sta ne apre un altro e ce lo mette dentro.

soluzione NFD (problema P)
{
   int i, b; // i sono gli oggetti, b i contenitori
   soluzione S;

   inizializzaSol(S); // bin[i]=0, cap[b]=0, K=0
   { ordina gli oggetti per p'_i_' tali che p'_1_' ≥ ... ≥ p'_n_' }
   S.k = 1; // apro il primo contenitore
   S.bin[1] = 1; 
   S.cap[1] = p1; // metto il primo oggetto nel primo contenitore

   i = 2; // considero il secondo oggetto
   b = 1;

   while( i <= P.n ) {
      if(S.cap[b] < P.p'_i_') b++; //se i non ci sta nel contenitore, ne apro uno nuovo
      S.bin[i] = b; 
      S.cap[b] -= P.p'_i_';
      i++;
   }

   S.k = b;
   return(S);
}

Per la complessità dell'algoritmo, consideriamo i vari apporti:

• inizializzazione: O(n) perché devo ripetere n volte l'assegnamento del valore
• ordinamento: se utilizzo un matchsort, allora avrò O(n logn)
• ciclo while: ripeto n-1 volte operazioni elementari, quindi O(n)

La complessità dell'algoritmo è dunque di O(n logn).

FFD

FFD sta per First Fit Decreasing, e prevede la scelta del primo contenitore k^' che trova con abbastanza spazio libero per metter dentro l'oggetto. Il codice si distingue sostanzialmente dal precedente solo all'interno del ciclo while.

soluzione FFD (problema P)
{
   int i, b; // i sono gli oggetti, b i contenitori
   soluzione S;

   inizializzaSol(S); // bin[i]=0, cap[b]=0, K=0
   { ordina gli oggetti per p'_i_' tali che p'_1_' ≥ ... ≥ p'_n_' }
   S.k = 1; // apro il primo contenitore
   S.bin[1] = 1; 
   S.cap[1] = p1; // metto il primo oggetto nel primo contenitore

   i = 2; // considero il secondo oggetto

   while( i <= P.n ) {
      b = 1;
      while(b < S.k && S.cap[b] < P.p'_i_') b++; // *nota
      S.bin[i] = b; 
      S.cap[b] -= P.p'_i_';
      if(S.k < b) S.k++; //aggiorna la lista dei contenitori usati
      i++;
   }
   return(S);
}

nota: avviene una scansione di tutti i contenitori aperti, finché non se ne trova uno con abbastanza spazio libero da farci stare dentro i. Se non lo trova, l'ultimo b++ eseguito corrisponde all'apertura di un nuovo contenitore. La lista dei contenitori usati verrà aggiornata poco più sotto.

Per la complessità dell'algoritmo, consideriamo i vari apporti:

• inizializzazione: O(n) perché devo ripetere n volte l'assegnamento del valore
• ordinamento: se utilizzo un matchsort, allora avrò O(n logn)
• ciclo while: nel caso pessimo dovrò creare un nuovo contenitore per ogni oggetto, quindi ripeterò n volte n operazioni elementari. La complessità sarà di O(n²).

La complessità dell'algoritmo è dunque di O(n²).

BFD

BFD sta per Best Fit Decreasing, e prevede la scelta tra i contenitori aperti di quello che minimizza la capacità residua dopo l'inserimento dell'oggetto i. Ad esempio se ho un oggetto di peso 5 e ho un contenitore che lascerebbe libero 3 e un altro 8, sceglierò il primo).

soluzione BFD (problema P)
{
   int i, b; // i sono gli oggetti, b i contenitori
   soluzione S;

   inizializzaSol(S); // bin[i]=0, cap[b]=0, K=0
   { ordina gli oggetti per p'_i_' tali che p'_1_' ≥ ... ≥ p'_n_' }
   S.k = 1; // apro il primo contenitore
   S.bin[1] = 1; 
   S.cap[1] = p1; // metto il primo oggetto nel primo contenitore

   i = 2; // considero il secondo oggetto

   while( i <= P.n ) {
      b = 1;
      m = 0;
      M = C;
      while(b <= S.k) {
         if(S.cap[b] - P.p'_i_' < M) {
            m = b;
            M = S.cap[b] - p'_i_';
         }
         b++;
      }
      if(m == 0) { // se l'oggetto non ci sta in nessun contenitore..
         S.k++;    // ne apro uno nuovo
         m = S.k;
      }
      S.bin[i] = m;
      S.cap[n] -= P.p'_i_';
      i++;
   }
   return(S);
}

Per la complessità dell'algoritmo, consideriamo i vari apporti:

• inizializzazione: O(n) perché devo ripetere n volte l'assegnamento del valore
• ordinamento: se utilizzo un matchsort, allora avrò O(n logn)
• ciclo while: nel caso pessimo dovrò creare un nuovo contenitore per ogni oggetto, quindi ripeterò n volte n operazioni elementari. La complessità sarà di O(n²).

La complessità dell'algoritmo è dunque di O(n²).

Torna alla pagina di Algoritmi e strutture dati