Algorithmes gloutons et programmation dynamique

En 30 secondes

• Un algorithme glouton choisit à chaque étape le meilleur choix immédiat, sans jamais revenir en arrière.
• La programmation dynamique résout chaque sous-problème une seule fois, mémorise son résultat, et le réutilise en cas de chevauchement de sous-problèmes.
• Le glouton n'est pas toujours optimal : avec les pièces 1, 3, 4 €, il rend 6 € avec 3 pièces, alors que l'optimal (2 pièces) est 3 € + 3 €.

Ce que tu sauras faire

• Décrire le principe d'un algorithme glouton.
• Décrire le principe de la programmation dynamique.
• Identifier une situation où le choix glouton ne donne pas la solution optimale.

Les mots à connaître

Algorithme glouton

un algorithme qui construit une solution en effectuant, à chaque étape, le choix qui semble le meilleur dans l'immédiat, sans jamais revenir sur les choix déjà faits.

Choix localement optimal

le choix qui donne le meilleur résultat immédiat à une étape donnée, sans tenir compte de son effet sur les étapes suivantes.

Solution optimale

la meilleure solution possible d'un problème au sens du critère fixé, par exemple le plus petit nombre de pièces pour rendre une somme donnée.

Le piège classique

Croire qu'un algorithme glouton donne toujours la solution optimale : ce n'est vrai que pour certains problèmes, comme le rendu de monnaie avec les pièces 1, 2, 5, 10 €, pas pour tout problème.

L'astuce

Glouton = un seul coup d'œil à la fois, jamais de retour en arrière : rapide, mais pas toujours optimal.