Introduction à l'algorithme gourmand
Une stratégie utilisée pour résoudre les problèmes. L'algorithme gourmand est considéré comme l'une des approches utilisées pour résoudre les problèmes. Cet hérétique de résolution de problèmes va de pair avec un choix qui semble le meilleur à ce moment-là. Cette approche est mieux utilisée pour résoudre les problèmes d'optimisation. Les problèmes d'optimisation peuvent être définis comme des problèmes qui nécessitent des résultats minimum ou maximum. Un algorithme gourmand est une approche la plus simple et la plus directe qui peut être utilisée pour obtenir une solution optimale.
Qu'est-ce que l'algorithme gourmand?
Greedy Algorithm est une stratégie algorithmique utilisée pour faire le meilleur choix optionnel à un stade très réduit tout en produisant finalement une solution optimale à l'échelle mondiale. Cet algorithme sélectionne la meilleure solution possible à ce moment sans tenir compte des conséquences. La méthode gourmande dit que le problème devrait être résolu par étapes où chaque entrée est considérée étant donné que cette entrée est faisable. Comme cette approche ne se concentre que sur un résultat immédiat sans égard pour la situation dans son ensemble, elle est considérée comme gourmande.
Définition du concept de base
Jusqu'à présent, nous savons ce qu'est un algorithme gourmand et pourquoi il est nommé ainsi. Les pointeurs ci-dessous vous feront mieux comprendre l'algorithme gourmand. Il est désormais très clair que l'algorithme gourmand ne fonctionne qu'en cas de problème; néanmoins, cette approche n'est applicable que si nous avons une condition ou une contrainte à ce problème.
Types de problèmes
- Problème de minimisation: trouver une solution à un problème est facile étant donné que toutes les conditions sont remplies. Cependant, lorsque ce problème exige un résultat minimum, il est alors appelé un problème de minimisation.
- Problème de maximisation: un problème qui exige le résultat maximum est connu sous le nom de problème de maximisation.
- Problème d'optimisation: un problème est appelé problème d'optimisation lorsqu'il nécessite des résultats minimum ou maximum.
Types de solutions
- Solution réalisable: Maintenant, lorsqu'un problème survient, nous avons de nombreuses solutions plausibles à ce problème. Pourtant, en tenant compte de la condition posée à ce problème, nous choisissons des solutions qui satisfont la condition donnée. Ces solutions qui nous aident à obtenir des résultats répondant à la condition donnée sont appelées solution réalisable .
- Solution optimale: Une solution est dite optimale lorsqu'elle est déjà réalisable et atteint l'objectif du problème; le meilleur résultat. Cet objectif pourrait être le résultat minimum ou maximum. Le point à noter ici est que tout problème n'aura qu'une seule solution optimale.
L'exemple suivant vous fera comprendre facilement la méthode gourmande. Disons, on veut acheter la meilleure voiture disponible sur le marché. L'une des méthodes pour choisir cette voiture consiste à analyser toutes les voitures du marché. Maintenant, cela prend du temps, pour faciliter la sélection d'une voiture parmi les marques spécifiques dans lesquelles ils sont intéressés à investir. En les catégorisant davantage, on choisirait à nouveau les modèles souhaités en fonction de ses caractéristiques. Par conséquent, l'approche utilisée ici est gourmande car cette solution était la solution optimale pour vous tout en considérant que tous les facteurs vous étaient favorables.
Composants de base d'un algorithme gourmand
Maintenant, lorsque nous avons une meilleure compréhension de ce mécanisme, explorons les composants de base d'un algorithme gourmand qui le distingue des autres processus:
- Ensemble candidat: une réponse est créée à partir de cet ensemble.
- Fonction de sélection: Il sélectionne le meilleur candidat à inclure dans la solution.
- Fonction de faisabilité: cette section calcule si un candidat peut être utilisé pour contribuer à la solution.
- Une fonction objective: il attribue une valeur à une solution complète ou partielle.
- Une fonction de solution: elle est utilisée pour indiquer si une solution appropriée a été trouvée.
Où l'algorithme gourmand fonctionne-t-il le mieux?
L'algorithme gourmand peut être appliqué aux problèmes mentionnés ci-dessous.
- L'approche Greedy peut être utilisée pour trouver le graphique d'arbre couvrant minimal en utilisant l'algorithme de Prim ou de Kruskal
- Trouver le chemin le plus court entre deux sommets est encore un autre problème qui peut être résolu en utilisant un algorithme gourmand. L'application de l'algorithme de Dijkstra avec l'algorithme gourmand vous donnera une solution optimale.
- Codage Huffman
Les avantages
Le plus grand avantage que l'algorithme Greedy a sur les autres est qu'il est facile à implémenter et très efficace dans la plupart des cas.
Désavantages
Greedy Algorithm construit essentiellement une solution partie par partie et choisit la partie suivante de telle manière qu'elle donne immédiatement la meilleure solution au problème actuel. En conséquence, les conséquences de la décision actuelle ne sont ni prises en compte ni préoccupées. Ne reconsidérant jamais les choix pris précédemment, Greedy Algorithm ne parvient pas à produire une solution optimale, bien qu'il donne une solution presque optimale . Problème de sac à dos et problème de voyageur de commerce sont des exemples de problèmes où l'algorithme gourmand ne parvient pas à produire une solution optimale.
- Problème de sac à dos: Le plus communément connu sous le nom de problème de sac à dos, est un problème quotidien rencontré par de nombreuses personnes. Disons, nous avons un ensemble d'articles et chacun a un poids et une valeur (profit) différents à remplir dans un conteneur ou doit être collecté de telle sorte que le poids total soit inférieur ou égal à celui du conteneur tandis que le profit total est maximisé .
Conclusion
L'algorithme gourmand est mieux applicable lorsque l'on a besoin d'une solution en temps réel et que les réponses approximatives sont «assez bonnes». De toute évidence, un algorithme gourmand minimise le temps tout en s'assurant qu'une solution optimale est produite, il est donc plus applicable à utiliser dans une situation où moins de temps est requis. Après avoir lu cet article, on pourrait avoir une bonne idée des algorithmes gourmands. De plus, cet article explique pourquoi il est considéré comme le meilleur framework qui répond à presque tous les défis de programmation et vous aide à décider de la solution la plus optimale à un moment donné.
Cependant, sur le côté rugueux, pour appliquer la théorie de l'algorithme gourmand, il faut travailler plus fort pour connaître les bons problèmes. Bien qu'il s'agisse d'un concept scientifique qui a une logique, il a également une essence de créativité.
Articles recommandés
Cela a été un guide pour ce qui est un algorithme gourmand. Ici, nous avons discuté du concept de base, des composants, des avantages et des inconvénients de l'algorithme gourmand. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus -
- Algorithme de programmation
- Qu'est-ce que Perl?
- Introduction à l'algorithme
- Qu'est-ce que le Sprint Agile?