Algorithmes gloutons

12.1 Introduction et motivation

Le chapitre précédent explorait tout l'espace des choix par retour sur trace — exact, mais souvent exponentiel. À l'opposé, un algorithme glouton ne se pose qu'une question à chaque étape : « quel est le meilleur choix local, ici et maintenant ? » ; il le fait, et ne revient jamais dessus. C'est rapide (un seul parcours, sans exploration), mais ce n'est pas toujours optimal : tout l'art est de reconnaître les problèmes où la stratégie gloutonne donne, malgré sa myopie, la solution optimale.

Ce chapitre présente le principe glouton sur deux problèmes classiques — le rendu de monnaie et la sélection d'activités — puis montre, par un contre-exemple, où le glouton se trompe, ce qui motivera la programmation dynamique du chapitre suivant.

12.2 Le principe glouton