Reconstituirea aliniamentului optim

47

    Soluţia este de a parcurge în sens contrar paşii făcuţi din colţul (n,m), găsind care casetă precedentă este responsabilă de cea curentă. De exemplu, în tabelul ce urmează, la caseta (4,2) se poate ajunge fie din caseta (3,1), fie din caseta (3,2); am notat aceasta prin cele două săgeţi care indică aceste casete. Putem deci urma oricare dintre aceste drumuri pornind din (n,m) către (0,0), obţinând astfel aliniamentul optim.

 

j

0

1

2

3

4

5

i

 

 

c

a

d

b

d

0

 

0

-1

-2

-3

-4

-5

1

a

-1

-1

1

0

-1

-2

2

c

-2

1

0

0

-1

-2

3

b

-3

0

0

-1

2

1

4

c

-4

-1

-1

-1

1

1

5

d

-5

-2

-2

1

0

3

6

b

-6

-3

-3

0

3

2

    Aliniamentele optimale ce corespund acestor drumuri sunt

a

c

b

c

d

b

-

 

–

c

–

a

d

b

d

, 

 

a

c

b

c

d

b

-

 

–

c

a

-

d

b

d

şi

 

–

a

c

b

c

d

b

 

c

a

d

b

–

d

-

.

 

    Fiecare dintre ele are trei coincidenţe, o nepotrivire, şi trei spaţii, având ca valoare 3.(2)+4.(-1)=2, valoarea alinierii optime deja determinată.

Analiza duratei

Teoremă: Algoritmul de programare dinamică calculează un aliniament optim într-un timp  O(n+m).

Demonstraţie: Algoritmul necesită completarea unui tabel (n+1).(m+1). Orice casetă particulară este calculată cu maxim 6 căutări în tabele (3 în V şi 3 în σ), 3 adunări şi un maxim cu trei variabile, adică un timp oarecare c, o constantă. Astfel, complexitatea algoritmului este de cel mult c.(n+1).(m+1). Reconstruirea unui singur aliniament poate fi făcută într-un timp de ordinul O(n+m).

© Cornel Mironel Niculae, 2003-2008

13-Nov-2009