Algorithmes d'approximation

Algorithme d'approximation

Un algorithme d'approximation 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.

Donc, pour toute instance d'un problème de minimisation admettant un algorithme d'approximation avec facteur ρ > 1 (i.e. un algorithme ρ-approché), si z * est la valeur de la solution optimale et z la valeur de la solution donnée par l'algorithme d'approximation, on aura z \le \rho z^*. C'est le cas 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.

Pour toute instance d'un problème de maximisation admettant un algorithme d'approximation avec facteur 0 < ρ < 1 (on parle toujours d'algorithme ρ-approché), si z * est la valeur de la solution optimale et z la valeur de la solution donnée par l'algorithme d'approximation, on aura z \ge \rho z^*.

Parmi les problèmes NP-complets certains sont non-approximables, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation. C'est le cas du Voyageur de commerce dans un graphe G = (V,E) avec des poids quelconques (positifs) puisque tout algorithme d'approximation pour ce problème dans le graphe complet KV où les arêtes de E ont une valeur nulle et les autres une valeur infiniment grande 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 Hamitonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).


Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme d%27approximation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithmes d'approximation de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme D'approximation — Un algorithme d approximation 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… …   Wikipédia en Français

  • Algorithme d'approximation — Un algorithme d approximation 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… …   Wikipédia en Français

  • Algorithmes De Remplacement Des Lignes De Cache — Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappé sur un ensemble de lignes de mémoire cache remplie. Il faut donc choisir la ligne de mémoire cache qui sera… …   Wikipédia en Français

  • Algorithmes de remplacement des lignes de cache — Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappée sur un ensemble de lignes de mémoire cache remplie. Il faut donc choisir la ligne de mémoire cache qui sera… …   Wikipédia en Français

  • Complexité des algorithmes — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Nombre D'or —  Pour l’article homonyme, voir Nombre d or (astronomie).  La proportion définie par a et b est dite d extrême et de moyenne raison lorsque a e …   Wikipédia en Français

  • Nombre d'Or —  Pour l’article homonyme, voir Nombre d or (astronomie).  La proportion définie par a et b est dite d extrême et de moyenne raison lorsque a e …   Wikipédia en Français

  • Nombre d'or —  Pour l’article homonyme, voir Nombre d or (astronomie).  La proportion définie par a et b est dite d extrême et de moyenne raison lorsque a est à b ce que a + b est à a, so …   Wikipédia en Français

  • Nombre d’or — Nombre d or  Pour l’article homonyme, voir Nombre d or (astronomie).  La proportion définie par a et b est dite d extrême et de moyenne raison lorsque a e …   Wikipédia en Français

  • Problème de la somme d'un sous-ensemble — Problème de la somme de sous ensembles Le problème de la somme de sous ensembles aussi noté SSP (de l anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”