Chapitre 2 • Notions de complexité
52
simplexe, « bon » en pratique, n’est pas polynomial comme le sont des « méthodes
intérieures »).
2.2.4 Approximation et approximabilité des problèmes
NP-difficiles
La résolution exacte des problèmes d’optimisation NP-difficiles n’étant pas envisageable pour des problèmes de taille industrielle, une résolution approchée peut
souvent être satisfaisante pour l’utilisateur. Deux critères sont alors importants à
considérer. Premièrement, l’algorithme fournissant la solution approchée doit être
de faible complexité, donc polynomial. Deuxièmement, une garantie sur la qualité
des solutions obtenues, c’est-à-dire une borne de leur écart par rapport à une solution
optimale, doit être fournie. Nous allons voir dans les deux paragraphes suivants des
solutions ayant pour objectif la satisfaction de ces deux critères.
Les algorithmes polynomiaux avec garantie relative
de performance
Nous allons définir ici la notion d’algorithme approché polynomial avec garantie
relative de performance. Nous donnerons cette définition pour les problèmes de
minimisation. Une définition similaire pourra aisément être établie pour les problèmes de maximisation. Nous notons Ĉ le coût de la solution approchée fournie par
l’algorithme approché et C*,
(1)
le coût minimal des solutions de l’instance traitée.
L’algorithme d’approximation est un algorithme polynomial avec garantie relative
de performance si et seulement si il s’exécute en temps polynomial et si il existe une
constante r > 1 telle que pour toute instance du problème on ait :
C
C*
< r (ou bien :
C*
C
< r pour un problème de maximisation). Il est d’autant meilleur que r est proche
de 1 ; pour un algorithme optimal on a : r = 1.
Avec ces algorithmes, nous serons assurés que, dans le pire des cas, la solution
proposée sera éloignée au plus d’un facteur r de la solution optimale. Ces algorithmes
répondent donc parfaitement à la problématique posée puisqu’ils sont de faible complexité et que l’erreur commise sur le coût de la solution obtenue est toujours bornée
par une constante. Cependant une telle garantie n’est pas toujours aisée à obtenir ;
il est même montré, qu’elle ne peut pas exister pour certains problèmes. Le lecteur
pourra consulter le livre de Hochbaum cité dans la bibliographie pour les résultats
concernant l’approximabilité des problèmes NP-difficiles. Dans le chapitre consacré
au problème du voyageur de commerce et aux méthodes arborescentes, un algorithme approché polynomial avec garantie relative de performance est présenté. De
nombreux autres exemples d’algorithmes approchés, polynomiaux, avec garantie
relative de performance peuvent être trouvés dans la « littérature ».
(1) en pratique difficile, voire impossible à obtenir…
ˆ
ˆ
52
simplexe, « bon » en pratique, n’est pas polynomial comme le sont des « méthodes
intérieures »).
2.2.4 Approximation et approximabilité des problèmes
NP-difficiles
La résolution exacte des problèmes d’optimisation NP-difficiles n’étant pas envisageable pour des problèmes de taille industrielle, une résolution approchée peut
souvent être satisfaisante pour l’utilisateur. Deux critères sont alors importants à
considérer. Premièrement, l’algorithme fournissant la solution approchée doit être
de faible complexité, donc polynomial. Deuxièmement, une garantie sur la qualité
des solutions obtenues, c’est-à-dire une borne de leur écart par rapport à une solution
optimale, doit être fournie. Nous allons voir dans les deux paragraphes suivants des
solutions ayant pour objectif la satisfaction de ces deux critères.
Les algorithmes polynomiaux avec garantie relative
de performance
Nous allons définir ici la notion d’algorithme approché polynomial avec garantie
relative de performance. Nous donnerons cette définition pour les problèmes de
minimisation. Une définition similaire pourra aisément être établie pour les problèmes de maximisation. Nous notons Ĉ le coût de la solution approchée fournie par
l’algorithme approché et C*,
(1)
le coût minimal des solutions de l’instance traitée.
L’algorithme d’approximation est un algorithme polynomial avec garantie relative
de performance si et seulement si il s’exécute en temps polynomial et si il existe une
constante r > 1 telle que pour toute instance du problème on ait :
C
C*
< r (ou bien :
C*
C
< r pour un problème de maximisation). Il est d’autant meilleur que r est proche
de 1 ; pour un algorithme optimal on a : r = 1.
Avec ces algorithmes, nous serons assurés que, dans le pire des cas, la solution
proposée sera éloignée au plus d’un facteur r de la solution optimale. Ces algorithmes
répondent donc parfaitement à la problématique posée puisqu’ils sont de faible complexité et que l’erreur commise sur le coût de la solution obtenue est toujours bornée
par une constante. Cependant une telle garantie n’est pas toujours aisée à obtenir ;
il est même montré, qu’elle ne peut pas exister pour certains problèmes. Le lecteur
pourra consulter le livre de Hochbaum cité dans la bibliographie pour les résultats
concernant l’approximabilité des problèmes NP-difficiles. Dans le chapitre consacré
au problème du voyageur de commerce et aux méthodes arborescentes, un algorithme approché polynomial avec garantie relative de performance est présenté. De
nombreux autres exemples d’algorithmes approchés, polynomiaux, avec garantie
relative de performance peuvent être trouvés dans la « littérature ».
(1) en pratique difficile, voire impossible à obtenir…
ˆ
ˆ