E facile verificare che, assumendo il criterio di costo uniforme, l’algoritmo richiede un tempo di calcolo Θ(n3) e uno spazio di memoria Θ(n2) su ogni grafo di ingresso di n nodi.
11.5 Cammini minimi
Un altro problema classico che si pu`o risolvere mediante programmazione dinamica riguarda il calcolo dei cammini di peso minimo che connettono i nodi in un grafo pesato.
Consideriamo un grafo diretto G = hV, Ei e una funzione costo w : E −→ Q tale che w(e) ≥ 0 per ogni e ∈ E. Per ogni cammino ` in G, ` = (v1, v2, . . . , vm), chiamiamo peso (o costo) di ` la somma dei costi dei suoi lati:
c(`) =
m−1
X
i=1
w(vi, vi+1)
Per ogni coppia di nodi u, v ∈ V si vuole determinare un cammino ` di peso minimo tra tutti i cammini da u a v, insieme al suo costo c(`).
Siano v1, v2, . . . , vni nodi di G. Il problema pu`o essere risolto calcolando le matrici D = [dij]i,j=1,2,...,n e P = [pij]i,j=1,2,...,nle cui componenti sono definite nel modo seguente: per ogni coppia di indici dis-tinti i, j, se esiste un cammino da vi a vj in G, dij rappresenta il costo del cammino di peso minimo che congiunge vi e vj e pij `e il predecessore di vjin tale cammino; se invece non esiste un cammino da via vj allora dij assume un valore convenzionale ∞, superiore al peso di ogni cammino in G, e pij assume il valore indefinito ⊥.
Conoscendo la matrice P `e possibile determinare un cammino di peso minimo da vi a vj semplice-mente scorrendo in modo opportuno la i- esima riga della matrice: se k1 = pij allora vk1 `e il penultimo nodo del cammino, se k2 = pik1 allora vk2 `e il terzultimo, e cos`ı via fino a determinare il primo nodo, ovvero vi.
Abbiamo cos`ı definito il problema per grafi con pesi non negativi. L’algoritmo che presentiamo tuttavia risolve il problema nel caso pi`u generale di grafi con pesi di segno qualsiasi, purch´e questi non formino cicli di costo negativo. Osserviamo che se esiste un ciclo di peso negativo lo stesso problema non `e ben definito.
Il metodo utilizzato per determinare la soluzione `e simile a quello descritto nella sezione precedente per calcolare la chiusura transitiva di un grafo. Per ogni tripla di indici i, j, k ∈ {1, 2, . . . , n} definiamo il coefficiente ckij come il costo del cammino di peso minimo da via vj passante per nodi di indice al pi`u uguale a k (esclusi i e j). Chiaramente dij = cnij. Inoltre definiamo i coefficienti c0ij nel modo seguente:
c0ij = w(vi, vj) se i 6= j e (vi, vj) ∈ E 0 se i = j ∞ altrimenti
Anche per questa famiglia di coefficienti possiamo definire un’equazione, analoga alla (11.1), che per-mette di calcolare i valori ckij, per i, j = 1, 2, . . . , n, conoscendo i ck−1ij :
ckij = min{ck−1ij , ck−1ik + ck−1kj }. (11.2) Basta osservare infatti che se ` `e un cammino di peso minimo da vi a vj passante per nodi di indice minore o uguale a k allora si verifica una dei due fatti seguenti:
1. ` passa solo per nodi di indice minore o uguale a k − 1, oppure
2. ` `e composto da due cammini che vanno rispettivamente da via vke da vka vj, entrambi di peso minimo tra tutti i cammini (congiungenti i rispettivi estremi) passanti per nodi di indice minore o uguale a k − 1.
Nel primo caso il costo di ` `e ck−1ij mentre nel secondo `e ck−1ik + ck−1kj ; inoltre in quest’ultimo il prede-cessore di vj in ` equivale al predecessore di vj nel cammino di costo minimo da vka vj passante per nodi di indice minore o uguale a k − 1.
Applicando l’equazione (11.2) possiamo allora descrivere un algoritmo del tutto simile a quello pre-sentato nella sezione precedente. Anche in questo caso possiamo limitarci a mantenere una sola matrice di valori ckij poich`e valgono le identit`a
ck−1ik = ckik e ck−1kj = ckkj
per ogni tripla di indici i, j, k. Cos`ı l’algoritmo calcola la matrice C = [cij] dei costi e quella B = [bij] dei predecessori dei cammini minimi che, al termine della computazione, coincideranno con le matrici D e P rispettivamente.
begin fori = 1, 2, . . . , ndo forj = 1, 2, . . . , ndo ifi = jthen ( cii:= 0 bii:= i else if(vi, vj) ∈ E then ( cij := w(vi, vj) bij := i else ( cij := ∞ bij := ⊥ fork = 1, 2, . . . , ndo fori = 1, 2, . . . , ndo forj = 1, 2, . . . , ndo ifcik+ ckj < cij then ( cij := cik+ ckj bij := bkj end
Concludiamo osservando che, assumendo il criterio di costo uniforme, il tempo di calcolo richiesto dall’algoritmo su ogni grafo di input di n nodi `e Θ(n3), mentre lo spazio di memoria `e Θ(n2).
Algoritmi greedy
Una delle tecniche pi`u semplici per la progettazione di algoritmi di ottimizzazione `e chiamata tecnica
greedy. Letteralmente questo termine significa “ingordo”, ma nel seguito preferiremo tradurlo “miope”.
Intuitivamente, questo metodo costruisce la soluzione di un problema di ottimizzazione mediante una successione di passi durante ciascuno dei quali viene scelto un elemento “localmente” migliore; in altre parole a ciascun passo la scelta migliore viene compiuta in un ambito limitato, senza controllare che il procedimento complessivo porti effettivamente al calcolo di una soluzione ottima per il problema.
Questa strategia, se da un lato permette solitamente di ottenere algoritmi semplici e facilmente im-plementabili, dall’altro pu`o portare alla definizione di procedure che non forniscono sempre la soluzione ottima. In questo capitolo vogliamo studiare le propriet`a degli algoritmi di questo tipo e verificare in quali casi `e possibile garantire che la soluzione costruita sia effettivamente la migliore.
12.1 Problemi di ottimizzazione
Per esprimere questi concetti in maniera precisa, introduciamo la nozione di sistema di indipendenza. Un sistema di indipendenza `e una coppia hE, F i nella quale E `e un insieme finito, F `e una famiglia F di sottoinsiemi di E chiusa rispetto all’inclusione; in altre parole, F ⊆ 2E (qui e nel seguito denoteremo con 2E la famiglia di tutti i sottoinsiemi di E) e inoltre
A ∈ F ∧ B ⊆ A ⇒ B ∈ F `
E evidente che, per ogni insieme finito E, la coppia hE, 2Ei forma un sistema di indipendenza.
Esempio 12.1
Sia G = (V, E) un grafo non orientato; diciamo che un insieme A ⊆ E forma una foresta se il grafo (V, A) `e privo di cicli. Denotiamo quindi con FGl’insieme delle foreste di G, ovvero
FG= {A ⊆ E | A forma una foresta}
`
E facile verificare che la coppia hE, FGi `e un sistema di indipendenza.
Viceversa, per ogni A ⊆ E, sia VA l’insieme dei vertici v ∈ V che sono estremi di un lato in A e diciamo che A forma un albero se il grafo (VA, A) `e connesso e privo di cicli: denotando con TGla famiglia degli alberi di G, ovvero
TG= {A ⊆ E | A forma un albero}, si verifica facilmente che hE, TGi non `e un sistema di indipendenza.
Esempio 12.2
Sia sempre G = (V, E) un grafo non orientato. Diciamo che un insieme A ⊆ E forma un matching se, per ogni coppia di lati distinti α, β ∈ A, α e β non hanno nodi in comune. Denotiamo inoltre con MGla famiglia dei sottoinsiemi di E che formano un matching. `E facile verificare che hE, MGi `e un sistema di indipendenza.
Analogamente, diciamo che un insieme S ⊆ V forma una clique di G se, per ogni coppia di nodi distinti s, u ∈ S, il lato
{s, v} appartiene a E. Denotiamo con CGla famiglia delle clique di G. Si pu`o verificare anche in questo caso che hV, CGi
forma un sistema di indipendenza.
Vari problemi di ottimizzazione possono essere definiti in modo naturale usando sistemi di indipen-denza pesati nei quali cio`e ogni elemento dell’insieme base `e dotato di un peso. Una funzione peso su un dato una sistema di indipendenza hE, F i, `e una arbitraria funzione w : E → IR+, dove IR+ `e l’insieme dei reali non negativi. Tale funzione pu`o essere ovviamente estesa ai sottoinsiemi di E ponendo, per ogni A ⊆ E, w(A) =P
x∈Aw(x). Possiamo allora formulare in modo preciso un problema di massimo: Istanza: un sistema di indipendenza hE, F i e una funzione peso w : E → IR+.
Soluzione : un insieme M ∈ F tale che w(M ) sia massimo (ovvero A ∈ F ⇒ w(A) ≤ w(M )).
In modo analogo possiamo definire un problema di minimo. In questo caso, dato una sistema di indipen-denza hE, F i, diciamo che un insieme A ∈ F `e massimale se non esiste B ∈ F diverso da A che include A, ovvero, per ogni B ∈ F , A ⊆ B ⇒ A = B.
Istanza: un sistema di indipendenza hE, F i e una funzione peso w : E → IR+.
Soluzione : un insieme A ∈ F massimale che sia di peso minimo (ovvero, tale che per ogni B ∈ F massimale w(A) ≤ w(B)).
Definiamo ora l’algoritmo greedy per il problema di massimo; tale algoritmo `e definito dalla seguente procedura. ProcedureMIOPE(E, F, w) begin S := ∅ Q := E whileQ 6= ∅do begin
determina l’elemento m di peso massimo in Q Q := Q − {m}
ifS ∪ {m} ∈ F thenS := S ∪ {m}
end returnS
end
Fissata una istanza del problema di ottimizzazione, ovvero una tripla E, F, w definita come sopra, la precedente procedura fornisce in uscita un insieme S che appartiene certamente a F (`e quindi una soluzione ammissibile), ma non `e necessariamente ottimo nel senso che pu`o non rappresentare un insieme di peso massimo in F .
Si pongono allora, a questo livello di generalit`a , due problemi:
1. qual `e il tempo di calcolo dell’algoritmo greedy, cio`e quanti passi di calcolo devono essere compiu-ti avendo come ingresso un insieme E di n elemencompiu-ti? A questo proposito osserviamo che l’input dell’algoritmo sar`a qui costituito dal solo insieme E e dalla funzione peso w: si suppone che F sia automaticamente definito in maniera implicita mediante una opportuna regola e sia comunque
disponibile una routine per verificare quando un insieme A ⊆ E appartiene a F . La famiglia F potrebbe infatti contenere un numero di elementi esponenziale in n e quindi la sua specifica diretta sarebbe improponibile.
2. In quali casi l’algoritmo greedy fornisce effettivamente una soluzione ottima? Qualora l’algoritmo non fornisca la soluzione ottima, si pone un terzo problema, ovvero quello di valutare la bont`a della soluzione prodotta. Questo porta a studiare una classe di algoritmi, detti di approssimazione, che in generale non forniscono la soluzione migliore a un dato problema ma ne producono una che approssima quella richiesta. In molti casi il calcolo della soluzione ottima `e troppo costoso in termini di tempo e ci si accontenta di una soluzione approssimata, purch`e ovviamente quest’ultima sia calcolabile in un tempo accettabile.
Concludiamo osservando che un algoritmo analogo pu`o essere descritto per il problema di minimo. Esso `e definito dalla seguente procedura:
ProcedureMIOPE-MIN(E, F, w) begin S := ∅ Q := E whileQ 6= ∅do begin
determina l’elemento m di peso minimo in Q Q := Q − {m}
ifS ∪ {m} ∈ F thenS := S ∪ {m}
end returnS
end
Anche per tale algoritmo valgono le osservazioni fatte a proposito della procedura MIOPE.