Algorithme glouton 791997 29538664 2008-05-13T17:33:16Z BotSottile 347421 robot Modifie: [[ko:탐욕 알고리즘]] On appelle '''algorithme glouton''' un [[Algorithmique|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. == Algorithme pour la coloration de graphe == 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 == Exemples == === 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 [[Théorie des graphes|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 minimal. Les algorithmes de [[Algorithme de Prim|Prim]] et de [[Algorithme de Kruskal|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. === Problème du 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 <math>(n-1)</math> 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 <math>j</math> puis on cherche la position d'insertion <math>i</math> et <math>j</math> de cycle qui minimise l'augmentation totale des coûts; Dans la plus lointaine insertion <math>j</math> est le sommet libre le plus loin du cycle au sens des coûts; dans la plus proche insertion <math>j</math> est le plus proche du cycle; enfin dans la meilleure insertion on teste tous les sommets <math>j</math> non encore inserés et on choisit celui qui donne la plus faible augmentation du coût. == Voir aussi == * [[Algorithme de Kruskal]] * [[Algorithme de Prim]] * [[Algorithme de Dijkstra]] * [[Codage de Huffman]] * [[Problème du sac à dos]] * [[Problème du voyageur de commerce]] == Liens extérieurs == * {{fr}} Une implémentation de l'algorithme de coloration en C : http://prolland.free.fr/Cours/Cycle2/Maitrise/GraphsTheory/glouton.txt {{Portail mathématiques}} [[Catégorie:Algorithme d'optimisation]] [[cs:Hladový algoritmus]] [[de:Greedy-Algorithmus]] [[en:Greedy algorithm]] [[es:Algoritmo voraz]] [[fi:Ahne algoritmi]] [[he:אלגוריתם חמדן]] [[hu:Mohó algoritmus]] [[it:Algoritmo greedy]] [[ja:貪欲法]] [[ko:탐욕 알고리즘]] [[no:Grådig algoritme]] [[pl:Algorytm zachłanny]] [[pt:Algoritmo guloso]] [[ru:Жадный алгоритм]] [[sl:Požrešna metoda]] [[sr:Похлепни алгоритам]] [[sv:Girig algoritm]] [[vi:Giải thuật tham lam]] [[zh:贪心法]]