Algorithme gourmand

Dans ce didacticiel, vous apprendrez ce qu'est un algorithme gourmand. Vous trouverez également un exemple d'approche gourmande.

Un algorithme glouton est une approche pour résoudre un problème en sélectionnant la meilleure option disponible pour le moment, sans se soucier du résultat futur qu'elle apporterait. En d'autres termes, les meilleurs choix localement visent à produire les meilleurs résultats au niveau mondial.

Cet algorithme n'est peut-être pas la meilleure option pour tous les problèmes. Cela peut produire des résultats erronés dans certains cas.

Cet algorithme ne revient jamais pour inverser la décision prise. Cet algorithme fonctionne dans une approche descendante.

Le principal avantage de cet algorithme est:

  1. L'algorithme est plus facile à décrire .
  2. Cet algorithme peut être plus performant que les autres algorithmes (mais pas dans tous les cas).

Solution réalisable

Une solution réalisable est celle qui fournit la solution optimale au problème.

Algorithme gourmand

  1. Pour commencer, l'ensemble de solutions (contenant les réponses) est vide.
  2. À chaque étape, un élément est ajouté à l'ensemble de solutions.
  3. Si l'ensemble de solutions est réalisable, l'élément actuel est conservé.
  4. Sinon, l'élément est rejeté et n'est plus jamais considéré.

Exemple - Approche gourmande

 Problème: vous devez modifier un montant en utilisant le plus petit nombre de pièces possible. Montant: 28 $ Pièces disponibles: pièce de 5 $ Pièce de 2 $ Pièce de 1 $

Solution:

  1. Créez un ensemble de solutions vide = ().
  2. pièces = (5, 2, 1)
  3. somme = 0
  4. Pendant que la somme ≠ 28, procédez comme suit.
  5. Sélectionnez une pièce C parmi les pièces dont la somme + C <28.
  6. Si C + somme> 28, ne renvoie aucune solution.
  7. Sinon, somme = somme + C.
  8. Ajoutez C à l'ensemble de solutions.

Jusqu'aux 5 premières itérations, l'ensemble de solutions contient 5 pièces de 5 $. Après cela, nous obtenons 1 pièce de 2 $ et enfin 1 pièce de 1 $.

Applications d'algorithme gourmand

  • Tri par sélection
  • Problème de sac à dos
  • Arbre couvrant minimum
  • Problème de chemin le plus court à source unique
  • Problème de planification des travaux
  • Algorithme d'arbre couvrant minimal de Prim
  • Algorithme d'arbre couvrant minimal de Kruskal
  • Algorithme minimal Spanning Tree de Dijkstra
  • Codage Huffman
  • Algorithme Ford-Fulkerson

Articles intéressants...