Algorithme d'approximation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus precisement, c'est une heuristique garantissant à la qualité de la solution fournie un rapport inférieur (si l'on minimise) à une constante, par-rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver une solution approchée qu'une solution exacte, le problème peut par exemple être NP-complet mais admettre un algorithme d'approximation polynomial. Ainsi dans les situations où l'on cherche une bonne solution mais pas forcement la meilleure, un algorithme d'approximation peut être un bon outil.

Définition[modifier | modifier le code]

Selon la nature du problème (maximisation, minimisation etc.) la définition peut varier, on donne ici la définition classique pour un problème de minimisation avec facteur d'approximation constant.

Pour un problème de minimisation ayant une solution optimale de valeur  z^* , un algorithme d'approximation de facteur  \rho > 1 (i.e. un algorithme  \rho -approché) est un algorithme donnant une solution de valeur  z , avec la garantie que z \le \rho z^*.

Exemple[modifier | modifier le code]

Par exemple pour le problème du transversal minimum puisque tout transversal formé par les sommets incidents aux arêtes d'un couplage maximal pour l'inclusion a une cardinalité inférieure à deux fois l'optimum.

C'est aussi le cas pour le cas particulier du voyageur de commerce où les poids satisfont les inégalités triangulaires car alors, le poids minimum d'un arbre couvrant est toujours inférieur à deux fois l'optimum. En affinant cette approche en utilisant un couplage bien choisi on peut aussi obtenir un facteur d'approximation de 3/2, avec l'algorithme de Christofides.

Schéma d'approximation[modifier | modifier le code]

Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur \epsilon > 0 et calculant une solution approchée avec un facteur  (1+\epsilon) . Si le temps de calcul est polynomial en la taille de l'entrée et en 1/ \epsilon, on parle de schéma d'approximation en temps polynomial (abrégé PTAS en anglais)[1].

Non-approximabilité[modifier | modifier le code]

Parmi les problèmes NP-complets certains sont non approximables, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation sauf si certaines conditions improbables sont vérifiées (par exemple P=NP).

Exemple du voyageur de commerce[modifier | modifier le code]

Le problème du voyageur de commerce dans un graphe  G=(V,E) avec des poids quelconques (positifs) est une problème qui n'admet pas d'algorithme d'approximation. En effet, tout algorithme d'approximation pour ce problème dans le graphe complet  K_V où les arêtes de  E ont une valeur nulle et les autres la valeur 1 fournit une réponse au problème de décision NP-complet de statuer sur l'hamiltonicité d'un graphe (en l'occurrence  G est hamiltonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ 2002, 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9), chap. 35.