Nel capitolo dedicato alle tecniche di Divide et Impera, abbiamo visto come sia possibile decomporre un problema complesso in più sottoproblemi definiti su istanze di dimensione inferiore e (quasi) uguale. Vi sono però situazioni in cui risulta essere più comodo (e utile) suddividere il problema in sottoproblemi le cui varie istanze possono avere dimensioni molto diverse. Inoltre, in molti casi, a causa delle dipendenze esistenti all’interno dei vari sottoproblemi, la chiamata di una procedura ricorsiva può portare all’esecuzione di calcoli già eseguiti.

Il metodo solitamente utilizzato per risolvere problemi di questa natura è quello della Programmazione Dinamica. Essa consiste nel determinare, per una data istanza i , l’insieme S(i) di tutte le sotto-istanze da cui dipende il calcolo della soluzione i-esima . Successivamente si costruisce una relazione di dipendenza tra tutti i vari elementi di S(i) e infine, si ricavano le soluzioni di S(i) a partire da quelle di dimensione minore.

I risultati parziali via via ottenuti vengono conservati in opportune aree di memoria, così da poter essere riutilizzati in caso di necessità. Per questo motivo, spesso, ad una riduzione dei tempi di calcolo corrisponde un aumento dei costi di mantenimento spaziale.

La procedura di Fibonacci

All’interno del capitolo dedicato alla Ricorsione, abbiamo affrontato il problema relativo al calcolo del valore n-esimo della sequenza di Fibonacci.

Procedura Fibonacci (n)
begin
  if n<=1 then          // costo 2 (lettura valore e confronto)
    return n            // costo 1
  else
    a := n - 1          // costo 3 (lettura valore, calcolo risultato e assegnamento)
    x := fibonacci (a)  // costo 2 + costo Tfibonacci(n - 1)
    b := n - 2          // costo 3 (lettura valore, calcolo risultato e assegnamento)
    y := fibonacci (b)  // costo 2 + costo Tfibonacci(n - 2)
    return (x + y)      // costo 4 (2 letture valore, calcolo risultato e assegnamento)
 end

È possibile che durante l’esecuzione della procedura alcuni termini della sequenza f_0, f_1, \dots, f_n vengano varie volte. Ad esempio il termine f_{n-2} deve essere calcolato due volte, una per determinare f_n = f_{n-1} + f_{n-2} e una per calcolare f_{n-1} = f_{n-2} + f_{n-3} . Lo stesso ragionamento può essere esteso agli altri elementi della sequenza.

All’interno del capitolo dedicato alla ricorsione abbiamo risolto il problema sfruttando la tecnica del Divide et Impera, in questo modo siamo stati in grado di calcolare il costo d’esecuzione della procedura: T(n) = \Omega((\frac{\sqrt{5}+1}{2})^n) = \Omega((1,6)^n) .

Una soluzione più efficiente può però essere ottenuta sfruttando la programmazione dinamica. Per determinare il valore corretto all’interno della sequenza viene creato un vettore in grado di memorizzare tutti i valori intermedi della stessa:

V = (V[1], V[2], \dots , V[n])

Procedura Fibonacci_D (n)
begin
  a := 0           // primo indice della sequenza
  b := 1           // secondo indice della sequenza
  k := 2           // terzo indice della sequenza (contiene il risultato)
  V[a] := 0        // vettore contenente i valori della sequenza
  V[b] := 1

  while k<=n do    // finchè non sono arrivato al passo n-esimo...
    x := V[a]      // scarico i valori precedenti
    y := V[b]

    v[k] := x + y  // eseguo il calcolo del valore corrente

    a := b         // aggiorno gli indici
    b := k
    k := k + 1
  end while

  return V[n]      // ritorno l'ultimo risultato
end

La procedura esegue n cicli in un tempo T(n) = \Theta(n) , notevolmente più efficiente rispetto al caso precedente. Essa richiede però un costo di memorizzazione uguale a \Theta (n) . È però possibile migliorare anche il costo di memorizzazione, osserviamo infatti che non è necessario mantenere in memoria un vettore n elementi; per calcolare f_i è sufficiente ricordare i due elementi che lo precedono: f_{i-1} e f_{i-2} .

Procedura Fibonacci_D2 (n)
begin
  if n&lt;=1 then
    return n
  else
    x := 0            // variabile contenente il primo valore (ex V[a])
    y := 1            // variabile contenente il secondo valore (ex V[b])

    for k=2, …, n do  // fin che non sono arrivato al passo n-esimo
      t := y          // eseguo il calcolo sfruttando una variabile temporanea
      y := x + y
      x := t
    end for

    return y          // ritorno il risultato
  end if
end

Così facendo il costo di memorizzazione si riduce a: O(1).