Algorithme approché

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 Algorithme approché 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

  • Algorithme De Knuth-Morris-Pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme KMP — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

  • Algorithme de Knuth-Pratt-Morris — Algorithme de Knuth Morris Pratt L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside… …   Wikipédia en Français

  • Algorithme de knuth-morris-pratt — L algorithme de Knuth Morris Pratt (souvent abrégé par algorithme KMP) est un algorithme de recherche de sous chaîne, permettant de trouver les occurrences d une chaîne P dans un texte S. Sa particularité réside en un pré traitement de la chaîne …   Wikipédia en Français

  • Algorithme De Boyer-Moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de boyer-moore — L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme 2.1 Pré traitement …   Wikipédia en Français

  • Algorithme de recherche de chaîne de caractères de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

  • Algorithme de recherche de sous-chaîne de Boyer-Moore — Algorithme de Boyer Moore L algorithme de Boyer Moore est un algorithme de recherche de sous chaîne particulièrement efficace. Il a été développé par Bob Boyer et J. Strother Moore en 1977. Sommaire 1 Présentation 2 Fonctionnement de l algorithme …   Wikipédia en Français

Share the article and excerpts

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