Algorithmes d'approximation

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:

  • 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

  • Relaxation (approximation) — In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about… …   Wikipedia

  • 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

  • Fouille de flots de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Metaheuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Méta-heuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Métaheuristiques — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

Share the article and excerpts

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