Algorithme D'approximation

Algorithme 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 Algorithme 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 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… …   Wikipédia en Français

  • Algorithme De Tracé De Segment De Bresenham — L’algorithme de tracé de segment de Bresenham est un algorithme développé par Bresenham en mai 1962, alors qu’il travaillait dans un laboratoire informatique d’IBM et cherchait à piloter un traceur attaché à une console texte. Cet algorithme a… …   Wikipédia en Français

  • Algorithme de trace de segment de Bresenham — Algorithme de tracé de segment de Bresenham L’algorithme de tracé de segment de Bresenham est un algorithme développé par Bresenham en mai 1962, alors qu’il travaillait dans un laboratoire informatique d’IBM et cherchait à piloter un traceur… …   Wikipédia en Français

  • Algorithme de tracé de segment de bresenham — L’algorithme de tracé de segment de Bresenham est un algorithme développé par Bresenham en mai 1962, alors qu’il travaillait dans un laboratoire informatique d’IBM et cherchait à piloter un traceur attaché à une console texte. Cet algorithme a… …   Wikipédia en Français

  • Algorithme d'Euclide (mathématiques élémentaires) — Algorithme d Euclide L algorithme d Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d Euclide.… …   Wikipédia en Français

  • Algorithme De Remez — En mathématiques, l algorithme de Remez, du nom de son inventeur Evgeny Yakovlevich Remez, vise à construire la meilleure approximation polynomiale d une fonction continue sur un intervalle borné, étant donné le degré maximal du polynôme. Cet… …   Wikipédia en Français

  • Algorithme de remez — En mathématiques, l algorithme de Remez, du nom de son inventeur Evgeny Yakovlevich Remez, vise à construire la meilleure approximation polynomiale d une fonction continue sur un intervalle borné, étant donné le degré maximal du polynôme. Cet… …   Wikipédia en Français

  • Algorithme De Sobel — Exemple de détection de contours avec opérateurs Sobel, ici : G=abs(Gx)+abs(Gy). L’algorithme de Sobel est un opérateur utilisé en traitement d image pour la détection de contours. Il s agit d un des opérateurs les plus simples qui donne… …   Wikipédia en Français

  • Algorithme de sobel — Exemple de détection de contours avec opérateurs Sobel, ici : G=abs(Gx)+abs(Gy). L’algorithme de Sobel est un opérateur utilisé en traitement d image pour la détection de contours. Il s agit d un des opérateurs les plus simples qui donne… …   Wikipédia en Français

Share the article and excerpts

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