8.2 Mod` eles matriciels
231
8.2.3 Recherche de trajectoires optimales
L’objectif de cette section est de calculer les trajectoires
(X
0,n , X
1,n , . . . , X
n,n ) = arg max
(x0,...,xn)
Γ n (x 0 , . . . , x n )
qui maximisent un crit` ere de performance positif Γ n de la forme
Γ n (x 0 , x 1 , . . . , x n ) = ν 0 (x 0 ) Q 1 (x 0 , x 1 ) . . . Q n (x n−1 , x n )
o` u ν 0 d´ esigne un crit` ere de performance initial sur E 0 , et Q n =
(Q n (x, y)) x∈En−1,y∈En une famille de matrices `
a entr´ ees positives Q n (x, y) >
0. On conviendra par la suite que cette trajectoire optimale est unique.
On notera V n+1 la fonction de performance marginale donn´ ee par
V n+1 (y n+1 ) = max
(x0,...,xn)
Γ n+1 (x 0 , . . . , x n , y n+1 ) et V 0 (x 0 ) = ν 0 (x 0 )
En utilisant la formule de r´ ecurrence
Γ n+1 (x 0 , x 1 , . . . , x n+1 ) = η 0 (x 0 ) Q 1 (x 0 , x 1 ) . . . Q n+1 (x n , x n+1 )
= Γ n (x 0 , x 1 , . . . , x n ) × Q n+1 (x n , x n+1 )
on d´ emontre ais´ ement que V n satisfait l’´ equation de la programmation dynamique directe
V n+1 (y n+1 ) = max
xn
max
(x0,...,xn−1)
Γ n (x 0 , . . . , x n−1 , x n )
× Q n+1 (x n , y n+1 )
= max
xn
(V n (x n ) × Q n+1 (x n , y n+1 ))
La trajectoire optimale est donn´ ee pour tout 0 ≤ p ≤ n par la formule
r´ ecursive `
a rebours
X
p,n+1 = D p
X
p+1,n+1
avec les fonctions D n donn´ ees par la formule suivante
D n (y n+1 ) := arg max
xn
(V n (x n ) × Q n+1 (x n , y n+1 ))
Ce calcul des trajectoires optimales est appel´ e algorithme de Viterbi.