Home

Federica EU

1/7

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)$ .