Algorithme glouton

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local. Dans certains cas cette approche permet d'arriver à un optimum global, mais dans le cas général c'est une heuristique. 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.

Principe[modifier | modifier le code]

En algorithmique, et plus précisément en optimisation combinatoire, de nombreux algorithmes fonctionnent en faisant une série d'étapes, avec des choix. Une méthode classique est la programmation dynamique qui permet de tester tous les choix. Cependant les complexités des algorithmes de ce type sont parfois trop grandes et l'on choisit d'autres méthodes. L'une de ces méthodes est de choisir localement la meilleure solution : ce sont les algorithmes gloutons[1].

Exemples de problèmes[modifier | modifier le code]

Rendu de monnaie[modifier | modifier le code]

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 de poids minimal[modifier | modifier le code]

Article détaillé : Arbre couvrant de poids 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 (c'est-à-dire un arbre couvrant), tel que la somme des poids de chaque arête soit minimale (d'où le terme arbre couvrant de poids minimal). L'algorithme de Prim et l'algorithme de Kruskal sont deux des algorithmes gloutons pour le problème[2].

Dans l'algorithme de Prim, on choisit un sommet et l'on fait grandir l'arbre depuis ce sommet de façon gloutonne. Plus précisément, on choisit un sommet arbitraire puis l'on sélectionne l'arête incidente à ce sommet de poids minimal et on l'ajoute à l'arbre et ainsi de suite. Autrement dit on construit l'arbre de manière itérative, on sélectionnant à chaque pas l'arête de poids minimum qui relie un sommet de l'arbre avec un sommet en dehors de l'arbre.

L'algorithme de Kruskal consiste à faire croître une forêt jusqu'à couverture complète. Chaque augmentation se fait de la manière la plus économique possible.

Cet exemple montre qu'il existe parfois plusieurs algorithme glouton pour un même problème.

Coloration de graphe[modifier | modifier le code]

Le problème de coloration consiste à donner des couleurs aux sommets tel que deux sommet aient des couleurs différentes. L'ensemble de couleur est limité. Le problème est NP-complet. L'algorithme glouton suivant, parfois appelé first-fit algorithm[3] est une heuristique pour ce problème.

Entrée : 
liste ordonnée V des n sommets d'un graphe G 
liste ordonnée C de couleurs    
Pour i variant de 1 à n 
 v = V[i]       
 couleur = la première couleur de C non utilisée par les voisins de v   
 colorier(v, couleur)   
Fin pour

Pour un graphe il existe toujours un ordre des sommets qui mène à une bonne solution en utilisant cet algorithme, cependant pour d'autres ordre l'algorithme sera bloqué car toutes les couleurs disponible auront déjà été utilisées, et l'étape la première couleur de C non utilisée par les voisins de v ne pourra pas être effectuée [3].

Matroïdes[modifier | modifier le code]

Les algorithmes gloutons sont reliés au concept de matroïde, dans le sens où, informellement, tout problème algorithmique qui peut être représenté par un matroïde peut être résolu par un algorithme glouton[4]. Une notion proche est celle de greedioide (en).

Approximation[modifier | modifier le code]

Un algorithme glouton peut être une algorithme d'approximation, c'est par exemple le cas pour le problème k-centre.

Notes et références[modifier | modifier le code]

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ , 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9) chap. 16 « Algorithmes gloutons », p. 361.
  2. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill,‎ , 2e éd. [détail de l’édition] (ISBN 0-262-03293-7, 978-0-262-03293-3 et 978-0-262-53196-2), chap. 23 : Minimum Spanning Trees, p. 561-579
  3. a et b « Connected Greedy Colourings », dans LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings,‎ , p. 433-441
  4. Jeremy Kun, « When Greedy Algorithms are Perfect: the Matroid ».

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]