Loading AI tools
Principe de réaliser, le meilleur choix optimum local, étape par étape, afin d'obtenir un résultat optimum global De Wikipédia, l'encyclopédie libre
Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin 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.
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.
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.
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 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 puis on cherche la position d'insertion et de cycle qui minimise l'augmentation totale des coûts :
Par exemple, l'algorithme suivant propose une coloration qui sera valide, mais pas forcément optimale, et ce n'est donc qu'une heuristique. Le problème de coloration de graphe est NP-complet, et pour l'instant pour traiter le cas général, il n'existe que des heuristiques ou des approximations polynomiales, ou des algorithmes polynomiaux dans certains cas particuliers.
Glouton :
Entrée : liste ordonnée V des n sommets d'un graphe G
liste ordonnée C de couleurs
Pour i allant 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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
