ASD2 - 03 - Programmazione Dinamica

In questa lezione abbiamo ripassato il paradigma della programmazione dinamica. In particolare abbiamo descritto tre algoritmi: uno per moltiplicare una sequenza di matrici, uno per calcolare il massimo indipendent set in un albero, e l'ultimo per calcolare la sottosequenza palindroma più lunga di una stringa.

Prima di introdurre i vari algoritmi facciamo una piccola nota riguardo alla programmazione dinamica.

Osservazione: In modo molto simile alla strategia divide et impera, anche nel paradigma della programmazione dinamica si cerca di spezzare il problema in sottoproblemi, risolvere i sottoproblemi separatamente e successivamente combinare il risultato dei sottoproblemi per ottenere ls soluzione al problema iniziale. Detto questo, una differenza significativa tra la tecnica divide et impera e la programmazione dinamica sta nel fatto che utilizzando la prima, il modo in cui spezziamo i sottoproblemi non dipende dal risultato dei sottoproblemi, mentre utilizzando la seconda il modo in cui spezziamo i sottoproblemi dipende dal risultato dei sottoproblemi.

Supponiamo di dover moltiplicare due matrici \(A\) e \(B\), di dimensione rispettivamente \((n \times m)\) e \((m \times r)\). La matrice risultante \(C = A \cdot B\) è una matrice \((n \times r)\), ed è ottenuta utilizzando la seguente formula

\[C = (c_{i, j})_{i, j}, \,\,\, c_{i, j} = \sum_{k = 1}^m a_{i, k} \cdot b_{k, j}\]

detto altrimenti, per ottenere l'elemento \(c_{i, j}\) si moltiplica la riga \(i\) della matrice \(A\) con la colonna \(j\) della matrice \(B\). Questo significa che per ottenre la matrice \(C\) dobbiamo effettuare un totale di \(m \cdot n \cdot r\) moltiplicazioni.

Supponiamo adesso di dover moltiplicare tra loro tre matrici \(A, B, C\), di dimensione rispettivamente \((a \times b)\), \((b \times c)\), \((c \times d)\). Notiamo che questa volta per ottenere la matrice prodotto \(D = A \cdot B \cdot C\) abbiamo due modi distinti per procedere, ciascuno dei quali richiede un particolare numero di operazioni

  • \(D = (A \cdot B) \cdot C\)

    In questo caso abbiamo un totale di \(bac + cad\) moltiplicazioni da effettuare, in quanto dobbiamo prima calcolare \(A \cdot B\), e successivamente dobbiamo moltiplicare il risultato di tale operazione, che è una matrice \((a \times c)\), per la matrice \(C\).

  • \(D = A \cdot (B \cdot C)\)

    In questo caso invece abbiamo un totale di \(bcd + abd\) moltiplicazioni da effettuare.

Anche se dalla proprietà associativa della moltiplicazione matriciale le due strade sono equivalenti, nel senso che entrambe calcolano la stessa matrice, dal punto di vista computazionale il numero di moltiplicazioni che eseguo può essere diverso. Questo significa che esiste una strada ottimale per ottenere il risultato voluto effettuando il minor numero di moltiplicazioni.

Siamo ora in grado di scrivere il problema che vogliamo risolvere: data una sequenza di matrici \(M_1, ..., M_n\), con \(M_i \in \mathbb{R}^{m_{i-1} \times m_i}\), per \(i = 1, ..., n\), vogliamo trovare il numero minimo di moltiplicazioni da effettuare per calcolare la matrice prodotto \(M_1 \cdot M_2 \cdot ... \cdot M_n\).

Andiamo quindi a risolvere questo problema utilizzando un approccio di programmazione dinamica. Supponiamo quindi di calcolare il prodotto della sequenza di matrici \(M_i, ..., M_k, M_{k+1}, ..., M_j\). Se scegliamo di spezzare il prodotto nell'indice \(k\), troviamo la seguente situazione

\[\underbrace{(M_i \, \cdot \,\,\, ... \,\,\, \cdot M_k)}_{\text{matrice } m_{i-1} \times m_k} \cdot \underbrace{(M_{k+1} \, \cdot \,\,\, ... \,\,\, \cdot M_j)}_{\text{matrice } m_k \times m_j}\]

in questo caso quindi il costo per calcolare il prodotto delle matrici è dato da:

  1. Il costo per calcolare la sequenza di matrici \((M_i \, \cdot \,\,\, ... \,\,\, \cdot M_k)\).

  2. Il costo per calcolare la sequenza di matrici \((M_{k+1} \, \cdot \,\,\, ... \,\,\, \cdot M_j)\).

  3. Il costo per combinare le due matrici tra loro, che avendo fissato \(k\) è dato da \(m_k \cdot m_{i-1} \cdot m_j\).

La struttura del problema e il modo in cui può essere spezzato ci suggerisce quindi di formalizzare i sottoproblemi nel seguente modo:

  • \(C(i, j) :=\) Numero minimo di moltiplicazioni da effettuare per moltiplicare la sequenza di matrici \(M_i,..., M_j\)

Siamo ora in grado di calcolare i sottoproblemi come segue

  • \(C(i, i) = 0\)

  • \(C(i, j) = \underset{i \leq k < j}{min} \Big\{C(i, k) + C(k+1, j) + m_k \cdot m_{i-1} \cdot m_j\Big\}\)

Notiamo come la soluzione al nostro problema generale è data dal valore di \(C(1, n)\).

Infine, per terminare la trattazione di questo problema riportiamo lo pseudocodice che calcola il valore dei vari sottoproblemi \(C(i, j)\) nel corretto ordine.

Infine, nel file matrix_multiplication.py è presente una implementazione in python dell'algoritmo appena discusso.

Ricordiamo che dato un grafo \(G = (V, E)\), un sottoinsieme dei nodi \(S \subseteq V\) è detto indipendent set di \(G\) se vale la seguente cosa

\[\forall u, v \in S: \,\, (u, v) \not \in E\]

in altre parole, \(S\) è un indipendent set se e solo se nessun nodo in \(S\) è collegato ad un altro nodo in \(S\) tramite un arco del grafo.

Il problema IS consiste nel trovare l'indipendent set più grande dato un grafo \(G\). Volendo essere più formali, possiamo schemtizzare il problema come segue

  • Input: Grafo \(G = (V, E)\).

  • Possibile soluzione: \(S \subseteq V\) tale che \(S\) è un indipendent set di \(G\).

  • Obiettivo: Massimizzare il numero di elementi di \(S\), ovvero \(\max |S|\).

Notiamo he la versione generale del problema IS è un noto problema NP-Completo, ovvero è un problema per cui non si è ancora riusciti a scoprire una soluzione polinomiale. Andando però a restringere l'input ai soli alberi, esiste un algoritmo polinomale che risolve questo problema. Segue quindi la trattazione di questo algoritmo.

La restrizione del problema IS che andiamo a considerare è descritta come segue

  • Input: Grafo \(G = (V, E)\) aciclico e connesso.

  • Possibile soluzione: \(S \subseteq V\) tale che \(S\) è un indipendent set di \(G\).

  • Obiettivo: Massimizzare il numero di elementi di \(S\), ovvero \(\max |S|\).

Per andarlo a risolvere utilizziamo nuovamente la tecnica della programmazione dinamica. In particolare supponiamo di dover calcolare l'indipendent set massimo a partire dalla radice \(r\) del nostro albero. Notiamo la seguente cosa

  • Se scegliamo di inserire \(r\) nel nostro indipendent set, allora non possiamo inserire i figli di \(r\), ma solo i nipoti di \(r\).

  • Se non inseriamo \(r\) nel nostro indipendent set, allora possiamo inserire i figli di \(r\).

Possiamo quindi definire i seguenti sottoproblemi

  • \(I(u) :=\) Size del massimo indipendent set costruito con i nodi presenti nel sottoalbero radicato in \(u\).

che, seguendo le osservazioni fatte prima, vengono calcolati come segue

  • Per ogni \(u \in V\) foglia si ha che

    \[I(u) = 1\]

  • Per ogni \(u \in V\) non foglia si ha che

    \[I(u) = \max\{1 + \underset{v \in V: v \text{ nipote di } u}{\sum\limits} I(v), \,\,\,\, \underset{v \in V: (u, v) \in E}{\sum\limits} I(v)\}\]

Come abbiamo visto in precedenza, la risposta al nostro problema è data dal sottoproblema \(I(r)\), dove \(r\) è la radice dell'albero \(G\).

Per conclduere la trattazione di questo problema, notiamo che è possibile implementare questo algoritmo tramite una visita in profondità.

Come ultimo problema trattato in questa lezione, discutiamo il problema del calcolo della lunghezza della sottosequenza palindroma più lunga. In particolare, dato un alfabeto di simboli \(\Sigma\) e data una stringa \(S = a_1 a_2 ... a_n \in \Sigma^n\), vogliamo trovare la lunghezza della sottosequenza palindroma \(x_{i_1}, x_{i_2}, ..., x_{i_k}\) più lunga.

Ricordiamo che con sottosequenza palindroma intendiamo una sequenza che non cambia se si legge da sinistra a destra o da destra a sinistra. Un esempio di sequenza palindroma è \(aba\), oppure \(abba\).

Nuovamente, per risolvere il problema utilizziamo un approccio dinamico. Andiamo quindi a definire i seguenti sottoproblemi

  • \(OPT(i, j) :=\) Lunghezza della sottosequenza palindroma più lunga contenuta in \(x_i, x_{i+1}, ..., x_{j-1}, x_j\).

e procediamo con il loro calcolo

  • Per ogni \(i = 1,..., n\), si ha \(OPT(i, i) = 1\).

  • Per ogni \(i, j \in \{1, ..., n\}\) con \(i < j\), si ha

    \[OPT(i, j) = \begin{cases} 2 + OPT(i-1, j-1) \,\,\, & \,\,\,, S[i] == S[j] \\ max\Big\{OPT(i+1, j), \,\, OPT(i, j-1)\Big\} \,\,\, & \,\,\,, \text{ altrimenti } \\ \end{cases}\]

Segue quindi lo pseudocodice che descrive come risolvere i vari sottoproblemi nel corretto ordine

Nel file palindrome_subsequence.py è presente una implementazione in python dell'algoritmo appena discusso.