46
|
|
|
|
46 |
La alinierea şirurilor acbcdb şi cadbd, algoritmul de programare dinamică completează următoarele valori ale V(i,j) de sus în jos şi de la stânga la dreapta, aplicând valorile iniţiale şi formula de recurenţă. (Să ne reamintim exemplul anterior care punctează potrivirile cu +2, şi nepotrivirile şi spaţiile cu –1.). De exemplu, în tabelul care urmează, conţinutul casetei situată pe linia 4 şi coloana 1 se obţine calculând max{-3+2, 0-1, -4-1} = -1.
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
|
a
|
b
|
-6
|
-3
|
-3
|
0
|
3
|
2
|
Valoarea aliniamentului optim este V(n,m), şi este prin urmare conţinutul casetei de pe ultima linie şi ultima coloană. Vedem, astfel, că există un aliniament al şirurilor acbcdb şi cadbd care are valoarea 2, astfel încât aliniamentul propus în primul exemplu având valoarea 1 nu este optimal. Dar cum putem determina aliniamentul optim, şi nu doar valoarea lui?
© Cornel Mironel Niculae, 2003-2008
13-Nov-2009