Chapitre 2 • Notions de complexité
48
d’un algorithme pouvant le résoudre. Nous nous limiterons ici aux conséquences
de cette théorie dans le quotidien du chercheur opérationnel. Le lecteur intéressé
par les aspects théoriques pourra consulter les ouvrages traitant de ce sujet cités
dans la bibliographie.
Dans ce chapitre, nous définirons deux classes importantes de problèmes puis,
à partir de ces deux classes, nous illustrerons les conséquences concrètes des résultats de la théorie de la complexité sur le traitement des problèmes d’optimisation.
Nous verrons qu’il est très souvent difficile de résoudre exactement certains problèmes usuels. Pour cette raison, nous examinerons comment envisager une résolution
approchée de ces problèmes a priori difficiles.
2.2.1 P et NP
Nous ferons ici la distinction entre un problème de décision et un problème d’optimisation. Nous concentrant sur les problèmes de décision, nous définirons formellement
les classes P et NP dont font partie les problèmes les plus couramment rencontrés
par le chercheur opérationnel. Signalons que la notation NP ne signifie pas “Non
Polynomial” mais “Non Déterministe Polynominal” ; la notation NDP aurait été préférable ; mais l’usage prime.
Un problème de décision est constitué d’une donnée et d’une question ne pouvant admettre que deux réponses : « oui » ou « non ». Illustrons cette définition
par quelques exemples. Le problème de la parité a pour donnée un entier n et pour
question : n est-il pair ? La réponse à cette question étant « oui » ou « non », nous
avons affaire à un problème de décision. Le problème de décision du plus court
chemin (la longueur d’un chemin étant le nombre de ses arcs) est défini de la façon
suivante. La donnée est G 5 (X, U)
(1)
un graphe (non valué), a et b deux sommets
de G et B un nombre entier ; la question posée est : « Existe-t-il un chemin d’origine a et d’extrémité b de longueur inférieure à B ? » De manière identique, le
problème du plus long chemin est le suivant : la donnée est G 5 (X, U) un graphe,
a et b deux sommets de G et B un nombre entier ; la question posée est « Existe-t-il
un chemin élémentaire (c’est-à-dire ne passant pas deux fois par un même sommet) d’origine a et d’extrémité b, de longueur supérieure à B ? » Nous donnons
comme dernier exemple le problème hamiltonien où la donnée est un graphe G et
la question est « G admet-il un cycle hamiltonien (c’est-à-dire passant une fois et
une seule par chaque sommet) ? ».
La définition des problèmes de décision étant donnée, nous sommes à même de
définir P la classe des problèmes de décision polynomiaux. La mesure de complexité
considérée pour définir la classe P est la complexité temporelle (ou nombre d’opérations élémentaires) dans le pire des cas, définie plus haut. Un problème de décision
appartient à la classe P, s’il peut être résolu par un algorithme A de complexité O1 n
k
2
où k est une constante et n est la taille de la donnée du problème. Montrons que certains problèmes, définis plus haut, appartiennent à P. Le problème de parité est résolu
(1) G comporte n (5 card X) sommets et m (5 card U) arcs.
48
d’un algorithme pouvant le résoudre. Nous nous limiterons ici aux conséquences
de cette théorie dans le quotidien du chercheur opérationnel. Le lecteur intéressé
par les aspects théoriques pourra consulter les ouvrages traitant de ce sujet cités
dans la bibliographie.
Dans ce chapitre, nous définirons deux classes importantes de problèmes puis,
à partir de ces deux classes, nous illustrerons les conséquences concrètes des résultats de la théorie de la complexité sur le traitement des problèmes d’optimisation.
Nous verrons qu’il est très souvent difficile de résoudre exactement certains problèmes usuels. Pour cette raison, nous examinerons comment envisager une résolution
approchée de ces problèmes a priori difficiles.
2.2.1 P et NP
Nous ferons ici la distinction entre un problème de décision et un problème d’optimisation. Nous concentrant sur les problèmes de décision, nous définirons formellement
les classes P et NP dont font partie les problèmes les plus couramment rencontrés
par le chercheur opérationnel. Signalons que la notation NP ne signifie pas “Non
Polynomial” mais “Non Déterministe Polynominal” ; la notation NDP aurait été préférable ; mais l’usage prime.
Un problème de décision est constitué d’une donnée et d’une question ne pouvant admettre que deux réponses : « oui » ou « non ». Illustrons cette définition
par quelques exemples. Le problème de la parité a pour donnée un entier n et pour
question : n est-il pair ? La réponse à cette question étant « oui » ou « non », nous
avons affaire à un problème de décision. Le problème de décision du plus court
chemin (la longueur d’un chemin étant le nombre de ses arcs) est défini de la façon
suivante. La donnée est G 5 (X, U)
(1)
un graphe (non valué), a et b deux sommets
de G et B un nombre entier ; la question posée est : « Existe-t-il un chemin d’origine a et d’extrémité b de longueur inférieure à B ? » De manière identique, le
problème du plus long chemin est le suivant : la donnée est G 5 (X, U) un graphe,
a et b deux sommets de G et B un nombre entier ; la question posée est « Existe-t-il
un chemin élémentaire (c’est-à-dire ne passant pas deux fois par un même sommet) d’origine a et d’extrémité b, de longueur supérieure à B ? » Nous donnons
comme dernier exemple le problème hamiltonien où la donnée est un graphe G et
la question est « G admet-il un cycle hamiltonien (c’est-à-dire passant une fois et
une seule par chaque sommet) ? ».
La définition des problèmes de décision étant donnée, nous sommes à même de
définir P la classe des problèmes de décision polynomiaux. La mesure de complexité
considérée pour définir la classe P est la complexité temporelle (ou nombre d’opérations élémentaires) dans le pire des cas, définie plus haut. Un problème de décision
appartient à la classe P, s’il peut être résolu par un algorithme A de complexité O1 n
k
2
où k est une constante et n est la taille de la donnée du problème. Montrons que certains problèmes, définis plus haut, appartiennent à P. Le problème de parité est résolu
(1) G comporte n (5 card X) sommets et m (5 card U) arcs.