Recherche de chemin optimum


Nous posons tout d'abord les principes fondamentaux :

- notion de chemin optimum, c'est-à-dire de valeur maximale ou minimale ;

- types de problèmes pouvant être posés et limite des algorithmes dédiés ;

- limite à l'existence d'un résultat (circuit "absorbant") ;

- représentation du résultat des calculs (arborescence des chemins de valeurs optimales).


Une première technique présentée est basée sur l'inégalité de Ford. Cette méthode peut être peu performante si les choix ne sont pas faits dans un ordre approprié (que l'on ne connait de toute façon pas nécessairement à l'avance...).

Nous abordons ensuite quelques méthodes classiques, qui pour beaucoup peuvent être vues comme des mises en oeuvres optimisées de l'inégalité de Ford.

Nous abordons donc les algorithmes de :

- Dijkstra,

- Bellman,

- Floyd/Warshall.