Problema dello zaino

Da Wikipedia, l'enciclopedia libera.

Questa voce di matematica è solo un abbozzo: contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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

Si ha uno zaino che può supportare un determinato peso. Si ha a propria disposizione una serie di N oggetti. Ognuno degli oggetti ha un peso e fornisce un'utilità ( ovvero un guadagno). Il problema si propone di trovare quali oggetti mettere all'interno dello zaino ottenendo la maggiore utilità, ma non eccedendo nel peso sostenibile dallo zaino stesso.

Questa è la formulazione matematica del problema (su supporrà di avere N oggetti tra i quali scegliere):

- ogni oggetto possiede un peso $w i$ e un'utilità $c i$

- si definiscono $x i$ ={0,1} N variabili binarie che indicano se un oggetto è inserito all'interno dello zaino o meno;

- si indica con W il peso massimo sopportabile dallo zaino.

Allora il problema è il seguente:

F.O. max z= $\sum_{i=1}^N c_i\cdot x_i$

S.T. $\sum_{i=1}^N w_i\cdot x_i\leq W$

$x_i=\left\{0,1\right\}$ $\forall i=1,...,N$

Il problema delo zaino è risolto spesso usando la programmazione dinamica, anche se è noto che tale metodo ha un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema NP-hard, e questo ha condotto a ricercare di usare il sottoinsieme somma come la 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) non dovrebbe impiegare tanto tempo per risolverlo.

Indice

1 Soluzione con la programmazione dinamica
2 Algoritmo Greedy
3 Rilassamento continuo
4 References

[modifica] Soluzione con la programmazione dinamica

Il problema dello zaino può essere risolto in modo esatto in tempo pseudo-polinomiale usando la programmazione dinamica. Viene descritta di seguito la soluzione per il problema dello zaino senza limiti.

Si indichino con $c_1,\dots,c_n$ i guadagni offerti dagli oggetti, e con $w_1,\dots,w_n$ i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo rispettando il vincolo che il peso complessivo sia inferiore al peso massimo consentito $W$ . Quindi per ogni gruppo $i$ di oggetti, tale che $i\leq W$ , si indichi con $A (i)$ il valore massimo che si può ottenere con un peso totale minore od uguale ad $i$ . Ovviamente, $A (W)$ è la soluzione del problema.

Si definiscono gli $A (i)$ ricorsivamente come di seguito:

$A (0) = 0$ ,
$A(i)=\max \lbrace v_j + A(i - c_j) | c_j \le i \rbrace$ .

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

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

Una soluzione simile al problema dello zaino 0-1 è a tempo pseudo-polinomiale. Come sopra, si indicano i costi con $c_1,\dots,c_n$ e i corrispondenti valori con $v_1,\dots,v_n$ . Si vuole massimizzare il valore totale soggetto al vincolo che il costo totale deve essere minor di $C$ . Si definisce una funzione ricorsiva $A (i, j)$ che sia il massimo valore che può essere ottenuto con un costo minore o uguale a $j$ utilizzando fino a $i$ oggetti.

Si può definire $A (i, j)$ in modo ricorsivo come di seguito:

$A (0, j) = 0$ ,
$A (i,0) = 0$ ,
$A (i, j) = A (i - 1, j)$ se $c i > j$ ,
$A (i, j) = max(A (i - 1, j), v i) + A (i - 1, j - c i)$ se $c_i\le j$ .

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

[modifica] Algoritmo Greedy

Martello e Toth (1990) proposero un'euristica greedy per risolvere il problema dello zaino. La loro versione ordina gli oggetti in ordine decrescente di peso per inserirli nello zaino fino all'esaurimento dello spazio disponibile. Se k è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo greedy garantisce che ne siano inseriti nello zaino almeno $\frac{k}{2}$ .

Sono possibili molte variazioni di questo algoritmo, la più efficiente prevede di ordinare gli elementi in base al loro costo unitario, vale a dire $\frac{c_i}{w_i}$ ed inserirli in ordine decrescente (euristica CUD).

È 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.

[modifica] Rilassamento continuo

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

[modifica] References

Michael R. Garey; David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. ISBN 0716710455 A6: MP9, pg.247.

Estratto da "http://it.wikipedia.org../../../p/r/o/Problema_dello_zaino.html"

Categorie: Stub matematica | Algoritmi | Ricerca operativa | Voci di qualità su fr.wiki