Chapitre 8 Complexité des problèmes et heuristiques
8.1. RETOUR SUR LA COMPLEXITE DES ALGORITHMES
On a vu plus haut ce qu'on entendait par algorithme polynomial : c'est un algorithme
dont on peut démontrer que le temps de calcul est borné par une fonction polynomiale de
la taille du problème, la taille étant elle-même définie par le nombre de bits nécessaire
pour entrer les données en mémoire (dans un problème de graphe, cette fonction
polynomiale s'exprimera par l'intermédiaire du nombre de sommets
et du nombre
d'arcs ou d'arêtes ).
Les algorithmes de chemin ou d'arbres que nous avons décrits sont polynomiaux. Il n'en
est pas de même pour l'algorithme du simplexe ou, comme on vient de le souligner, pour
la procédure arborescente susceptible de résoudre le problème du voyageur de
commerce. Cela dit, on sait qu'il existe des algorithmes polynomiaux pour résoudre un
programme linéaire ; pour l'instant, il n'existe pas de tels algorithmes pour résoudre le
problème du voyageur de commerce. Cette différence nous conduit à introduire quelques
notions sur la complexité des algorithmes et des problèmes, utiles si l'on veut connaître
quel est l'état de l'art actuel en matière d'algorithmique et pour comprendre la nécessité,
dans beaucoup de cas, d'introduire des méthodes moins satisfaisantes que les algorithmes
d'optimisation, méthodes que nous évoquons dans le chapitre suivant.
a) Problème polynomial
C'est un problème combinatoire pour lequel existe un algorithme polynomial (exemple :
chemin de valeur minimale, arbre de valeur minimale). Nous appellerons la classe des
problèmes polynomiaux.
b) Problèmes d'existence et problèmes d'optimisation
Il est utile de distinguer deux types de problèmes : ceux pour lesquels on cherche une
solution qui satisfasse à des contraintes (exemple : existe-t-il un circuit hamiltonien dans
un graphe orienté donné ? Ou encore : existe-t-il un circuit hamiltonien de valeur totale
inférieure à un nombre donné ? Ou encore : existe-t-il une solution à un programme
linéaire en nombre entier donné ?) Et ceux pour lesquels on cherche la ou les solutions
qui minimisent ou maximisent une certaine fonction (c'est le cas des problèmes que nous
avons abordés : celui du voyageur de commerce exige que non seulement on trouve un
circuit hamiltonien mais que par ailleurs ce circuit soit le plus court possible).
Remarque : on peut dans beaucoup de cas ramener la complexité d'un problème
d'optimisation à celle du problème correspondant d'existence. Ainsi, il est évident que si
on trouvait un algorithme polynomial pour le voyageur de commerce (auquel cas ce
problème lui-même est dit polynomial) alors on aurait un algorithme polynomial pour le
8.1. RETOUR SUR LA COMPLEXITE DES ALGORITHMES
On a vu plus haut ce qu'on entendait par algorithme polynomial : c'est un algorithme
dont on peut démontrer que le temps de calcul est borné par une fonction polynomiale de
la taille du problème, la taille étant elle-même définie par le nombre de bits nécessaire
pour entrer les données en mémoire (dans un problème de graphe, cette fonction
polynomiale s'exprimera par l'intermédiaire du nombre de sommets
et du nombre
d'arcs ou d'arêtes ).
Les algorithmes de chemin ou d'arbres que nous avons décrits sont polynomiaux. Il n'en
est pas de même pour l'algorithme du simplexe ou, comme on vient de le souligner, pour
la procédure arborescente susceptible de résoudre le problème du voyageur de
commerce. Cela dit, on sait qu'il existe des algorithmes polynomiaux pour résoudre un
programme linéaire ; pour l'instant, il n'existe pas de tels algorithmes pour résoudre le
problème du voyageur de commerce. Cette différence nous conduit à introduire quelques
notions sur la complexité des algorithmes et des problèmes, utiles si l'on veut connaître
quel est l'état de l'art actuel en matière d'algorithmique et pour comprendre la nécessité,
dans beaucoup de cas, d'introduire des méthodes moins satisfaisantes que les algorithmes
d'optimisation, méthodes que nous évoquons dans le chapitre suivant.
a) Problème polynomial
C'est un problème combinatoire pour lequel existe un algorithme polynomial (exemple :
chemin de valeur minimale, arbre de valeur minimale). Nous appellerons la classe des
problèmes polynomiaux.
b) Problèmes d'existence et problèmes d'optimisation
Il est utile de distinguer deux types de problèmes : ceux pour lesquels on cherche une
solution qui satisfasse à des contraintes (exemple : existe-t-il un circuit hamiltonien dans
un graphe orienté donné ? Ou encore : existe-t-il un circuit hamiltonien de valeur totale
inférieure à un nombre donné ? Ou encore : existe-t-il une solution à un programme
linéaire en nombre entier donné ?) Et ceux pour lesquels on cherche la ou les solutions
qui minimisent ou maximisent une certaine fonction (c'est le cas des problèmes que nous
avons abordés : celui du voyageur de commerce exige que non seulement on trouve un
circuit hamiltonien mais que par ailleurs ce circuit soit le plus court possible).
Remarque : on peut dans beaucoup de cas ramener la complexité d'un problème
d'optimisation à celle du problème correspondant d'existence. Ainsi, il est évident que si
on trouvait un algorithme polynomial pour le voyageur de commerce (auquel cas ce
problème lui-même est dit polynomial) alors on aurait un algorithme polynomial pour le