Algoritmi e Strutture Dati IIEsercizi di Programmazione Dinamica

Prof. Paola Bonizzoni

Anno Accademico 2007/2008

Appunti scritti da Alberto Leporati, Rosalba Zizza e Christian Pirovano

Esercizio 1

Si determini un algoritmo per trovare in tempo O(n2) la piu lunga sottose-quenza monotona (crescente) di una sequenza di n numeri interi.Per esempio, sia X = 2, 4, 7, 6, 11, 13, 21, 14, 1. Allora la piu lunga sottose-quenza monotona crescente e 6, 11, 13, 21, di lunghezza 4.

Soluzione. Sia X = x1, . . . , xn la sequenza di numeri interi; per ogni i ∈{1, 2, . . . , n}, indichiamo con Xi la sottosequenza x1, . . . , xi. Sempre peri ∈ {1, 2, . . . , n}, sia c[i] la lunghezza della piu lunga sequenza crescente diXi che termina con xi (cioe che contiene effettivamente xi).

Il motivo per cui imponiamo che l’elemento xi appartenga effettivamentealla sottosoluzione ottima relativa alla sottosequenza Xi e che quando andia-mo a considerare un elemento xj con j > i, per sapere se tale elemento puofar parte della sottosoluzione ottima relativa alla sottosequenza Xj dobbia-mo verificare che la condizione xi < xj sia verificata; questo chiaramente lopossiamo fare solo se sappiamo qual e l’ultimo elemento della sottosequenzacrescente piu lunga contenuta in Xi. Dovendo quindi memorizzare da qual-che parte questa informazione, la cosa migliore e quella di incorporarla (comeabbiamo fatto sopra) nel valore di c[i]. D’altra parte, osserviamo che se l’ele-mento xi non appartenesse alla piu lunga sottosequenza crescente contenutain Xi vorrebbe dire che esiste un elemento xk, con k < i, che termina talesequenza. Ma allora tale sequenza sarebbe anche la piu lunga sottosequenzacrescente contenuta in Xk; quindi, tanto vale definire il valore di c[i] comeabbiamo fatto sopra.

Ricaviamo ora un’equazione di ricorrenza che ci consenta di calcolare ilvalore di c[i] per ogni i ∈ {1, 2, . . . , n}. E facile vedere che vale c[1] = 1.Infatti, le sottosequenze possibili di X1 (che e formata solamente da x1) sonodue: quella che contiene x1 e quella che non lo contiene. Entrambe sono

1

crescenti, e hanno rispettivamente lunghezza 1 e 0. Quindi la piu lungasottosequenza crescente di X1 ha lunghezza 1, e pertanto poniamo c[1] = 1.

Sia ora i > 1, e supponiamo di aver gia calcolato i valori di c[1], c[2], . . .,c[i − 1]. Poiche le sottosequenze di X1, X2, . . . , Xi−1 possono essere tutteconsiderate sottosequenze di Xi−1, abbiamo che i valori c[1], c[2], . . . , c[i− 1]rappresentano le lunghezze delle piu lunghe sottosequenze crescenti di Xi−1

che terminano, rispettivamente, con x1, x2, . . . , xi−1. Tra queste ci sarannoalcune sottosequenze alle quali possiamo attaccare xi e altre alle quali l’ele-mento xi non puo essere attaccato. Se prendiamo la piu lunga sottosequenzaalla quale possiamo attaccare xi, e aggiungiamo xi, otteniamo la piu lungasottosequenza crescente di Xi che termina con xi. La lunghezza di tale sot-tosequenza sara uguale a 1 piu la lunghezza della sottosequenza alla qualeabbiamo attaccato xi. Pertanto il valore di c[i] e dato da:

c[i] =

{1 + max{c[j] | 1 ≤ j < i, xj < xi} se i > 1

1 se i = 1

Poiche puo accadere che l’insieme {c[j] | 1 ≤ j < i, xj < xi} sia vuoto(il che corrisponde al fatto che l’elemento xi e minore di tutti gli elementiprecedenti, e quindi non puo essere attaccato a nessuna delle sottosequenze diXi−1), assumiamo per definizione che sia max ∅ = 0, cosı che il corrispondentevalore di c[i] sia uguale a 1.

Una volta calcolati i valori c[1], c[2], . . . , c[n], la soluzione al problemaproposto e data da:

max1≤i≤n

c[i]

che e facilmente ricavabile da un semplice ciclo for che scandisce il vettorec[1..n] alla ricerca del massimo elemento.

L’algoritmo che calcola i valori c[1], c[2], . . . c[n] e facilmente ricavabiledall’equazione di ricorrenza, ed e il seguente:

Max-Growing-Sequence

c[1] ← 1for i ← 2 to n do

max ← 0for j ← 1 to i− 1 do

if (xj < xi) and (c[j] > max)then max ← c[j]

2

endif

endfor

c[i] ← 1 + maxendfor

return c

E facile verificare che la complessita in tempo dell’algoritmo proposto eO(n2), mentre lo spazio richiesto e quello necessario per memorizzare il vet-tore c[1..n], e quindi Θ(n).

Esercizio 2

Siano date n scatole B1, . . . , Bn. Ogni scatola Bi e descritta da una tripla(ai, bi, ci), le cui componenti denotano rispettivamente lunghezza, larghezzae altezza della scatola. La scatola Bi puo essere inserita nella scatola Bj se esolo se ai < aj, bi < bj e ci < cj; in particolare, le scatole non possono essereruotate. Per brevita indichiamo con Bi ⊂ Bj il fatto che la scatola Bi puoessere inserita nella scatola Bj.

Descrivere un algoritmo efficiente per determinare il massimo valore di ktale che esiste una sequenza Bi1 , . . . , Bik che soddisfa le condizioni:

Bi1 ⊂ Bi2 ⊂ · · · ⊂ Bik

ei1 < i2 < · · · < ik

Analizzare la complessita dell’algoritmo proposto.

Soluzione. Nonostante questo esercizio sembri piu complicato di quelloprecedente, il problema proposto e isomorfo a quello trattato nell’esercizioprecedente. Si tratta infatti di trovare la piu lunga sottosequenza crescentedi scatole contenuta nella sequenza B1, . . . , Bn. La tecnica di soluzione diquesto problema e identica a quella adottata nell’esercizio precedente, doveal posto di verificare se due interi xj e xi sono tali che xj < xi andiamo averificare se due scatole Bj e Bi sono tali che Bj ⊂ Bi, ovvero se aj < ai,bj < bi e cj < ci.

Sia allora z[1..n] un vettore di n componenti (non lo chiamiamo c, comeabbiamo fatto nell’esercizio precedente, per non confoderci con le altezze delle

3

scatole). Detta z[i] la lunghezza massima di una sottosequenza crescente adelementi in B1, . . . , Bi che contiene Bi, calcoliamo i valori z[1], z[2], . . . , z[n]in questo ordine. La soluzione del problema proposto sara data dal valore di:

max1≤i≤n

z[i]

L’equazione di ricorrenza che consente di ricavare il valore di z[i] e prati-camente identica a quella dell’esercizio precedente:

z[i] =

{1 + max{z[j] | 1 ≤ j < i, aj < ai, bj < bi, cj < ci} se i > 1

1 se i = 1

dove, come abbiamo osservato nell’esercizio precedente, assumiamo che valgamax ∅ = 0.

L’algoritmo che calcola i valori di z[1], z[2], . . . , z[n] e il seguente:

Max-Boxes-Chain

z[1] ← 1for i ← 2 to n do

max ← 0for j ← 1 to i− 1 do

if (aj < ai) and (bj < bi) and (cj < ci) and (z[j] > max)then max ← z[j]

endif

endfor

z[i] ← 1 + maxendfor

return z

E facile verificare che la complessita in tempo dell’algoritmo propostoe O(n2), mentre lo spazio richiesto e quello necessario per memorizzare ilvettore z[1..n], e quindi Θ(n).

Esercizio 3

Scrivere un algoritmo efficiente che, date due sequenze di interi positiviX = x1, . . . , xn e Y = y1, . . . , ym, determini la lunghezza della piu lunga

4

sottosequenza crescente comune a X e a Y , ovvero:

max{k | ∃ i1, i2, . . . , ik ∈ {1, 2, . . . , n}, j1, j2, . . . , jk ∈ {1, 2, . . . ,m} :

i1 < i2 < · · · < ik, j1 < j2 < · · · < jk,

xi1 = yj1 < xi2 = yj2 < . . . < xik = yjk}

Ad esempio, se X = 1, 4, 12, 3, 7, 16, 8 e Y = 12, 1, 3, 17, 8 allora la lunghezzadella piu lunga sottosequenza crescente comune a X e a Y e 3 (corrispondentea 1, 3, 8), mentre 12, 3, 8 e una LCS ma non e crescente.

Soluzione. La soluzione di questo esercizio e molto simile a quelle date pergli esercizi precedenti. Come al solito, indichiamo con Xi la sottosequenzax1, x2, . . . , xi di X, e con Yj la sottosequenza y1, y2, . . . , yj di Y . I sottoproble-mi naturali del problema proposto consistono nel determinare la lunghezzadi una LCS crescente tra Xi e Yj, per i ∈ {1, . . . , n} e j ∈ {1, . . . , m}.

Come abbiamo fatto negli esercizi precedenti, per essere sicuri che la so-luzione al problema sia valida (cioe che la LCS di cui calcoliamo la lunghezzasia crescente) occorre memorizzare da qualche parte il valore dell’ultimo ele-mento delle sottosequenze ottime corrispondenti ai sottoproblemi. Convienepertanto definire una matrice c[1..n, 1..m], dove il valore di c[i, j] e la lun-ghezza di una LCS crescente tra Xi e Yj tale che l’ultimo elemento della LCSe uguale sia a xi che a yj (e quindi, in particolare, xi = yj).

Ricaviamo l’equazione di ricorrenza che consente di determinare il valoredi c[i, j]. Se xi 6= yj, non esiste una LCS crescente tra Xi e Yj che terminasia con xi che con yj; pertanto, in questo caso abbiamo c[i, j] = 0. Se invecexi = yj, occorre cercare la piu lunga tra le LCS crescenti di Xs e Yt, per tuttii valori di s e t tali che 1 ≤ s < i e 1 ≤ t < j, che terminano con un valoreminore di xi. Detti s e t i valori di s e t cosı individuati1, il valore di c[i, j]sara uguale a 1 + c[s, t]. Quindi, l’equazione di ricorrenza che consente diricavare c[i, j] e la seguente:

c[i, j] =

{0 se xi 6= yj

1 + max{c[s, t] | 1 ≤ s < i, 1 ≤ t < j, xs ≤ xi} se xi = yj

dove, come abbiamo fatto negli esercizi precedenti, assumiamo che valgamax ∅ = 0.

1s e t sono cioe i valori massimi tra gli s e t per cui valgono le disequazioni 1 ≤ s < i e1 ≤ t < j

5

La soluzione del problema proposto sara data dal valore di:

max1 ≤ i ≤ n1 ≤ j ≤ m

c[i, j]

L’algoritmo che calcola i valori di c[i, j] e il seguente. Si osservi che ivalori vengono calcolati dalla prima verso l’ultima riga; all’interno di ogniriga, i valori vengono calcolati da sinistra verso destra.

Growing-LCS

for i ← 1 to n do

for j ← 1 to m do

if xi 6= yj

then c[i, j] ← 0else max ← 0

for s ← 1 to i− 1 do

for t ← 1 to j − 1 do

if xs < xi and c[s, t] > maxthen max ← c[s, t]

endif

endfor

endfor

c[i, j] ← 1 + maxendif

endfor

endfor

return c

E facile verificare che la complessita in tempo dell’algoritmo proposto eO((nm)2), mentre lo spazio richiesto e quello necessario per memorizzare ilvettore c[1..n, 1..m], e quindi Θ(nm).Di seguito vediamo la matrice c ottenuta con le stringhe X = 1, 4, 12, 3, 7, 16, 8e Y = 12, 1, 3, 17, 8 (sulle intesazioni di righe e colonne, mettiamo diretta-mente i valori di xi e yj). In questo caso l’ottimo lo si trova in posizione c[7, 5],in generale lo si deve cercare come massimo elemento in tutta la matrice.

6

12 1 3 17 81 0 1 0 0 04 0 0 0 0 0

12 1 0 0 0 03 0 0 2 0 07 0 0 0 0 0

16 0 0 0 0 08 0 0 0 0 3

Tabella 1: Matrice c, con le piu lunghe LCS crescenti tra xi e yj

Esercizio 4

Si dice che una sequenza di interi x1, x2, . . . , xm e una sequenza zig–zag se,per ogni i ∈ {1, 2, . . . , m− 1}, vale:

xi < xi+1 se i e dispari

xi > xi+1 se i e pari

Ad esempio, 3, 8, 1, 5, 2 e una sequenza zig–zag, mentre 3, 8, 10, 5, 2 non euna sequenza zig–zag (10 e maggiore di 8).Descrivere e analizzare un algoritmo che, data una sequenza Y = y1, y2, . . . , ym,determini la lunghezza della piu lunga sottosequenza zig–zag di Y .

Ad esempio, se Y = 3, 4, 8, 5, 6, 2 allora la lunghezza massima e 5 (corri-spondente alla sottosequenza 3, 8, 5, 6, 2, o anche 4, 8, 5, 6, 2).

Soluzione.1. Data Y = y1y2 · · · yn, sia x1 · · · xm la piu lunga sottosequenza ZIG-

ZAG di Y , dove xm = yt, con 1 ≤ t ≤ n (ossia t e l’indice dell’ultimoelemento preso effettivamente nella sequenza ZIG-ZAG). Se |X| e pari, ossiam e pari, allora x1 · · ·xm−1 deve essere la piu lunga sottosequenza ZIG-ZAGdi lunghezza dispari di y1 · · · yk, con k < t e yk < yt. Se cosı non fosse, esiste-rebbe un’altra sottosequenza di lunghezza dispari, piu lunga di x1 · · ·xm−1,con ultimo elemento minore di yt tale che aggiungendo yt, otterrei una sotto-sequenza ZIG-ZAG di Y di lunghezza maggiore di x1 · · · xm, il che e assurdo,dato che x1 · · · xm era la soluzione ottima. Simmetricamente se m e dispari.

2. Definiamo Z(i, 0) la lunghezza della piu lunga sottosequenza a ZIG-ZAG di lunghezza pari di y1 · · · yi, che termina con yi. Similmente, definiamoZ(i, 1) la lunghezza della piu lunga sottosequenza a ZIG-ZAG di lunghezza

7

dispari di y1 · · · yi, che termina con yi. E importante notare che yi deveessere l’ultimo elemento della sequenza a ZIG-ZAG di y1 · · · yi, altrimentinon sarebbe possibile verificare la natura a ZIG-ZAG della sequenza stessa.Allora, si ha

Z(i, 0) =

1 + max{Z(k, 1)|1 ≤ k < i, yk < yi} se i ≥ 20 se i = 1 oppure

6 ∃k t.c. 1 ≤ k < i, yk < yi.

Z(i, 1) =

1 + max{Z(k, 0)|1 ≤ k < i, yk > yi} se i ≥ 21 se i = 1 oppure

6 ∃k t.c. 1 ≤ k < i, yk > yi.

La soluzione si ha calcolando

max1≤i≤n

{Z(i, 0), Z(i, 1)}

3. Di seguito lo pseudocodice che implementa le equazioni di program-mazione dinamica trovate.

Z(1,0):=0; Z(1,1)=1;

massimo:=0;

for i:=1 to n do

begin

for k:=i-1 downto to 1 do

begin

max1:=-1;

max2:=0;

if yk < yj then begin

q:=Z(k,1);

if q> max1 then max1:=q

end

else begin

q:=Z(k,0);

if q>max2 then max2 :=q

end

end

8

Z(i,0):=1+max1;

Z(i,1):=1+max2;

if (massimo < max{Z(i, 0), Z(i, 1)}) then

massimo := max{Z(i, 0), Z(i, 1)}end

return massimo

Riportiamo di seguito un esempio di Z per Y = 3, 4, 8, 5, 6, 2.

Z(0) 0 2 2 2 4 0Z(1) 1 1 1 3 3 5

Esercizio 5

Siano G1 = (V, E1) e G2 = (V,E2) due grafi diretti definiti sullo stessoinsieme di vertici V = {v1, v2, . . . , vn}, i cui archi sono del tipo (vi, vj), con1 ≤ i < j ≤ n. Ad ogni arco (u, v) ∈ Ei, i = 1, 2, e associato un costo ci(u, v),intero e strettamente positivo. Un cammino (vi1 , vi2 , . . . , vik), vij ∈ V , e dettoalternante se alterna archi di E1 ad archi di E2, ovvero se (vij , vij+1

) ∈ E1

per ogni j dispari, e (vij , vij+1) ∈ E2 per ogni j pari.

Scrivere l’equazione di ricorrenza per determinare, dati G1, G2, il cammi-no alternante di costo minimo da v1 a vn.

Possibile soluzione. (a)1. Supponiamo di aver trovato un cammino tra i vertici (v1, . . . , vn), cheminimizza il costo totale e che sia alternante. L’ultimo arco puo essere di E1

o di E2. La soluzione ottima sara data dal minimo tra il cammino che terminacon un arco di E1 e quello che termina con arco di E2. Di conseguenza, ilcammino minimo alternante sara dato dalla somma del costo del camminominimo su (v1, . . . , vn−1) che termina con arco di E2 e il costo dell’arco di E1

che incide su vn nel primo caso, e viceversa nel secondo caso. Se questa nonfosse ottima per n − 1 vertici, potrei trovarne un’altra ottima per n verticiaggiungendo a questa il costo dell’ultimo arco (assurdo).

2. Definiamo M(i, 1) = costo minimo di un cammino alternante da v1

a vi, dove l’ultimo arco considerato e di E1 e M(i, 2) = costo minimo diun cammino alternante da v1 a vi, dove l’ultimo arco considerato e di E2.

9

Indicheremo con ck(j, i) il costo dell’arco (vj, vi) nel grafo Gk, per k = 1, 2.La ricorrenza e

M(i, 1) = min1≤j<i

{M(j, 2) + c1(j, i)}

M(i, 2) = min1≤j<i

{M(j, 1) + c2(j, i)}

e inoltre

M(1, 1) = 0, M(1, 2) = 0

La soluzione si avra calcolando il

min{M(n, 1),M(n, 2)}

Nota. Chiaramente si poteva anche definire M(i, k) il costo minimo di cam-mino alternante da vi a vn dove il primo arco e in Ek, per k = 1, 2. In talcaso avremmo avuto

M(i, 1) = mini<j≤n

{M(j, 2) + c1(i, j)}

M(i, 2) = mini<j≤n

{M(j, 1) + c2(i, j)}

e inoltre

M(n, 1) = 0, M(n, 2) = 0

La soluzione si avra calcolando M(1, 1).

Esercizio 5b

Sia G = (V,E) un grafo diretto definito su un insieme di vertici V ={v1, v2, . . . , vn}, i cui archi sono del tipo (vi, vj), con 1 ≤ i < j ≤ n. Adogni arco (u, v) ∈ E, e associato un costo wu,v, intero e strettamente positi-vo. Sia c : E → {R, N} una funzione che assegna il colore rosso (R) o nero(N) agli archi di G.Scrivere un’equazione di ricorrenza per calcolare il costo minimo di un cam-mino da v1 a vn che non contenga due archi consecutivi dello stesso colore.

10

Nota: l’esercizio e simile al precedente. Si tratta di trovare un camminoalternante in G.

Possibile soluzione.Si definisca D(k)(i, j, cI , cF ) il costo di un cammino minimo tra un nodo i eun nodo j in cui tutti i vertici intermedi sono nell’insieme {1, . . . , k}. Sia cI

il colore assegnato al primo arco del cammino, e sia cF il colore assegnatoall’ultimo arco del cammino da i a j.Il caso base dell’equazione di ricorrenza si ottiene considerando il camminoche non ha alcun vertice intermedio (quindi k = 0):

D(0)(i, j, cI , cF ) =

wi,j se (i, j) ∈ E, cI = cF

0 se i = j∞ altrimenti

Cioe il costo di un cammino minimo senza vertici intermedi e wi,j se (i, j)e un arco di G e se il colore del primo arco e il colore dell’ultimo arco sonouguali (in quanto ho un solo arco).Il costo e 0 se i e j coincidono (non vi sono archi nel cammino).Il costo e ∞ se i 6= j e (i, j) /∈ E, oppure se cI 6= cF (in quanto c’e un soloarco, che puo avere un solo colore).La ricorrenza e definita come:

D(k)(i, j, cI , cF ) = min

{D(k−1)(i, k, cI , cF1) + D(k−1)(k, j, cI1, cF ),D(k−1)(i, j, cI , cF )

dove cF1 6= cI1.Questo significa che il peso di un cammino minimo da i a j in cui tutti i verticiintermedi sono in {1, . . . , k} e dato dal minimo tra il costo di un camminominimo da i a k in cui tutti i vertici intermedi sono in {1, . . . , k − 1} piu ilcosto di un cammino minimo da k a j in cui tutti i vertici intermedi sono in{1, . . . , k − 1} e il costo di un cammino minimo tra i e j senza passare da k.In figura 1 un esempio di cammino tra i e j.

11

i j

k

R N

cF 1

cI 1

Figura 1: Cammino minimo tra i e j considerato come somma dei camminitra i e k e tra k e j.

Esercizio 6

Sia data A = [aij] matrice n × m di interi. Una A-lista e una sequenza di(a1j1 , a2j2 , . . . , anjn), dove 1 ≤ j1 ≤ · · · jn ≤ m. Il peso di una A-lista e lasomma degli elementi che la compongono. Scrivere l’equazione di ricorrenzaper determinare, data in input A, il massimo peso di una A-lista.

Possibile soluzione. 1. Una soluzione ottima e caratterizzata da elementidi righe successive, ossia prendo un elemento per riga, senza mai prendere unelemento con indice di colonna inferiore. Ad ogni passo decido se prendere unelemento, e in tal caso devo spostarmi solo di una riga, oppure non prendereun elemento, e in tal caso richiamo semplicemente il problema sulla stessariga e un’altra colonna. Se (a1j1 , a2j2 , . . . , anjn), e una soluzione ottima per A(di dimensione n × m), allora (a1j1 , a2j2 , . . . , an−1jn−1) deve essere soluzioneottima per A di dimensione (n− 1)×m; se cosınon fosse, quando aggiungol’ultimo elemento della riga n-sima, otterrei una soluzione per A originariamigliore di quella ottima (assurdo).

2. Definiamo M(i, j) il massimo peso di una A-lista per A di dimensionei× j. La ricorrenza e

M(i, j) = max

{M(i− 1, j) + aij se prendo aij

M(i, j − 1) se non prendo aij.

12

M(1, j) = max1≤h≤j

a1h M(i, 1) =i∑

t=1

at1

La soluzione si ha calcolando M(n,m).

Esercizio 7

Sia data la sequenza citt1, . . . , cittn di citta che devono essere attraversatetutte e nell’ordine della sequenza. In ogni citta citti, si deve pagare unatassa ti. In accordo al bit ei, si riceve o meno un bonus per l’esenzione dalpagamento di tasse successive. Ogni esenzione puo essere usata una solavolta. Dati ti e ei per ogni citti, descrivere la ricorrenza per determinare latassa totale minima che un viaggiatore deve pagare per attraversare tutte len citta.

Possibile soluzione. 1. Il viaggiatore attraversa citt1, . . . , cittn pagandouna tassa minima se e solo se considerando citt2, . . . , cittn ha pagato tassaminima, altrimenti si contraddice l’ipotesi di ottimalita.

2. Si ha bisogno di un paramentro per memorizzare la citta in cui ci sitrova e del numero dei bonus per esenzioni a disposizione. Definiamo alloraM(i, j) = la minima tassa per il tragitto da citti, . . . , cittn, avendo percorsotutte le citta citti, . . . , cittn con j bonus per esenzioni a disposizione. Se nellacitta citti non c’e’ esenzione, allora posso decidere di pagare la tassa o di nonpagarla sfruttando un bonus; se c’ e bouns, posso decidere di non usarlo equindi di pagare, oppure di usarlo (immediatamente). Effettuero il minimotra queste 4 possibilita. La ricorrenza e

M(i, j) = min

M(i + 1, j) + ti se ei = 0 pagoM(i + 1, j − 1) se ei = 0 non pagoM(i + 1, j + 1) + ti se ei = 1 pagoM(i + 1, j) se ei = 1 non pago .

Inoltre

M(n, j) = 0 M(n, 0) = tn

La soluzione e M(1, 0).

13

Esercizio 8

Date due sequenze u1, . . . , un e d1, . . . , dm ed una matrice di compatibilian×m formata da interi positivi C = [ci,j], una lista di k coppie((ui1, dj1), (ui2, dj2), . . . , (uik , djk)) e detta non-incrociante se i1 < i2 < · · · <ik e j1 < j2 < . . . < jk. La compatibilia di tale lista e la somma dellecompatibilita delle coppie che la compongono, cioe ci1,j1 + ci2,j2 + · · ·+ cik,jk.

Descrivere ed analizzare un algoritmo che, data in input una matrice dicompatibilia n × m formata da interi positivi C = [ci,j], ed un intero k,determini, in tempo polinomiale, la massima compatibilita di una lista di kcoppie non-incrocianti.

Esempio. Si consideri la matrice C = [ci,j], tale che ci,j = (i + j)2,i = 1, 2, 3, j = 1, 2, 3, 4 e sia k = 2. Alcune liste di 2 coppie non-incrociantisono le seguenti: ((u1, d2), (u3, d3)) la cui compatibilita e 9 + 36 = 45,((u2, d2), (u3, d4)), la cui compatibilita e 16 + 49 = 65, ((u1, d1), (u2, d4)),la cui compatibilita e 4 + 36 = 40. Alcune liste di coppie che non soddisfanola proprieta di essere non-incrocianti sono le seguenti:

((u2, d2), (u3, d1)), ((u1, d4), (u3, d3)), ((u3, d2), (u2, d3))

.

Possibile soluzione. 1. Supponiamo che ((ui1, dj1), (ui1, dj2), . . . , (uik , djk))sia una lista di k coppie non-incrocianti che massimizzi i costi, ossia una so-luzione ottima. Se consideriamo k − 1 coppie, cioe tagliamo l’ultima coppia,otteniamo una soluzione ottima per k − 1 coppie non incrocianti per le se-quenze u1, . . . , ui(k−1) e d1, . . . , dj(k−1), dove gli ultimi possono essere presicome la (k − 1)−sima coppia oppure no. Infatti se questa non fosse ottima,potrei trovarne un’altra migliore tale che aggiungendo l’ultima coppia avreisoluzione migliore di quella ottima per il problema originario (assurdo).

2. Sia M(i, j, t) = massimo costo di t coppie non-incrocianti scelte traui, . . . , un e dj, . . . , dm. Scriviamo la ricorrenza

M(i, j, t) = max

M(i + 1, j + 1, t− 1) + c(i, j)M(i, j + 1, t)M(i + 1, j, t).

InoltreM(i, j, 0) = 0M(i, j, t) = −∞, se t > min{n− i + 1,m− j + 1}

14

M(i, j, t) = 0, se i > n oppure j > m

La soluzione e M(1, 1, k). La complessita e O(mnk).

3. Calcoliamo il valore di una soluzione ottima prima con tecnica top-down (ricosiva con memorizzazione).

CoppieNonIncrocianti(n,m,k)for i:=1 to n do

for j:= 1 to m do

for t:= 0 to k do

M(i,j,t)= −∞;

return Lookup(1,1,k).

Lookup(i,j,t)if M(i,j,t) > −∞ then return M(i,j,t);

if ((t=0) or (i>n) or (j>m)) then return 0

else

if t > min{n− i + 1,m− j + 1} then return −∞else begin

q1:=Lookup(i+1,j+1,t-1) + c(i,j);

q2:=Lookup(i,j+1,t);

q3:=Lookup(i+1,j,t);

q:= max{q1, q2, q3};if q>M(i,j,t) then M(i,j,t):=q;

end;

return M(i,j,t).

Scriviamo ora un algoritmo con tecnica bottom-up (iterativa).

CoppieNonIncrocianti(n,m,k);

for i:=n downto 1 do

for j:=m downto to 1 do

for t:=0 to k do

begin if ((t=0) or (i>n) or (j>m)) then M(i,j,t):=0

else if t > min{n− i+1,m−j +1} then return −∞else begin

q1:=Lookup(i+1,j+1,t-1) + c(i,j);

q2:=Lookup(i,j+1,t);

q3:=Lookup(i+1,j,t);

q:= max{q1, q2, q3};

15

if q>M(i,j,t) then M(i,j,t):=q;

end;

end;

return M(1,1,k).

Esercizio 9

Sia G = (V, E) un grafo orientato e aciclico, in cui ogni arco (u, v) ∈ E ha uncosto Cu,v > 0. Il costo misto di un cammino (u0, u1), (u1, u2), . . . , (uk−1, uk)di lunghezza k e

k +k−1∑i=0

(−1)iCui,ui+1

Descrivere una equazione di ricorrenza che, data un grafo G orientato e aci-clico, un insieme di costi {Cu,v} e un vertice w ∈ V , determini il massimocosto misto di un cammino che parte da w.

Possibile soluzione. 1. Supponiamo di avere determinato il massimo costomisto di un cammino che parte da w e sia (w, ui1 , . . . , uin) tale cammino as-sociato alla soluzione ottima. Se consideriamo il cammino (w, ui1 , . . . , uin−1),esso deve rappresentare un cammino di massimo costo misto di lunghezzak − 1, altrimenti perderei l’ottimalita della soluzione (di lunghezza k). In-fatti, se al costo misto ottimale aggiungessi (se k e dispari, sia ha k − 1pari e dunque l’ultimo costo e aggiunto al parziale) il costo dell’ultimo arcoCin−1,in , o lo togliessi (se k e pari, allora k − 1 e dispari e dunque l’ultimocosto e sottratto al parziale), otterrei una soluzione finale migliore di quellafissata (assurdo).

2. Definiamo M(v, 0) = il massimo costo misto del cammino da w a v dilunghezza pari, e M(v, 1) = il massimo costo misto del cammino da w a v dilunghezza dispari. La ricorrenza e:

M(v, 0) = maxu:(u,v)∈E

{M(u, 1)− Cu,v + 1}

M(v, 1) = maxu:(u,v)∈E

{M(u, 0) + Cu,v + 1}

e inoltre M(w, 0) = 0,M(w, 1) = −∞ e M(v, 0) = M(v, 1) = −∞, se nonesiste arco u tale che (u, v) ∈ E. La soluzione al problema sara

16

maxv∈V

{M(v, 0),M(v, 1)}

Esercizio 10

Sia T un albero binario in cui ad ogni arco (u, v) e associato un peso w(u,v) >0. Una (0,1)-colorazione di T associa ad ogni arco uno dei due colori 0 e 1,in modo tale che tutti gli archi, quando in numero di tre, incidenti su unostesso nodo non hanno lo stesso colore. Il peso di una (0,1)-colorazione e lasomma dei pesi degli archi colorati 1.

Descrivere una ricorrenza che dato in input un albero T e i pesi w(u,v) > 0relativi ad ogni arco (u, v) in T, determini il massimo peso di una (0,1)-colorazione.

Possibile soluzione. 1. Una soluzione ottima al problema e una (0,1)-colorazione che massimizza il peso dell’albero radicato in root(T ). Se sietichetta il ramo tra root(T ) e un suo figlio U con 0 (risp. 1), allora entrambii rami tra U e i suoi figli non possono essere etichettati 0 (risp.1). Sceglierola configurazione che massimizza il peso totale e aggiungero il peso dell’ar-co solo se l’etichetto 1. Se il problema richiamato sui figli di root(T ) nondesse soluzione ottima, ne potrei ottenere un’altra migliore per il problemaoriginario.

2. Definiamo M((u, v), c) = il massimo peso di una (0,1)-colorazione delsottoalbero contenente l’arco (u, v) e tutti gli archi del sottoalbero radicatoin v, quando l’arco (u, v) e colorato c, con c ∈ {0, 1}. La ricorrenza e:

M((u, v), 0) = max

M((v, left(v)), 0) + M((v, right(v)), 1)M((v, left(v)), 1) + M((v, right(v)), 1)M((v, left(v)), 1) + M((v, right(v)), 1).

M((u, v), 1) = w(u,v) + max

M((v, left(v)), 0) + M((v, right(v)), 0)M((v, left(v)), 0) + M((v, right(v)), 1)M((v, left(v)), 1) + M((v, right(v)), 0).

Inoltre M((u,NIL), 0) = M((u,NIL), 1) = 0. La soluzione al problema edata da

17

max

M((root(T ), left(root(T ))), 0) + M((root(T ), right(root(T ))), 0)M((root(T ), left(root(T ))), 0) + M((root(T ), right(root(T ))), 1)M((root(T ), left(root(T ))), 1) + M((root(T ), right(root(T ))), 0)M((root(T ), left(root(T ))), 1) + M((root(T ), right(root(T ))), 1).

Esercizio 11

Sia G = (V,E, ω) un grafo con archi E = E1 ∪ E2, con E1 ed E2 disgiunti.Si determino le equazioni di ricorrenza di un algoritmo di programmazionedinamica per il calcolo del costo minimo di un cammino dal vertice i al verticej contenente al piu z archi di E1.

Possibile soluzione. Per la soluzione di questo esercizio, modifichiamol’equazione di ricorrenza dell’algoritmo di Floyd-Warshall, aggiungendo unparametro. Ricordiamo che V = {1, . . . , n} e che il grafo in input ha unafunzione peso ω cosı definita:

wij =

0 se i = j∞ se i 6= j, (i, j) 6∈ Ecij se i 6= j, (i, j) ∈ E.

dove cij e il costo effettivo dell’arco (i, j). Ricordando la ricorrenza di Floyd-Warshall, aggiungiamo un parametro che tenga conto degli archi di E1, su cuiabbiamo un vincolo. Dunque la ricorrenza puo essere cosı descritta. Indicocon D(i, j, k, t) il costo minimo di un cammino da i a j con vertici intermediin {1, . . . , k}, usando al piu t archi di E1.

Infatti ad ogni passo, posso non considerare il vertice intermedio k, equindi riconduco il mio problema a quello del calcolo del costo minimo diun cammino da i a j con vertici intermedi in {1, . . . , k − 1}, usando al piu tarchi di E1. Se, invece, considero il vertice k, spezzo il cammino da i a j indue, uno da i a k, l’altro da k a j usando in entrambi i cammini i vertici in{1, . . . , k− 1}; inoltre, poiche in totale si devono avere al piu t archi di E1, siconsiderano tutte le possibili espressioni di t come somma di due valori, unoper ogni pezzo del cammino. Precisamente:

18

D(i, j, k, t) = min

{D(i, j, k − 1, t) se (a)mint1+t2≤t{D(i, k, k − 1, t1) + D(k, j, k − 1, t2)} se (b)

dove

(a) k non appartiene al cammino da i a j,(b) k appartiene al cammino da i a j.

Se k = 0 e t = 0, allora D(i, j, 0, 0) = ∞, se (i, j) ∈ E1, mentre D(i, j, 0, 0) =ωij, se (i, j) 6∈ E1. Inoltre se k = 0, t > 0, allora D(i, j, 0, t) = ωij.

La soluzione si ottiene con la chiamata a D(i, j, n, z).

Esercizio 12

Si costruisca la ricorrenza di un algoritmo di programmazione dinamica chedetermini, in un grafo colorato con vertici rossi e neri, il cammino minimo dalnodo i al nodo j contenente esattamente k vertici rossi interni al cammino(ossia esclusi i e j).

Possibile soluzione. Per la soluzione di questo esercizio, modifichiamol’equazione di ricorrenza dell’algoritmo di Floyd-Warshall, aggiungendo unparametro. Ricordiamo che V = {1, . . . , n} e che il grafo in input ha unafunzione peso ω cosı definita:

wij =

0 se i = j∞ se i 6= j, (i, j) 6∈ Ecij se i 6= j, (i, j) ∈ E.

dove cij e il costo effettivo dell’arco (i, j). Ricordando la ricorrenza di Floyd-Warshall, aggiungiamo un parametro che tenga conto del vincolo sul numerodi vertici rossi. Dunque la ricorrenza puo essere cosı descritta. Indico conD(i, j, k, l) il costo minimo di un cammino da i a j con vertici intermedi in{1, . . . , l}, contenente esattamente k vertici (interni) rossi.

Infatti ad ogni passo, posso non considerare il vertice intermedio l e quindiriconduco il problema a quello del calcolo del costo minimo di un camminoda i a j con vertici intermedi in {1, . . . , l − 1}, contenente esattamente kvertici interni rossi. Se, invece, considero il vertice l, spezzo il cammino da

19

i a j in due cammini minimi, uno minimo da i a l, l’altro minimo da l a jusando in entrambi i cammini i vertici in {1, . . . , l − 1}; inoltre, poiche intotale si devono avere esattamente k vertici rossi intermedi, si consideranotutte le possibili espressioni di k come somma di due valori k1 e k2, unoper ogni pezzo del cammino. Per capire come questi sono legati al valore kdel problema, bisogna tener conto del fatto che se il vertice intermedio l enero, si ha che k1 + k2 = k, mentre se l e rosso, si ha che k1 + k2 = k − 1,essendo l intermedio e colorato di rosso, ma che non viene contato nei duesottoproblemi (che escludono dal conteggio i vertici estremi di ogni cammino).Precisamente, per ogni l, k > 0:

D(i, j, k, l) = min

D(i, j, k, l − 1) se (1)mink1+k2=k{D(i, l, l − 1, k1) + D(l, j, l − 1, k2))} se (2)mink1+k2+1=k{D(i, l, l − 1, k1) + D(l, j, l − 1, k2))} se (3) .

dove

(1) l non appartiene al cammino,(2) l appartiene al cammino, l nero,(3) l appartiene al cammino, l rosso.

Inoltre, se non ci sono vertici intermedi, ossia sto considerando l’arco (i, j),allora se non richiedo vertici rossi intermedi, allora il valore del sottoproblemasara esattamente il peso dell’arco, mentre se richiedo un certo numero divertici rossi k > 0, allora ho una condizione di errore. Per impedire che talesottoproblema sia allora considerato, attribuisco come valore infinito. Infine,se non devo considerare piu alcun vertice intermedio rosso, avro condizionedi errore se l intermedio e rosso, perche tale situazione non deve essere scelta.Allora,

D(i, j, k, 0) =

{wij se k = 0∞ se k > 0.

D(i, j, 0, l) =

D(i, j, 0, l − 1) se (1)D(i, l, 0, l − 1) + D(l, j, 0, l − 1)) se (2)∞ se (3) .

La soluzione si ottiene con la chiamata a D(i, j, k, n).

20

Esercizio 13

Si costruisca la ricorrenza di un algoritmo di programmazione dinamica chedetermini, in un grafo colorato con vertici rossi e neri, il cammino minimodal nodo i al nodo j contenente esattamente k vertici rossi inclusi i e j.

Possibile soluzione. Tale esercizio e una delle possibili variazione dell’eser-cizio 11. Infatti, indichiamo con D(i, j, k, l) il costo minimo di un camminoda i a j con vertici intermedi in {1, . . . , l}, contenente esattamente k verticirossi compresi i e j. Allora, seguendo il ragionamento precedente, se il verticeintermedio e nero, allora la ricorrenza resta inalterata, ma se l e rosso, verraconteggiato in entrambi i sottoproblemi che rappresentano i due sottocam-mini in cui il cammino da i a j viene spezzato rispetto a l. Allora, il minimosara fatto su k1 + k2 = k + 1.

Inoltre, la base della ricorsione resta identica per k = 0. Invece, se non cisono vertici intermedi, dunque l = 0, si ha D(i, j, k, 0) = wij se k = 0 e i, jentrambi neri, oppure k = 1 e solo una tra i, j rosso, oppure se k = 2 e i, jentrambi rossi (in altre parole, se k e esattamente il numero di rossi tra i ej).

Invece, D(i, j, k, 0) = ∞ se k > 0 e i, j entrambi neri, oppure k = 0 ok ≥ 2 e solo una tra i, j rosso, oppure se k ≤ 1 e i, j entrambi rossi (in altreparole, se k e diverso dal numero di rossi tra i e j).

Esercizio 14 (Compito del 9.7.2001)

Si costruisca la ricorrenza di un algoritmo di programmazione dinamica chedetermini in un grafo G colorato con vertici rossi e neri se esiste un camminodal nodo x al nodo y contenente al piu k vertici neri interni al cammino.

Possibile soluzione. Sia G = (V,E), dove V = {1, . . . , n} e l’insiemedei vertici V = {1, . . . , n} ognuno colorato rosso o nero ed E e l’insiemedegli archi di G. Indichiamo con D(i, j, t, k) l’espressione booleana associataall’esistenza di un cammino dal vertice i al vertice j passando per i verticiintermedi in {1, . . . , t} ed usando al piu k vertici neri interni al cammino.Dunque D(i, j, t, k) = 1 se esiste cammino da i a j passando per i verticiintermedi in {1, . . . , t} ed usando al piu k vertici neri interni al cammino,altrimenti D(i, j, t, k) = 0.

21

Infatti ad ogni passo, posso considerare il vertice intermedio t. Se t nonappartiene al cammino tra i e j, allora riconduco il problema a quello del-l’esistenza di un cammino da i a j con vertici intermedi in {1, . . . , t − 1}.Se invece t appartiene al cammino tra i e j spezzo il cammino da i a j indue, uno da i a t, l’altro da t a j usando in entrambi i cammini i vertici in{1, . . . , t − 1}; inoltre, poiche in totale si devono avere al piu k vertici neri,se t e nero si considerano tutte le possibili espressioni di k − 1 come sommadi due valori, uno per ogni pezzo del cammino, se invece t e rosso, considerole espressioni di k come somma di due valori. Precisamente, per ogni k > 0,definiamo

D(i, j, t, k) =

D(i, j, t− 1, k) se t 6∈ cammino da i a j,D(i, t, t− 1, k1), D(t, j, t− 1, k2) se t rosso, k1 + k2 ≤ k,D(i, t, t− 1, k1), D(t, j, t− 1, k2) se t nero, k1 + k2 + 1 ≤ k.

dove la parentesi { significa “OR” tra le tre possibilita e la virgola tra le duecondizioni significa “AND”.

Le condizioni di base sono le seguenti. Se t = 0, allora D(i, j, 0, k) = 1,se (i, j) ∈ E, mentre D(i, j, 0, k) = 0, se (i, j) 6∈ E, per ogni k ≥ 0. Infine,D(i, j, t, 0) = D(i, j, t−1, 0) se t non appartiene al cammino da i a j, mentre,per ogni t, D(i, j, t, 0) = 0, se t nero, D(i, j, t, 0) = D(i, j, t− 1, 0), se t rosso.

La soluzione si ottiene con la chiamata a D(x, y, n, k).

22