Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 16.Il Problema dello Zaino 0/1: un algoritmo di Programmazione Dinamica


Programmazione Dinamica, 1

La Programmazione Dinamica (PD) è un’altra tecnica esatta tipica per la risoluzione dei problemi di ottimizzazione caratterizzati da variabili di decisione intere.

Essa si basa sul principio per il quale sia possibile definire la soluzione ottima del problema di programmazione lineare intero originario (Pli) in termini di combinazione di soluzioni ottime dei sottoproblemi di (Pli), identici a (Pli), ma di dimensione più piccola.

Infatti, un algoritmo di PD tipicamente divide (senza partizionare) un problema in sottoproblemi (non indipendenti fra loro), risolve i sottoproblemi ricorsivamente e poi combina le loro soluzioni ottime per ottenere una soluzione ottima del problema originario.

Programmazione Dinamica, 2

Si ricorda che due sottoproblemi \mbox{(Pli)}_h e \mbox{(Pli)}_k non sono indipendenti quando possono essere a loro volta suddivisi nei seguenti sottoproblemi

\[ \mbox{(Pli)}_h=\{\mbox{(Pli)}_{h1},\mbox{(Pli)}_{h2},\ldots,\mbox{(Pli)}_{hi}\} \]

\[ \mbox{(Pli)}_k=\{\mbox{(Pli)}_{k1},\mbox{(Pli)}_{k2},\ldots,\mbox{(Pli)}_{kj}\} \]

e risulta

\[  \{\mbox{(Pli)}_{h1},\mbox{(Pli)}_{h2},\ldots,\mbox{(Pli)}_{hi}\}\cap\{\mbox{(Pli)}_{k1},\mbox{(Pli)}_{k2},\ldots,\mbox{(Pli)}_{kj}\}\not=\emptyset, \]

cioè \mbox{(Pli)}_h e \mbox{(Pli)}_k condividono almeno un sottoproblema.

Programmazione Dinamica, 3

Nella progettazione e messa a punto di un algoritmo di PD per risolvere un problema di ottimizzazione discreta (Pli) è necessario seguire i seguenti tre passi fondamentali.

Passo 1. Verificare che (Pli) esibisca una sottostruttura ottima.

Passo 2. Definire il valore z(x^*) che la funzione obiettivo assume in corrispondenza di una soluzione ottima x^* di (Pli) ricorsivamente come combinazione di soluzioni ottime dei suoi sottoproblemi.

In questa fase, è fondamentale esplicitare il valore che la funzione obiettivo assume in corrispondenza di una soluzione ottima dei sottoproblemi cosiddetti elementari, in quanto non ulteriormente divisibili in sottoproblemi.

L’equazione ricorsiva risultante da questa fase è nota come equazione di ricorrenza, mentre esplicitare il valore che la funzione obiettivo assume in corrispondenza di una soluzione ottima dei sottoproblemi elementari corrisponde a stabilire le condizioni iniziali.

Passo 3. Progettare un algoritmo basato sulla ricorrenza individuata al Passo 2.

Il Problema dello Zaino 0/1: un algoritmo di PD, 1

In quanto segue verrà descritto un algoritmo di PD per il Problema dello Zaino 0/1.
Verificare che il Problema dello Zaino 0/1 gode della proprietà di sottostruttura ottima è molto semplice ed è lasciato per esercizio, per cui si procederà direttamente alla descrizione dei Passo 2.

Siano m,\ \hat W\in {\mathbb Z} tali che
\[ 1\leq m\leq n,\qquad 0\leq{\hat W}\leq W \]
e sia \mbox{(Z$_{0/1}$)$_{m\hat W}$} il sottoproblema del Problema dello Zaino 0/1 caratterizzato da m oggetti e capacità dello zaino pari a \hat W .

Il valore che la funzione obiettivo assume in corrispondenza di una soluzione ottima per \mbox{(Z$_{0/1}$)$_{m\hat W}$} è dato da

\[ f_{m,\hat W}=\max\left\{\displaystyle{\sum_{j=1}^m p_jx_j\ \vert\ \sum_{j=1}^m w_jx_j\leq \hat W,\ x_j\in\{0,1\},\ j=1,2,\ldots,m}\right\}. \]

Il Problema dello Zaino 0/1: un algoritmo di PD, 2

Dunque, f_{m,\hat W} esprime il massimo profitto ricavabile caricando alcuni degli oggetti 1,2,\ldots,m in uno zaino di capacità \hat W .

E’ banale osservare che
\[ f_{1,\hat W}=\left\{ \begin{array}{lll} 0,   & \mbox{{\rm se }} \hat W=0,1,\ldots,w_1-1; \\ & & \mbox{{\rm (condizioni iniziali)}} \\ p_1; & \mbox{{\rm se }} \hat W=w_1,\ldots,W.\end{array} \right . \]

Il Problema dello Zaino 0/1: un algoritmo di PD, 3

In generale,  per m=2, …, n, si ha che

\[ f_{m,\hat W}=\left\{ \begin{array}{lll} f_{m-1,\hat W}, & \mbox{{\rm se }} \hat W=0,1,\ldots,w_{m}-1; \\ & & \mbox{{\rm (ricorrenza)}} \\ P, & \mbox{{\rm se }} \hat W=w_m,\ldots,W, \end{array} \right .\]

dove
\[ P=\max\left\{f_{m-1,\hat W},\ f_{m-1,\hat W-w_m}+p_m\right\}. \]

Il valore che la funzione obiettivo assume in corrispondenza di una soluzione ottima al problema \mbox{(Z$_{0/1}$)$_{nW}$} sarà contenuto in f_{n,W} .

Il Problema dello Zaino 0/1: un algoritmo di PD, 4

Il Problema dello Zaino 0/1 è un problema “difficile” dal punto di vista computazionale (NP-completo).
Infatti, un semplice algoritmo che realizza la ricorrenza e le condizioni iniziali appena formalizzate ha complessità computazionale pari a O(nW) .

Si noti che per valori di W molto elevati, l’algoritmo B&B risulta più efficiente.

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion