Algorithme glouton

Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Dans les cas où l'algorithme ne fournit pas systématiquement la solution optimale, il est appelé une heuristique gloutonne. L'illustration ci-contre montre un cas où ce principe est mis en échec.

En partant du point A et en cherchant à monter selon la plus forte pente, un algorithme glouton trouvera le maximum local "m", mais pas le maximum global "M".


Sommaire

Exemples de problèmes

Rendu de monnaie

Article détaillé : Problème du rendu de monnaie.

Suivant le système de pièces, l'algorithme glouton est optimal ou pas. Dans le système de pièces européen (en centimes : 1, 2, 5, 10, 20, 50, 100, 200), où l'algorithme glouton donne la somme suivante pour 37 : 20+10+5+2, on peut montrer que l'algorithme glouton donne toujours une solution optimale.

Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal.

Arbre couvrant minimal

Le problème consiste, dans un graphe non orienté connexe et valué, à trouver un sous-ensemble d'arêtes, formant un arbre, incluant tous les sommets, tel que la somme des poids de chaque arête soit minimale.

Les algorithmes de Prim et de Kruskal sont tous deux des algorithmes gloutons. Le premier consiste à choisir arbitrairement un sommet et à faire croître un arbre à partir de ce sommet. Le second consiste à faire croître une forêt jusqu'à couverture complète. Chaque augmentation se fait de la manière la plus économique possible.

Voyageur de commerce

Une heuristique gloutonne construit une seule solution, par une suite de décisions définitives sans retour arrière, parmi ces méthodes on cite le plus proche voisin, la plus proche insertion, la plus lointaine insertion et la meilleure insertion.

Dans la méthode du plus proche voisin, on part d'un sommet quelconque et à chacune des (n − 1) itérations on relie le dernier sommet atteint au sommet le plus proche au sens coût, puis on relie finalement le dernier sommet au premier sommet choisi.

Dans les méthodes d'insertion, on part d'un cycle réduit à une boucle au départ, à chaque itération on choisit un sommet libre j puis on cherche la position d'insertion i et j de cycle qui minimise l'augmentation totale des coûts; Dans la plus lointaine insertion j est le sommet libre le plus loin du cycle au sens des coûts; dans la plus proche insertion j est le plus proche du cycle; enfin dans la meilleure insertion on teste tous les sommets j non encore insérés et on choisit celui qui donne la plus faible augmentation du coût.

Coloration de graphe

Par exemple, l'algorithme suivant n'est qu'une heuristique, car le problème de coloration de graphe est NP-complet.

Debut

 Glouton G=(V,E)
 
 Y=V
 
 couleur = 0
 
   Tant que (Y n'est pas vide Faire)
   
      couleur ++
      Z=Y
   
      Tant que Z (n'est pas vide Faire)
    
        Choisir v un sommet de Z
        colorier v par couleur
        Y = Y - v
        Z = Z - v - (les voisins de v)
   
     Fin tant que
  Fin tant que

Fin

Liens internes

Lien externe


Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • Algorithme Glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Algorithme De Kruskal — Arbre couvrant de poids minimum L algorithme de Kruskal est un algorithme de recherche d arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe valué et non orienté. Sommaire …   Wikipédia en Français

  • Algorithme De Prim — Arbre couvrant de poids minimum L algorithme de Prim est un algorithme glouton déterminant un arbre couvrant minimal d un graphe connexe valué et non orienté. C est à dire qu il trouve un sous ensemble d arêtes formant un arbre incluant tous les… …   Wikipédia en Français

  • Algorithme de kruskal — Arbre couvrant de poids minimum L algorithme de Kruskal est un algorithme de recherche d arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe valué et non orienté. Sommaire …   Wikipédia en Français

  • Algorithme de prim — Arbre couvrant de poids minimum L algorithme de Prim est un algorithme glouton déterminant un arbre couvrant minimal d un graphe connexe valué et non orienté. C est à dire qu il trouve un sous ensemble d arêtes formant un arbre incluant tous les… …   Wikipédia en Français

  • Algorithme de recherche best-first — La recherche best first (littéralement : le meilleur en premier) est un algorithme de recherche qui parcourt un graphe en explorant le nœud le plus prometteur selon une règle spécifique. Judea Pearl décrit la recherche best first comme l… …   Wikipédia en Français

  • Algorithme génétique — Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d obtenir une solution approchée à un problème d optimisation, lorsqu il n existe pas de méthode exacte (ou que la solution est inconnue) pour le… …   Wikipédia en Français

  • Algorithme —  Ne pas confondre avec la notion d algorithme en sport Un algorithme est une suite finie et non ambiguë d’opérations ou d instructions permettant de résoudre un problème. Le mot algorithme vient du nom latinisé du mathématicien persan Al… …   Wikipédia en Français

  • Algorithme de Prim — Pour les articles homonymes, voir Prim. Arbre couvrant de poids minimum L algorithme de Prim est un algorithme glouton qui permet de trouver un arbre couvrant …   Wikipédia en Français

  • Algorithme probabiliste — En informatique, un algorithme probabiliste, parfois dit aussi randomisé, est un algorithme dont le déroulement fait appel à des données tirées au hasard. Parmi les algorithmes probabilistes, on distingue généralement ceux dits de Monte Carlo et… …   Wikipédia en Français

Share the article and excerpts

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