DAA - Méthode gourmande

Parmi toutes les approches algorithmiques, l'approche la plus simple et la plus directe est la méthode Greedy. Dans cette approche, la décision est prise sur la base des informations actuellement disponibles sans se soucier de l'effet de la décision actuelle à l'avenir.

Les algorithmes gourmands construisent une solution partie par partie, choisissant la partie suivante de telle manière qu'elle donne un avantage immédiat. Cette approche ne reconsidère jamais les choix faits précédemment. Cette approche est principalement utilisée pour résoudre des problèmes d'optimisation. La méthode gourmande est facile à mettre en œuvre et assez efficace dans la plupart des cas. Par conséquent, nous pouvons dire que l'algorithme Greedy est un paradigme algorithmique basé sur l'heuristique qui suit le choix optimal local à chaque étape dans l'espoir de trouver une solution optimale globale.

Dans de nombreux problèmes, il ne produit pas une solution optimale bien qu'il donne une solution approximative (presque optimale) dans un temps raisonnable.

Composants de l'algorithme gourmand

Les algorithmes gourmands ont les cinq composants suivants -

  • A candidate set - Une solution est créée à partir de cet ensemble.

  • A selection function - Permet de choisir le meilleur candidat à ajouter à la solution.

  • A feasibility function - Utilisé pour déterminer si un candidat peut être utilisé pour contribuer à la solution.

  • An objective function - Utilisé pour attribuer une valeur à une solution ou à une solution partielle.

  • A solution function - Utilisé pour indiquer si une solution complète a été atteinte.

Zones d'application

L'approche gourmande est utilisée pour résoudre de nombreux problèmes, tels que

  • Trouver le chemin le plus court entre deux sommets à l'aide de l'algorithme de Dijkstra.

  • Trouver l'arbre couvrant minimal dans un graphique en utilisant l'algorithme de Prim / Kruskal, etc.

Là où l'approche cupide échoue

Dans de nombreux problèmes, l'algorithme Greedy ne parvient pas à trouver une solution optimale, de plus il peut produire la pire solution. Des problèmes tels que le vendeur itinérant et le sac à dos ne peuvent pas être résolus en utilisant cette approche.