122
Recherche opérationnelle
n'ont pas de circuit de valeur négative (s'il existe de tels circuits en effet, il n'existe pas
entre certains sommets de chemin de valeur minimale, puisqu'en empruntant une infinité
de fois de tels circuits, on obtient des valeurs de chemin infiniment négatives).
Une problématique se pose de façon constante sur les algorithmes : c'est celle de
l'estimation de leur temps de calcul. On l'a déjà rencontrée à propos de la programmation
linéaire (chapitre 4) lorsque nous avons introduit les méthodes de point intérieur.
Qu'en est-il de l'algorithme de chemin de valeur minimale que nous venons d'exposer?
D'une façon générale, on définit la complexité d'un algorithme comme un majorant du
nombre d'opérations élémentaires qu'il doit effectuer pour trouver la solution. Par
opération élémentaire, on entend toute opération simple effectuée sur deux nombres,
réels ou entiers, comme la substitution, la comparaison, ou encore les opérations
arithmétiques.
La rapidité de l'algorithme dépend évidemment de la taille du problème (définie grosso
modo comme le nombre de caractères élémentaires qui permettent d'entrer les données
dans un ordinateur et résumées par des caractéristiques simples du problème, comme le
nombre de sommets et d'arcs dans un graphe ou le nombre de contraintes et de variables
dans un programme linéaire) et des données pour les variables utilisées (les valeurs des
arcs par exemple ou les valeurs des coefficients des contraintes et du second membre
pour les PL). On appelle instance cet ensemble de variables. La complexité est une
fonction de la taille, représentant le nombre maximal d'opérations élémentaires
effectuées sur l'ensemble des instances possibles, pour cette taille. En général, cette
fonction est impossible à connaître, mais on peut lui trouver un majorant qui donne des
indications précieuses sur la rapidité de l'algorithme. Si par exemple, on démontre que le
nombre d'opérations en question est borné par une fonction polynomiale de la taille du
problème, alors on dira que l'algorithme est polynomial; dans le cas contraire, il est dit
exponentiel.
L'algorithme de Moore-Dijkstra est polynomial.
En effet, à chaque itération , on doit d'abord trouver le minimum de valeurs. Ceci
peut se faire pour comparaisons. Comme varie de 1 à
, la somme de ces
comparaisons est de l'ordre de (on utilisera la notation O( )).
Ensuite, si l'on appelle
le demi-degré extérieur du sommet trouvé par l'opération
précédente, il faut faire
opérations et comparaisons. On explore en fait, sur
l'ensemble des itérations, l'ensemble des arcs. Cette phase est donc en
Au total, la complexité est de l'ordre
, et on a bien affaire à un algorithme
polynomial.
Cette notion est importante, car il est bien évident que les algorithmes polynomiaux
donnent une meilleure assurance de rapidité de traitement que les algorithmes qui ne le
sont pas. On a déjà donné pour les PL des exemples de temps de traitement rédhibitoires
pour un algorithme exponentiel comme le simplexe, même avec les ordinateurs les plus
performants.
Recherche opérationnelle
n'ont pas de circuit de valeur négative (s'il existe de tels circuits en effet, il n'existe pas
entre certains sommets de chemin de valeur minimale, puisqu'en empruntant une infinité
de fois de tels circuits, on obtient des valeurs de chemin infiniment négatives).
Une problématique se pose de façon constante sur les algorithmes : c'est celle de
l'estimation de leur temps de calcul. On l'a déjà rencontrée à propos de la programmation
linéaire (chapitre 4) lorsque nous avons introduit les méthodes de point intérieur.
Qu'en est-il de l'algorithme de chemin de valeur minimale que nous venons d'exposer?
D'une façon générale, on définit la complexité d'un algorithme comme un majorant du
nombre d'opérations élémentaires qu'il doit effectuer pour trouver la solution. Par
opération élémentaire, on entend toute opération simple effectuée sur deux nombres,
réels ou entiers, comme la substitution, la comparaison, ou encore les opérations
arithmétiques.
La rapidité de l'algorithme dépend évidemment de la taille du problème (définie grosso
modo comme le nombre de caractères élémentaires qui permettent d'entrer les données
dans un ordinateur et résumées par des caractéristiques simples du problème, comme le
nombre de sommets et d'arcs dans un graphe ou le nombre de contraintes et de variables
dans un programme linéaire) et des données pour les variables utilisées (les valeurs des
arcs par exemple ou les valeurs des coefficients des contraintes et du second membre
pour les PL). On appelle instance cet ensemble de variables. La complexité est une
fonction de la taille, représentant le nombre maximal d'opérations élémentaires
effectuées sur l'ensemble des instances possibles, pour cette taille. En général, cette
fonction est impossible à connaître, mais on peut lui trouver un majorant qui donne des
indications précieuses sur la rapidité de l'algorithme. Si par exemple, on démontre que le
nombre d'opérations en question est borné par une fonction polynomiale de la taille du
problème, alors on dira que l'algorithme est polynomial; dans le cas contraire, il est dit
exponentiel.
L'algorithme de Moore-Dijkstra est polynomial.
En effet, à chaque itération , on doit d'abord trouver le minimum de valeurs. Ceci
peut se faire pour comparaisons. Comme varie de 1 à
, la somme de ces
comparaisons est de l'ordre de (on utilisera la notation O( )).
Ensuite, si l'on appelle
le demi-degré extérieur du sommet trouvé par l'opération
précédente, il faut faire
opérations et comparaisons. On explore en fait, sur
l'ensemble des itérations, l'ensemble des arcs. Cette phase est donc en
Au total, la complexité est de l'ordre
, et on a bien affaire à un algorithme
polynomial.
Cette notion est importante, car il est bien évident que les algorithmes polynomiaux
donnent une meilleure assurance de rapidité de traitement que les algorithmes qui ne le
sont pas. On a déjà donné pour les PL des exemples de temps de traitement rédhibitoires
pour un algorithme exponentiel comme le simplexe, même avec les ordinateurs les plus
performants.