266
Recherche opérationnelle
Pour illustrer cet algorithme, nous allons prendre un exemple : soit à chercher le chemin
de valeur minimale entre les sommets et du graphe non orienté suivant : (les valeurs
des arcs sont indiquées)
On vérifie que les sommets sont répartis en cinq niveaux et que l'on se trouve bien
devant un problème relevant de la programmation dynamique déterministe, où l'indice
« temps » a simplement été remplacé par l'indice « niveaux ». On a par exemple si l'on
utilise les notations précédentes :
etc.
={E, F, G}
etc.
etc.
Appliquons alors l'algorithme :
Phase 1
(Les valeurs des sous-politiques optimales
pour chacun des sommets, sont entourées
sur la figure).
A
B
C
D
E
H
F
I
G
J
K
4
2
3
4
3
1
1
5
3
1
1
2
2
2
5
5
4
2
3
4
5
8
9
7
3
5
6
7
4
4
A
B
C
D
E
H
F
I
G
J
K
4
2
3
4
3
1
1
5
3
1
1
2
2
2
5
5
4
2
3
4
4
4