Algoritmi e Strutture Dati II

Esercizi 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 pi`
u lunga sottosequenza monotona (crescente) di una sequenza di n numeri interi.
Per esempio, sia X = 2, 4, 7, 6, 11, 13, 21, 14, 1. Allora la pi`
u lunga sottosequenza 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 per
i {1, 2, . . . , n}, sia c[i] la lunghezza della pi`
u lunga sequenza crescente di
Xi che termina con xi (cio`e che contiene effettivamente xi ).
Il motivo per cui imponiamo che lelemento xi appartenga effettivamente
alla sottosoluzione ottima relativa alla sottosequenza Xi `e che quando andiamo a considerare un elemento xj con j > i, per sapere se tale elemento pu`o
far parte della sottosoluzione ottima relativa alla sottosequenza Xj dobbiamo verificare che la condizione xi < xj sia verificata; questo chiaramente lo
possiamo fare solo se sappiamo qual `e lultimo elemento della sottosequenza
crescente pi`
u lunga contenuta in Xi . Dovendo quindi memorizzare da qualche parte questa informazione, la cosa migliore `e quella di incorporarla (come
abbiamo fatto sopra) nel valore di c[i]. Daltra parte, osserviamo che se lelemento xi non appartenesse alla pi`
u lunga sottosequenza crescente contenuta
in Xi vorrebbe dire che esiste un elemento xk , con k < i, che termina tale
sequenza. Ma allora tale sequenza sarebbe anche la pi`
u lunga sottosequenza
crescente contenuta in Xk ; quindi, tanto vale definire il valore di c[i] come
abbiamo fatto sopra.
Ricaviamo ora unequazione di ricorrenza che ci consenta di calcolare il
` facile vedere che vale c[1] = 1.
valore di c[i] per ogni i {1, 2, . . . , n}. E
Infatti, le sottosequenze possibili di X1 (che `e formata solamente da x1 ) sono
due: quella che contiene x1 e quella che non lo contiene. Entrambe sono
1

crescenti, e hanno rispettivamente lunghezza 1 e 0. Quindi la pi`

u lunga
sottosequenza crescente di X1 ha lunghezza 1, e pertanto poniamo c[1] = 1.
Sia ora i > 1, e supponiamo di aver gi`a calcolato i valori di c[1], c[2], . . .,
c[i 1]. Poiche le sottosequenze di X1 , X2 , . . . , Xi1 possono essere tutte
considerate sottosequenze di Xi1 , abbiamo che i valori c[1], c[2], . . . , c[i 1]
rappresentano le lunghezze delle pi`
u lunghe sottosequenze crescenti di Xi1
che terminano, rispettivamente, con x1 , x2 , . . . , xi1 . Tra queste ci saranno
alcune sottosequenze alle quali possiamo attaccare xi e altre alle quali lelemento xi non pu`o essere attaccato. Se prendiamo la pi`
u lunga sottosequenza
alla quale possiamo attaccare xi , e aggiungiamo xi , otteniamo la pi`
u lunga
sottosequenza crescente di Xi che termina con xi . La lunghezza di tale sottosequenza sar`a uguale a 1 pi`
u la lunghezza della sottosequenza alla quale
abbiamo attaccato xi . Pertanto il valore di c[i] `e dato da:
(
1 + max{c[j] | 1 j < i, xj < xi } se i > 1
c[i] =
1
se i = 1
Poiche pu`o accadere che linsieme {c[j] | 1 j < i, xj < xi } sia vuoto
(il che corrisponde al fatto che lelemento xi `e minore di tutti gli elementi
precedenti, e quindi non pu`o essere attaccato a nessuna delle sottosequenze di
Xi1 ), assumiamo per definizione che sia max = 0, cos` che il corrispondente
valore di c[i] sia uguale a 1.
Una volta calcolati i valori c[1], c[2], . . . , c[n], la soluzione al problema
proposto `e data da:
max c[i]
1in

che `e facilmente ricavabile da un semplice ciclo for che scandisce il vettore

c[1..n] alla ricerca del massimo elemento.
Lalgoritmo che calcola i valori c[1], c[2], . . . c[n] `e facilmente ricavabile
dallequazione di ricorrenza, ed `e il seguente:
Max-Growing-Sequence
c[1] 1
for i 2 to n do
max 0
for j 1 to i 1 do
if (xj < xi ) and (c[j] > max)
then max c[j]
2

endif
endfor
c[i] 1 + max
endfor
return c
` facile verificare che la complessit`a in tempo dellalgoritmo proposto `e
E
O(n2 ), mentre lo spazio richiesto `e quello necessario per memorizzare il vettore 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, larghezza
e altezza della scatola. La scatola Bi pu`o essere inserita nella scatola Bj se e
solo se ai < aj , bi < bj e ci < cj ; in particolare, le scatole non possono essere
ruotate. Per brevit`a indichiamo con Bi Bj il fatto che la scatola Bi pu`o
essere inserita nella scatola Bj .
Descrivere un algoritmo efficiente per determinare il massimo valore di k
tale che esiste una sequenza Bi1 , . . . , Bik che soddisfa le condizioni:
Bi1 Bi2 Bik
e
i1 < i2 < < ik
Analizzare la complessit`a dellalgoritmo proposto.
Soluzione. Nonostante questo esercizio sembri pi`
u complicato di quello
precedente, il problema proposto `e isomorfo a quello trattato nellesercizio
precedente. Si tratta infatti di trovare la pi`
u lunga sottosequenza crescente
di scatole contenuta nella sequenza B1 , . . . , Bn . La tecnica di soluzione di
questo problema `e identica a quella adottata nellesercizio precedente, dove
al posto di verificare se due interi xj e xi sono tali che xj < xi andiamo a
verificare se due scatole Bj e Bi sono tali che Bj Bi , ovvero se aj < ai ,
bj < b i e cj < c i .
Sia allora z[1..n] un vettore di n componenti (non lo chiamiamo c, come
abbiamo fatto nellesercizio precedente, per non confoderci con le altezze delle
3

scatole). Detta z[i] la lunghezza massima di una sottosequenza crescente ad

elementi in B1 , . . . , Bi che contiene Bi , calcoliamo i valori z[1], z[2], . . . , z[n]
in questo ordine. La soluzione del problema proposto sar`a data dal valore di:
max z[i]

1in

Lequazione di ricorrenza che consente di ricavare il valore di z[i] `e praticamente identica a quella dellesercizio precedente:
(
1 + max{z[j] | 1 j < i, aj < ai , bj < bi , cj < ci } se i > 1
z[i] =
1
se i = 1
dove, come abbiamo osservato nellesercizio precedente, assumiamo che valga
max = 0.
Lalgoritmo che calcola i valori di z[1], z[2], . . . , z[n] `e il seguente:
Max-Boxes-Chain
z[1] 1
for i 2 to n do
max 0
for 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 + max
endfor
return z
` facile verificare che la complessit`a in tempo dellalgoritmo proposto
E
`e O(n2 ), mentre lo spazio richiesto `e quello necessario per memorizzare il
vettore z[1..n], e quindi (n).

Esercizio 3
Scrivere un algoritmo efficiente che, date due sequenze di interi positivi
X = x1 , . . . , xn e Y = y1 , . . . , ym , determini la lunghezza della pi`
u 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} :
i 1 < i 2 < < i k , j1 < j 2 < < j k ,
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 lunghezza
della pi`
u lunga sottosequenza crescente comune a X e a Y `e 3 (corrispondente
a 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 per
gli esercizi precedenti. Come al solito, indichiamo con Xi la sottosequenza
x1 , x2 , . . . , xi di X, e con Yj la sottosequenza y1 , y2 , . . . , yj di Y . I sottoproblemi naturali del problema proposto consistono nel determinare la lunghezza
di 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 soluzione al problema sia valida (cio`e che la LCS di cui calcoliamo la lunghezza
sia crescente) occorre memorizzare da qualche parte il valore dellultimo elemento delle sottosequenze ottime corrispondenti ai sottoproblemi. Conviene
pertanto definire una matrice c[1..n, 1..m], dove il valore di c[i, j] `e la lunghezza di una LCS crescente tra Xi e Yj tale che lultimo elemento della LCS
`e uguale sia a xi che a yj (e quindi, in particolare, xi = yj ).
Ricaviamo lequazione di ricorrenza che consente di determinare il valore
di c[i, j]. Se xi 6= yj , non esiste una LCS crescente tra Xi e Yj che termina
sia con xi che con yj ; pertanto, in questo caso abbiamo c[i, j] = 0. Se invece
xi = yj , occorre cercare la pi`
u lunga tra le LCS crescenti di Xs e Yt , per tutti
i valori di s e t tali che 1 s < i e 1 t < j, che terminano con un valore
minore di xi . Detti s e t i valori di s e t cos` individuati1 , il valore di c[i, j]
sar`a uguale a 1 + c[s, t]. Quindi, lequazione di ricorrenza che consente di
ricavare c[i, j] `e la seguente:
(
0
se xi 6= yj
c[i, j] =
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 valga
max = 0.
1

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

La soluzione del problema proposto sar`a data dal valore di:

c[i, j]
max
1in
1jm
Lalgoritmo che calcola i valori di c[i, j] `e il seguente. Si osservi che i
valori vengono calcolati dalla prima verso lultima riga; allinterno di ogni
riga, 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] 0
else max 0
for s 1 to i 1 do
for t 1 to j 1 do
if xs < xi and c[s, t] > max
then max c[s, t]
endif
endfor
endfor
c[i, j] 1 + max
endif
endfor
endfor
return c
` facile verificare che la complessit`a in tempo dellalgoritmo proposto `e
E
O((nm)2 ), mentre lo spazio richiesto `e quello necessario per memorizzare il
vettore 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, 8
e Y = 12, 1, 3, 17, 8 (sulle intesazioni di righe e colonne, mettiamo direttamente i valori di xi e yj ). In questo caso lottimo lo si trova in posizione c[7, 5],
in generale lo si deve cercare come massimo elemento in tutta la matrice.

1
4
12
3
7
16
8

12
0
0
1
0
0
0
0

1
1
0
0
0
0
0
0

3 17 8
0 0 0
0 0 0
0 0 0
2 0 0
0 0 0
0 0 0
0 0 3

Tabella 1: Matrice c, con le pi

u lunghe LCS crescenti tra xi e yj

Esercizio 4
Si dice che una sequenza di interi x1 , x2 , . . . , xm `e una sequenza zigzag se,
per ogni i {1, 2, . . . , m 1}, vale:
xi < xi+1
xi > xi+1

se i `e dispari
se i `e pari

Ad esempio, 3, 8, 1, 5, 2 `e una sequenza zigzag, mentre 3, 8, 10, 5, 2 non `e

una sequenza zigzag (10 e maggiore di 8).
Descrivere e analizzare un algoritmo che, data una sequenza Y = y1 , y2 , . . . , ym ,
determini la lunghezza della pi`
u lunga sottosequenza zigzag di Y .
Ad esempio, se Y = 3, 4, 8, 5, 6, 2 allora la lunghezza massima `e 5 (corrispondente alla sottosequenza 3, 8, 5, 6, 2, o anche 4, 8, 5, 6, 2).
Soluzione.
1. Data Y = y1 y2 yn , sia x1 xm la pi`
u lunga sottosequenza ZIGZAG di Y , dove xm = yt , con 1 t n (ossia t `e lindice dellultimo
elemento preso effettivamente nella sequenza ZIG-ZAG). Se |X| `e pari, ossia
m `e pari, allora x1 xm1 deve essere la pi`
u lunga sottosequenza ZIG-ZAG
di lunghezza dispari di y1 yk , con k < t e yk < yt . Se cos` non fosse, esisterebbe unaltra sottosequenza di lunghezza dispari, pi`
u lunga di x1 xm1 ,
con ultimo elemento minore di yt tale che aggiungendo yt , otterrei una sottosequenza 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 pi`
u lunga sottosequenza a ZIGZAG di lunghezza pari di y1 yi , che termina con yi . Similmente, definiamo
Z(i, 1) la lunghezza della pi`
u lunga sottosequenza a ZIG-ZAG di lunghezza
7

 importante notare che yi deve

dispari di y1 yi , che termina con yi . E
essere lultimo elemento della sequenza a ZIG-ZAG di y1 yi , altrimenti
non sarebbe possibile verificare la natura a ZIG-ZAG della sequenza stessa.
Allora, si ha

1 + max{Z(k, 1)|1 k < i, yk < yi } se i 2

0
se i = 1 oppure
Z(i, 0) =

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

1 + max{Z(k, 0)|1 k < i, yk > yi } se i 2

1
se i = 1 oppure
Z(i, 1) =

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

La soluzione si ha calcolando
max {Z(i, 0), Z(i, 1)}

1in

3. Di seguito lo pseudocodice che implementa le equazioni di programmazione 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)
Z(1)

0 2 2
1 1 1

2 4 0
3 3 5

Esercizio 5
Siano G1 = (V, E1 ) e G2 = (V, E2 ) due grafi diretti definiti sullo stesso
insieme di vertici V = {v1 , v2 , . . . , vn }, i cui archi sono del tipo (vi , vj ), con
1 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 detto
alternante 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 lequazione di ricorrenza per determinare, dati G1 , G2 , il cammino alternante di costo minimo da v1 a vn .
Possibile soluzione. (a)
1. Supponiamo di aver trovato un cammino tra i vertici (v1 , . . . , vn ), che
minimizza il costo totale e che sia alternante. Lultimo arco pu`o essere di E1
o di E2 . La soluzione ottima sar`a data dal minimo tra il cammino che termina
con un arco di E1 e quello che termina con arco di E2 . Di conseguenza, il
cammino minimo alternante sar`a dato dalla somma del costo del cammino
minimo su (v1 , . . . , vn1 ) che termina con arco di E2 e il costo dellarco di E1
che incide su vn nel primo caso, e viceversa nel secondo caso. Se questa non
fosse ottima per n 1 vertici, potrei trovarne unaltra ottima per n vertici
aggiungendo a questa il costo dellultimo arco (assurdo).
2. Definiamo M (i, 1) = costo minimo di un cammino alternante da v1
a vi , dove lultimo arco considerato `e di E1 e M (i, 2) = costo minimo di
un cammino alternante da v1 a vi , dove lultimo arco considerato `e di E2 .
9

Indicheremo con ck (j, i) il costo dellarco (vj , vi ) nel grafo Gk , per k = 1, 2.

La ricorrenza `e
M (i, 1) = min {M (j, 2) + c1 (j, i)}
1j<i

M (i, 2) = min {M (j, 1) + c2 (j, i)}

1j<i

e inoltre
M (1, 1) = 0,

M (1, 2) = 0

La soluzione si avr`a calcolando il

min{M (n, 1), M (n, 2)}
Nota. Chiaramente si poteva anche definire M (i, k) il costo minimo di cammino alternante da vi a vn dove il primo arco `e in Ek , per k = 1, 2. In tal
caso avremmo avuto
M (i, 1) = min {M (j, 2) + c1 (i, j)}
i<jn

M (i, 2) = min {M (j, 1) + c2 (i, j)}

i<jn

e inoltre
M (n, 1) = 0,

M (n, 2) = 0

La soluzione si avr`a 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. Ad
ogni arco (u, v) E, `e associato un costo wu,v , intero e strettamente positivo. Sia c : E {R, N } una funzione che assegna il colore rosso (R) o nero
(N) agli archi di G.
Scrivere unequazione di ricorrenza per calcolare il costo minimo di un cammino da v1 a vn che non contenga due archi consecutivi dello stesso colore.
10

Nota: lesercizio e simile al precedente. Si tratta di trovare un cammino

alternante in G.
Possibile soluzione.
Si definisca D(k) (i, j, cI , cF ) il costo di un cammino minimo tra un nodo i e
un nodo j in cui tutti i vertici intermedi sono nellinsieme {1, . . . , k}. Sia cI
il colore assegnato al primo arco del cammino, e sia cF il colore assegnato
allultimo arco del cammino da i a j.
Il caso base dellequazione di ricorrenza si ottiene considerando il cammino
che non ha alcun vertice intermedio (quindi k = 0):

wi,j se (i, j) E, cI = cF
(0)
0
se i = j
D (i, j, cI , cF ) =

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 dellultimo arco sono
uguali (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 ce un solo
arco, che puo avere un solo colore).
La ricorrenza e definita come:
(k1)
D
(i, k, cI , cF 1 ) + D(k1) (k, j, cI1 , cF ),
(k)
D (i, j, cI , cF ) = min
D(k1) (i, j, cI , cF )
dove cF 1 6= cI1 .
Questo significa che il peso di un cammino minimo da i a j in cui tutti i vertici
intermedi sono in {1, . . . , k} e dato dal minimo tra il costo di un cammino
minimo da i a k in cui tutti i vertici intermedi sono in {1, . . . , k 1} pi
u il
costo 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

k
c I1

c F1
R

Figura 1: Cammino minimo tra i e j considerato come somma dei cammini

tra 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 la
somma degli elementi che la compongono. Scrivere lequazione di ricorrenza
per determinare, data in input A, il massimo peso di una A-lista.
Possibile soluzione. 1. Una soluzione ottima `e caratterizzata da elementi
di righe successive, ossia prendo un elemento per riga, senza mai prendere un
elemento con indice di colonna inferiore. Ad ogni passo decido se prendere un
elemento, e in tal caso devo spostarmi solo di una riga, oppure non prendere
un elemento, e in tal caso richiamo semplicemente il problema sulla stessa
riga e unaltra colonna. Se (a1j1 , a2j2 , . . . , anjn ), `e una soluzione ottima per A
(di dimensione n m), allora (a1j1 , a2j2 , . . . , an1jn1 ) deve essere soluzione
ottima per A di dimensione (n 1) m; se cos`non fosse, quando aggiungo
lultimo elemento della riga n-sima, otterrei una soluzione per A originaria
migliore di quella ottima (assurdo).
2. Definiamo M (i, j) il massimo peso di una A-lista per A di dimensione
i j. La ricorrenza `e

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

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

12

M (1, j) = max a1h

M (i, 1) =

1hj

i
X

at1

t=1

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

Esercizio 7
Sia data la sequenza citt1 , . . . , cittn di citt`a che devono essere attraversate
tutte e nellordine della sequenza. In ogni citt`a citti , si deve pagare una
tassa ti . In accordo al bit ei , si riceve o meno un bonus per lesenzione dal
pagamento di tasse successive. Ogni esenzione pu`o essere usata una sola
volta. Dati ti e ei per ogni citti , descrivere la ricorrenza per determinare la
tassa totale minima che un viaggiatore deve pagare per attraversare tutte le
n citt`a.
Possibile soluzione. 1. Il viaggiatore attraversa citt1 , . . . , cittn pagando
una tassa minima se e solo se considerando citt2 , . . . , cittn ha pagato tassa
minima, altrimenti si contraddice lipotesi di ottimalit`a.
2. Si ha bisogno di un paramentro per memorizzare la citt`a in cui ci si
trova e del numero dei bonus per esenzioni a disposizione. Definiamo allora
M (i, j) = la minima tassa per il tragitto da citti , . . . , cittn , avendo percorso
tutte le citt`a citti , . . . , cittn con j bonus per esenzioni a disposizione. Se nella
citt`a citti non ce esenzione, allora posso decidere di pagare la tassa o di non
pagarla sfruttando un bonus; se c `e bouns, posso decidere di non usarlo e
quindi di pagare, oppure di usarlo (immediatamente). Effettuer`o il minimo
tra queste 4 possibilit`a. La ricorrenza `e

M (i + 1, j) + ti

M (i + 1, j 1)
M (i, j) = min
M (i + 1, j + 1) + ti

M (i + 1, j)

se
se
se
se

ei
ei
ei
ei

=0
=0
=1
=1

Inoltre
M (n, j) = 0

M (n, 0) = tn

La soluzione `e M (1, 0).

13

pago
non pago
pago
non pago .

Esercizio 8
Date due sequenze u1 , . . . , un e d1 , . . . , dm ed una matrice di compatibili`a
n 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 compatibili`a di tale lista `e la somma delle
compatibilit`a delle coppie che la compongono, cio`e ci1,j1 + ci2,j2 + + cik,jk .
Descrivere ed analizzare un algoritmo che, data in input una matrice di
compatibili`a n m formata da interi positivi C = [ci,j ], ed un intero k,
determini, in tempo polinomiale, la massima compatibilit`a di una lista di k
coppie 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-incrocianti
sono le seguenti: ((u1 , d2 ), (u3 , d3 )) la cui compatibilit`a `e 9 + 36 = 45,
((u2 , d2 ), (u3 , d4 )), la cui compatibilit`a `e 16 + 49 = 65, ((u1 , d1 ), (u2 , d4 )),
la cui compatibilit`a `e 4 + 36 = 40. Alcune liste di coppie che non soddisfano
la propriet`a 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 soluzione ottima. Se consideriamo k 1 coppie, cio`e tagliamo lultima coppia,
otteniamo una soluzione ottima per k 1 coppie non incrocianti per le sequenze u1 , . . . , ui(k1) e d1 , . . . , dj(k1) , dove gli ultimi possono essere presi
come la (k 1)sima coppia oppure no. Infatti se questa non fosse ottima,
potrei trovarne unaltra migliore tale che aggiungendo lultima coppia avrei
soluzione migliore di quella ottima per il problema originario (assurdo).
2. Sia M (i, j, t) = massimo costo di t coppie non-incrocianti scelte tra
ui , . . . , un e dj , . . . , dm . Scriviamo la ricorrenza

M (i + 1, j + 1, t 1) + c(i, j)
M (i, j, t) = max M (i, j + 1, t)

M (i + 1, j, t).
Inoltre
M (i, j, 0) = 0
M (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 complessit`a `e O(mnk).
3. Calcoliamo il valore di una soluzione ottima prima con tecnica topdown (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 un
costo Cu,v > 0. Il costo misto di un cammino (u0 , u1 ), (u1 , u2 ), . . . , (uk1 , uk )
di lunghezza k `e
k+

k1
X

(1)i Cui ,ui+1

i=0

Descrivere una equazione di ricorrenza che, data un grafo G orientato e aciclico, un insieme di costi {Cu,v } e un vertice w V , determini il massimo
costo misto di un cammino che parte da w.
Possibile soluzione. 1. Supponiamo di avere determinato il massimo costo
misto di un cammino che parte da w e sia (w, ui1 , . . . , uin ) tale cammino associato alla soluzione ottima. Se consideriamo il cammino (w, ui1 , . . . , uin1 ),
esso deve rappresentare un cammino di massimo costo misto di lunghezza
k 1, altrimenti perderei lottimalit`a della soluzione (di lunghezza k). Infatti, se al costo misto ottimale aggiungessi (se k `e dispari, sia ha k 1
pari e dunque lultimo costo `e aggiunto al parziale) il costo dellultimo arco
Cin1 ,in , o lo togliessi (se k `e pari, allora k 1 e dispari e dunque lultimo
costo `e sottratto al parziale), otterrei una soluzione finale migliore di quella
fissata (assurdo).
2. Definiamo M (v, 0) = il massimo costo misto del cammino da w a v di
lunghezza pari, e M (v, 1) = il massimo costo misto del cammino da w a v di
lunghezza dispari. La ricorrenza `e:
M (v, 0) = max {M (u, 1) Cu,v + 1}
u:(u,v)E

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

u:(u,v)E

e inoltre M (w, 0) = 0, M (w, 1) = e M (v, 0) = M (v, 1) = , se non

esiste arco u tale che (u, v) E. La soluzione al problema sar`a
16

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

vV

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 uno
stesso nodo non hanno lo stesso colore. Il peso di una (0,1)-colorazione `e la
somma dei pesi degli archi colorati 1.
Descrivere una ricorrenza che dato in input un albero T e i pesi w(u,v) > 0
relativi 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 dellalbero radicato in root(T ). Se si
etichetta il ramo tra root(T ) e un suo figlio U con 0 (risp. 1), allora entrambi
i rami tra U e i suoi figli non possono essere etichettati 0 (risp.1). Sceglier`o
la configurazione che massimizza il peso totale e aggiunger`o il peso dellarco solo se letichetto 1. Se il problema richiamato sui figli di root(T ) non
desse soluzione ottima, ne potrei ottenere unaltra migliore per il problema
originario.
2. Definiamo M ((u, v), c) = il massimo peso di una (0,1)-colorazione del
sottoalbero contenente larco (u, v) e tutti gli archi del sottoalbero radicato
in v, quando larco (u, v) `e colorato c, con c {0, 1}. La ricorrenza `e:

M ((v, lef t(v)), 0) + M ((v, right(v)), 1)

M ((u, v), 0) = max M ((v, lef t(v)), 1) + M ((v, right(v)), 1)

M ((v, lef t(v)), 1) + M ((v, right(v)), 1).

M ((v, lef t(v)), 0) + M ((v, right(v)), 0)

M ((u, v), 1) = w(u,v) + max M ((v, lef t(v)), 0) + M ((v, right(v)), 1)

M ((v, lef t(v)), 1) + M ((v, right(v)), 0).

Inoltre M ((u, N IL), 0) = M ((u, N IL), 1) = 0. La soluzione al problema `e
data da
17


M ((root(T ), lef t(root(T ))), 0) + M ((root(T ), right(root(T ))), 0)

M ((root(T ), lef t(root(T ))), 0) + M ((root(T ), right(root(T ))), 1)

max
M ((root(T ), lef t(root(T ))), 1) + M ((root(T ), right(root(T ))), 0)

M ((root(T ), lef t(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 programmazione
dinamica per il calcolo del costo minimo di un cammino dal vertice i al vertice
j contenente al pi`
u z archi di E1 .
Possibile soluzione. Per la soluzione di questo esercizio, modifichiamo
lequazione di ricorrenza dellalgoritmo di Floyd-Warshall, aggiungendo un
parametro. Ricordiamo che V = {1, . . . , n} e che il grafo in input ha una
funzione peso cos` definita:

0 se i = j
se i 6= j, (i, j) 6 E
wij =

cij se i 6= j, (i, j) E.
dove cij `e il costo effettivo dellarco (i, j). Ricordando la ricorrenza di FloydWarshall, aggiungiamo un parametro che tenga conto degli archi di E1 , su cui
abbiamo un vincolo. Dunque la ricorrenza pu`o essere cos` descritta. Indico
con D(i, j, k, t) il costo minimo di un cammino da i a j con vertici intermedi
in {1, . . . , k}, usando al pi`
u t archi di E1 .
Infatti ad ogni passo, posso non considerare il vertice intermedio k, e
quindi riconduco il mio problema a quello del calcolo del costo minimo di
un cammino da i a j con vertici intermedi in {1, . . . , k 1}, usando al pi`
ut
archi di E1 . Se, invece, considero il vertice k, spezzo il cammino da i a j in
due, uno da i a k, laltro da k a j usando in entrambi i cammini i vertici in
{1, . . . , k 1}; inoltre, poich`e in totale si devono avere al pi`
u t archi di E1 , si
considerano tutte le possibili espressioni di t come somma di due valori, uno
per ogni pezzo del cammino. Precisamente:

18

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

D(i, j, k 1, t)
mint1 +t2 t {D(i, k, k 1, t1 ) + D(k, j, k 1, t2 )}

se (a)
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 che
determini, in un grafo colorato con vertici rossi e neri, il cammino minimo dal
nodo 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, modifichiamo
lequazione di ricorrenza dellalgoritmo di Floyd-Warshall, aggiungendo un
parametro. Ricordiamo che V = {1, . . . , n} e che il grafo in input ha una
funzione peso cos` definita:

0 se i = j
se i 6= j, (i, j) 6 E
wij =

cij se i 6= j, (i, j) E.
dove cij `e il costo effettivo dellarco (i, j). Ricordando la ricorrenza di FloydWarshall, aggiungiamo un parametro che tenga conto del vincolo sul numero
di vertici rossi. Dunque la ricorrenza pu`o essere cos` descritta. Indico con
D(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 quindi
riconduco il problema a quello del calcolo del costo minimo di un cammino
da i a j con vertici intermedi in {1, . . . , l 1}, contenente esattamente k
vertici 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, laltro minimo da l a j

usando in entrambi i cammini i vertici in {1, . . . , l 1}; inoltre, poich`e in
totale si devono avere esattamente k vertici rossi intermedi, si considerano
tutte le possibili espressioni di k come somma di due valori k1 e k2 , uno
per ogni pezzo del cammino. Per capire come questi sono legati al valore k
del problema, bisogna tener conto del fatto che se il vertice intermedio l `e
nero, 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 due
sottoproblemi (che escludono dal conteggio i vertici estremi di ogni cammino).
Precisamente, per ogni l, k > 0:

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

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 larco (i, j),
allora se non richiedo vertici rossi intermedi, allora il valore del sottoproblema
sar`a esattamente il peso dellarco, mentre se richiedo un certo numero di
vertici rossi k > 0, allora ho una condizione di errore. Per impedire che tale
sottoproblema sia allora considerato, attribuisco come valore infinito. Infine,
se non devo considerare pi`
u alcun vertice intermedio rosso, avr`o condizione
di errore se l intermedio `e rosso, perche tale situazione non deve essere scelta.
Allora,

wij se k = 0
D(i, j, k, 0) =
se k > 0.

se (1)
D(i, j, 0, l 1)
D(i, l, 0, l 1) + D(l, j, 0, l 1)) se (2)
D(i, j, 0, l) =

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 che
determini, in un grafo colorato con vertici rossi e neri, il cammino minimo
dal nodo i al nodo j contenente esattamente k vertici rossi inclusi i e j.
Possibile soluzione. Tale esercizio `e una delle possibili variazione dellesercizio 11. Infatti, indichiamo con D(i, j, k, l) il costo minimo di un cammino
da i a j con vertici intermedi in {1, . . . , l}, contenente esattamente k vertici
rossi compresi i e j. Allora, seguendo il ragionamento precedente, se il vertice
intermedio `e nero, allora la ricorrenza resta inalterata, ma se l `e rosso, verr`a
conteggiato in entrambi i sottoproblemi che rappresentano i due sottocammini in cui il cammino da i a j viene spezzato rispetto a l. Allora, il minimo
sar`a fatto su k1 + k2 = k + 1.
Inoltre, la base della ricorsione resta identica per k = 0. Invece, se non ci
sono vertici intermedi, dunque l = 0, si ha D(i, j, k, 0) = wij se k = 0 e i, j
entrambi neri, oppure k = 1 e solo una tra i, j rosso, oppure se k = 2 e i, j
entrambi rossi (in altre parole, se k `e esattamente il numero di rossi tra i e
j).
Invece, D(i, j, k, 0) = se k > 0 e i, j entrambi neri, oppure k = 0 o
k 2 e solo una tra i, j rosso, oppure se k 1 e i, j entrambi rossi (in altre
parole, 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 che
determini in un grafo G colorato con vertici rossi e neri se esiste un cammino
dal nodo x al nodo y contenente al pi`
u k vertici neri interni al cammino.
Possibile soluzione. Sia G = (V, E), dove V = {1, . . . , n} `e linsieme
dei vertici V = {1, . . . , n} ognuno colorato rosso o nero ed E `e linsieme
degli archi di G. Indichiamo con D(i, j, t, k) lespressione booleana associata
allesistenza di un cammino dal vertice i al vertice j passando per i vertici
intermedi in {1, . . . , t} ed usando al pi`
u k vertici neri interni al cammino.
Dunque D(i, j, t, k) = 1 se esiste cammino da i a j passando per i vertici
intermedi in {1, . . . , t} ed usando al pi`
u 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 non

appartiene al cammino tra i e j, allora riconduco il problema a quello dellesistenza 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 in
due, uno da i a t, laltro da t a j usando in entrambi i cammini i vertici in
{1, . . . , t 1}; inoltre, poich`e in totale si devono avere al pi`
u k vertici neri,
se t `e nero si considerano tutte le possibili espressioni di k 1 come somma
di due valori, uno per ogni pezzo del cammino, se invece t `e rosso, considero
le espressioni di k come somma di due valori. Precisamente, per ogni k > 0,
definiamo

se t 6 cammino da i a j,
D(i, j, t 1, k)
D(i, t, t 1, k1 ), D(t, j, t 1, k2 ) se t rosso, k1 + k2 k,
D(i, j, t, 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 possibilit`a e la virgola tra le due
condizioni 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