Problema dello zaino

Da Wikipedia, l'enciclopedia libera.
In questo caso, la soluzione è di mettere nello zaino tre scatole gialle e tre grigie

Il Problema dello zaino, detto anche Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente:

sia dato uno zaino che possa sopportare un determinato peso. Siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.

Introduzione[modifica | modifica wikitesto]

Il problema espresso in maniera più formale diventa:

  • ognuno degli N oggetti possiede un peso e un valore ;
  • si indica con W il peso massimo sopportabile dallo zaino;
  • la possibilità che un oggetto venga inserito o meno nello zaino è espressa dalle variabili intere .

La funzione obiettivo è:

I vincoli:

In base al tipo di variabili si ha poi la distinzione in:

  • problema dello zaino 0-1:
ogni oggetto può esserci o non esserci senza ripetizioni;
  • problema dello zaino con limiti
ogni oggetto non può apparire nello zaino più di un certo numero di volte;
  • problema dello zaino senza limiti
ogni oggetto può apparire nello zaino un numero arbitrario di volte.

Il problema dello zaino è risolto spesso usando la programmazione dinamica, anche se è noto che tale metodo abbia un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema NP-difficile, e questo ha indirizzato la ricerca verso il problema Subset-sum come base per il sistema di crittografia a chiave pubblica, come Merkle-Hellman. Questi tentativi usavano tipicamente alcuni gruppi oltre agli interi. Merkle-Hellman e altri algoritmi simili vennero presto abbandonati, in quanto i sottoproblemi di somma che producevano erano risolvibili da algoritmi lineari.

La versione decisionale di questo problema è NP-completa e infatti è uno dei 21 problemi NP-completi di Karp.

Il problema dello zaino, nella versione di ottimizzazione, è di fondamentale importanza in quanto, per molte istanze di comune applicazione, può essere risolto in maniera soddisfacente; per questo problema, infatti, sono disponibili buone euristiche e buoni rilassamenti. Un algoritmo di enumerazione implicita (ad esempio Branch and bound) normalmente non impiega molto tempo per risolverlo.

Soluzione problema dello zaino senza limiti[modifica | modifica wikitesto]

Viene descritta di seguito la soluzione per il problema dello zaino senza limiti.

Si indichino con i guadagni offerti dagli oggetti, e con i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo rispettando il vincolo che il peso complessivo sia inferiore o uguale al peso massimo consentito . Ora, si indichi con il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore od uguale ad . Ovviamente , e sarà la soluzione del nostro problema.

Si definiscono gli ricorsivamente come di seguito:

  • ,
  • .

Qui si considera zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da fino a si ottiene la soluzione. Dato che il calcolo di ogni implica l'esame di oggetti (che sono tutti stati calcolati in precedenza), e visto che ci sono valori di da calcolare, il tempo impiegato per trovare la soluzione è .

Ciò non contraddice il fatto che il problema dello zaino è NP-completo, dato che , al contrario di , non è polinomiale rispetto alla lunghezza dell'input del problema. Tale lunghezza è proporzionale al numero di bit in , e non a stesso.

Soluzione problema dello zaino 0-1[modifica | modifica wikitesto]

Come sopra, indichiamo con il peso dell'i-esimo oggetto e con il suo valore. Si vuole massimizzare il valore totale rispettando il vincolo che il peso totale sia minore o uguale al peso massimo consentito . Definiamo come il massimo valore che può essere trasportato con uno zaino di capacità avendo a disposizione solo i primi oggetti.

Si può definire ricorsivamente come segue:

  • ,
  • ,
  • se ,
  • se .

La soluzione può essere allora trovata calcolando . Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a e uno spazio anch'esso proporzionale a , anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a .

Algoritmo Greedy[modifica | modifica wikitesto]

Martello e Toth (1990) hanno utilizzato un'euristica greedy per risolvere il problema dello zaino. La loro versione ordina gli oggetti in base al loro costo unitario, vale a dire e li esamina in ordine decrescente. L'oggetto corrente viene inserito se e solo se il suo peso non supera la capacità residua corrente.

È bene far notare come questi algoritmi siano euristici: essi, quindi, non garantiscono l'ottimalità della soluzione ma sono in grado di fornire una "buona" soluzione in tempo ragionevole; spesso questo tipo di algoritmi viene utilizzato in approcci di enumerazione implicita come gli algoritmi Branch and bound.

Rilassamento continuo[modifica | modifica wikitesto]

Si dimostra che il rilassamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in [0, 1] delle variabili (in particolare una sola variabile avrà valore non binario). In questo modo euristica e rilassamento possono essere risolti simultaneamente in maniera efficiente.

Bibliografia[modifica | modifica wikitesto]