Retour au cours

Leçon 48 : Greedy Algorithms : Caractéristiques et Pièges

Algorithmes : De Zéro à Héro (Un Guide pour Débutants)

48. Greedy Algorithms (Algorithmes Gloutons) : Caractéristiques et Pièges

Les algorithmes gloutons construisent une solution pièce par pièce, choisissant toujours la pièce suivante qui offre l'avantage immédiat le plus évident.

Caractéristiques Clés

  1. Structure Optimale (Optimal Substructure) : La solution optimale au problème contient la solution optimale à ses sous-problèmes (similaire à Greedy/D&C).
  2. Propriété du Choix Glouton (Greedy Choice Property) : Une solution globalement optimale peut être atteinte en faisant un choix localement optimal (glouton) à chaque étape.

Pièges : Quand l'approche gloutonne échoue

Bien que simple et rapide, une approche gloutonne ne mène pas toujours à un optimum global. Elle ne fonctionne que si le problème présente la Propriété du Choix Glouton.

  • Exemple : Imaginez un système monétaire avec des dénominations {1, 7, 10}. Si vous devez faire 15 centimes, une approche gloutonne pourrait choisir 10, puis 1, 1, 1, 1, 1 (6 pièces). La solution optimale est 7 + 7 + 1 (3 pièces).

Si le choix glouton est mauvais, il n'y a aucun mécanisme pour revenir en arrière et le corriger.