Les chaînes de Markov
267
Phase 2
))]
,
(
)
(
(
)),
,
(
)
(
[
=
)
(
G
D
v
D
V
G
C
v
C
V
Min
G
V
6
=
)
,
(
)
(
=
G
D
v
D
V
Phase 3
))
,
(
)
(
(
)),
,
(
)
(
(
[
=
)
(
H
F
v
F
V
H
E
v
E
V
Min
H
V
)]
,
(
)
(
)),
,
(
)
(
(
)),
,
(
)
(
(
[
=
)
(
I
G
v
G
V
I
F
v
F
V
I
E
v
E
V
Min
I
V
)]
,
(
)
(
(
)),
,
(
)
(
(
[
=
)
(
J
G
v
G
V
J
E
v
E
V
Min
J
V
Phase 4
))]
,
(
)
(
),
,
(
)
(
(
)),
,
(
)
(
(
[
=
)
(
K
J
v
J
V
K
I
v
I
V
K
H
v
H
V
Min
K
V
9
=
)
,
(
)
(
=
K
I
v
I
V
Le chemin optimal a donc pour valeur 9. Pour avoir les sommets de ce chemin, il suffit
de reprendre le processus à l'envers : l'optimum 9 est obtenu par le sommet Le sous
optimum en
est obtenu par le sommet etc. On obtient le chemin
, en trait
doublé sur la figure. Cela étant, quel est l'avantage du principe d'optimalité dans le cas
déterministe? Le problème initial était :
)
,
(
1
1
0
=
t
t
t
T
t
x
x
v
Min
1
1 ... T
x
x
avec
7
=
)
,
(
)
(
=
J
G
v
G
V
7
=
)
,
(
)
(
=
I
E
v
E
V
8
=
)
,
(
)
(
=
H
E
v
E
V
4
=
)
,
(
)
(
=
F
C
v
C
V
5
=
)
,
(
)
(
=
E
C
v
C
V