Structures de données - Algorithmes gourmands
Un algorithme est conçu pour parvenir à une solution optimale pour un problème donné. Dans l'approche d'algorithme glouton, les décisions sont prises à partir du domaine de solution donné. En tant qu'être gourmand, la solution la plus proche qui semble fournir une solution optimale est choisie.
Les algorithmes gourmands tentent de trouver une solution optimale localisée, qui peut éventuellement conduire à des solutions optimisées globalement. Cependant, les algorithmes généralement gourmands ne fournissent pas de solutions globalement optimisées.
Compter les pièces
Ce problème consiste à compter jusqu'à une valeur souhaitée en choisissant le moins de pièces possible et l'approche gourmande oblige l'algorithme à choisir la plus grosse pièce possible. Si on nous fournit des pièces de 1, 2, 5 et 10 ₹ et qu'on nous demande de compter 18 ₹, la procédure gourmande sera -
1 - Sélectionnez une pièce de 10 ₹, le nombre restant est de 8
2 - Sélectionnez ensuite une pièce de 5 ₹, le nombre restant est de 3
3 - Sélectionnez ensuite une pièce de 2 ₹, le nombre restant est de 1
4 - Et enfin, la sélection d'une pièce de 1 ₹ résout le problème
Cependant, cela semble fonctionner correctement, pour ce décompte, nous devons choisir seulement 4 pièces. Mais si nous modifions légèrement le problème, la même approche peut ne pas être en mesure de produire le même résultat optimal.
Pour le système monétaire, où nous avons des pièces d'une valeur de 1, 7, 10, compter les pièces d'une valeur de 18 sera absolument optimal, mais pour un compte comme 15, il peut utiliser plus de pièces que nécessaire. Par exemple, l'approche gourmande utilisera 10 + 1 + 1 + 1 + 1 + 1, totalisant 6 pièces. Alors que le même problème pourrait être résolu en utilisant seulement 3 pièces (7 + 7 + 1)
Par conséquent, nous pouvons conclure que l'approche gourmande choisit une solution optimisée immédiate et peut échouer là où l'optimisation globale est une préoccupation majeure.
Exemples
La plupart des algorithmes de mise en réseau utilisent l'approche gourmande. Voici une liste de quelques-uns d'entre eux -
- Problème de vendeur itinérant
- Algorithme d'arbre couvrant minimal de Prim
- Algorithme d'arbre couvrant minimal de Kruskal
- Algorithme d'arbre couvrant minimal de Dijkstra
- Graphique - Coloration de la carte
- Graphique - Couverture de sommet
- Problème de sac à dos
- Problème de planification des travaux
Il existe de nombreux problèmes similaires qui utilisent l'approche gourmande pour trouver une solution optimale.