Algorithmes gloutons : cours, méthodes et exercices corrigés

Problèmes d'optimisation, stratégie gloutonne et choix localement optimal, sous-structure optimale, contre-exemples de non-optimalité, rendu de monnaie, sac à dos binaire et fractionnaire, arbre de Huffman, sélection d'activités, file de priorité, preuve par échange, complexités, comparaison avec la programmation dynamique.

16méthodes
33exercices corrigés
3problèmes
22pièges
44figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Ce que tu sauras faire

Beaucoup de problèmes demandent la meilleure solution parmi un nombre énorme de possibilités. Essayer toutes les possibilités est souvent impossible. Un algorithme glouton construit une solution en prenant, à chaque étape, ce qui paraît le meilleur sur le moment, sans jamais revenir en arrière. La méthode est simple et rapide ; elle est parfois exacte, parfois seulement approchée. Tout l'enjeu est de savoir dans quel cas on se trouve.

modéliser un problème d'optimisation : solutions réalisables, objectif, solution optimale ;
expliquer la stratégie gloutonne et analyser la structure d'une solution gloutonne ;
expliquer la propriété de sous-structure optimale sur un exemple simple ;
écrire et dérouler un rendu de monnaie, un sac à dos glouton et une sélection de créneaux ;
montrer à la main, par un contre-exemple, qu'un glouton n'est pas optimal ;
reconnaître le glouton de l'arbre de Huffman et comprendre pourquoi il est exact ;
calculer la complexité d'un glouton, tri préalable compris, au meilleur et au pire cas.

L'essentiel : Vocabulaire Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Définitions

Problème d'optimisation : un ensemble de solutions réalisables, le plus souvent fini, et une fonction objectif à rendre maximale ou minimale.
Solution optimale : solution réalisable dont l'objectif est le meilleur possible.
Algorithme glouton : il construit une solution étape par étape ; à chaque étape, il fait le choix qui paraît le meilleur à cet instant, et il ne le remet jamais en cause.
Exact : renvoie toujours une solution optimale. Heuristique : donne vite une solution réalisable, sans garantie d'optimalité.
Sous-structure optimale : une solution optimale contient des solutions optimales des sous-problèmes qu'elle laisse.

Une solution gloutonne se lit toujours de la même façon : une solution partielle, un choix selon un critère, un sous-problème plus petit.

Une méthode du chapitre Extrait gratuit

Méthode Reconnaître et modéliser un problème d'optimisation

Quand l’utiliser

Un énoncé demande le meilleur, le plus grand nombre, le coût minimal, ou une répartition avec une limite. Toute étude commence par cette fiche, même quand l'énoncé paraît clair.

Rappel de cours

Un problème d'optimisation est donné par ses solutions réalisables, celles qui respectent les contraintes, et par une fonction objectif à rendre maximale ou minimale (cours, section 1.2).

Démarche

Écrire les données, avec leur type en Python.
Écrire les contraintes : ce qui rend une solution réalisable.
Écrire l'objectif, et dire s'il faut le maximiser ou le minimiser.
Dire à quoi ressemble une solution en Python : une liste d'indices, une liste de 0 et de 1.
Estimer le nombre de solutions réalisables : la force brute est-elle possible ?

Rédaction type

« Une solution est une liste S de 0 et de 1, où S[i] vaut 1 si l'objet i est pris. Elle est réalisable si la somme des poids pris ne dépasse pas c. On maximise la somme des valeurs prises. Il y a $2^n$ listes possibles : on ne peut pas les examiner toutes dès que $n$ dépasse quelques dizaines. »

Exemple traité

Des points à éclairer sont placés le long d'une piste, aux abscisses X. Une lampe placée en $x$ éclaire l'intervalle $[x, x + 10]$ . On veut le moins de lampes possible. Données : la liste X de $n$ abscisses. Solution : une liste L de positions de lampes. Contrainte : chaque point de X est dans l'intervalle d'au moins une lampe. Objectif : minimiser len(L). Les positions réelles sont en nombre infini, mais on peut pousser chaque lampe vers la droite jusqu'au premier point qu'elle éclaire sans perdre aucun point : il suffit de placer les lampes sur des points de X, ce qui fait $2^n$ choix.

Erreurs fréquentes

Commencer à coder sans avoir dit ce qu'est une solution.
Confondre la solution (les objets choisis) et la valeur de la solution.
Oublier une contrainte de l'énoncé, comme « chaque objet une seule fois ».

Pour s’entraîner

Exercice 1, problème 3.

Un exercice corrigé Extrait gratuit

Exercice Trois problèmes à modéliser ★☆☆

Pour chacune des trois situations suivantes, on veut écrire le problème d'optimisation avant de chercher à le résoudre.

Situation A. Rendre 38 dirhams avec le moins de pièces possible, avec les valeurs de DH, en quantité illimitée.
Situation B. Charger un camion de 12 quintaux avec des caisses, chacune prise entière ou laissée, pour que la valeur chargée soit la plus grande. Les caisses sont (9, 4), (12, 5), (15, 7) et (20, 9), écrites (valeur, poids).
Situation C. Accorder le plus grand nombre possible de créneaux de la balance de la coopérative, parmi (8, 10), (9, 11) et (10, 12). Une balance ne sert qu'un producteur à la fois.

Pour chaque situation, donner les données, la forme d'une solution, les contraintes, la fonction objectif, et dire s'il faut la minimiser ou la maximiser.
Donner, pour chacune, une solution réalisable, et une proposition qui ne l'est pas, en disant quelle contrainte elle viole.
Pour B et C avec $n$ caisses ou $n$ créneaux, combien la force brute examine-t-elle de candidats ? L'ensemble des solutions réalisables de A est-il fini ?
Donner une solution optimale de chaque situation, en la justifiant par une comparaison complète.

Indications

Méthode 1 : quatre lignes dans cet ordre : données, solution, contraintes, objectif.
Une solution de A est une suite de nombres de pièces ; une solution de B ou de C est un sous-ensemble.
Question 4, situation B : il y a 16 sous-ensembles, et ceux de plus de deux caisses sont trop lourds.

Analyse : comment trouver l’idée

Écris d'abord les quatre lignes de chaque problème : données, solution, contraintes, objectif. Pour un optimum à la main, passe en revue tous les cas, sans te fier à un glouton.

Correction détaillée

Question 1.

	A	B	C
Données	somme 38, valeurs de `DH`	caisses `(valeur, poids)`, charge 12	créneaux `(debut, fin)`
Solution	nombre $x_i$ de pièces de chaque valeur	sous-ensemble de caisses	sous-ensemble de créneaux
Contraintes	$\sum x_i v_i = 38$ , $x_i$ entiers naturels	somme des poids au plus 12	créneaux choisis deux à deux compatibles
Objectif	$\sum x_i$ , à minimiser	somme des valeurs, à maximiser	nombre de créneaux, à maximiser

Question 2. A : 19 pièces de 2 sont une solution réalisable ; [20, 20] n'en est pas une, car sa somme vaut 40 et non 38. B : (9, 4) et (12, 5) pèsent 9, c'est réalisable ; (15, 7) et (20, 9) pèsent 16, plus que 12. C : (8, 10) et (10, 12) sont compatibles, car le premier créneau finit quand le second commence ; (8, 10) et (9, 11) se chevauchent de 9 h à 10 h.

Question 3. Dans B et C, chaque élément est pris ou laissé : la force brute examine $2^n$ sous-ensembles. Dans A, l'ensemble des solutions réalisables est fini, car chaque $x_i$ vaut au plus $38 / v_i$ . Il reste grand, mais il est fini : c'est ce qui rend la force brute possible en principe.

Question 4. A : [20, 10, 5, 2, 1], 5 pièces. Les pièces de 10 et de 20 donnent un multiple de 10, donc les pièces de 1, 2 et 5 doivent faire une somme terminée par 8. Si elles font 8, il en faut au moins 3, et il reste 30, qui demande 2 pièces : 5 en tout. Si elles font 18, 28 ou 38, il en faut au moins 5, 7 ou 9, et le total dépasse 5 pièces. B : deux caisses au plus entrent dans le camion, car les trois plus légères pèsent déjà 16 ; les paires possibles valent 21, 24 et 27, et les caisses seules 20 au plus ; le meilleur choix est (12, 5) et (15, 7), de valeur 27 et de poids 12. C : les trois créneaux ne sont pas compatibles, et (8, 10) et (10, 12) le sont, donc l'optimum vaut 2.

Le programme contrôle l'optimum de B, puis affiche le rendu glouton de A, le même que celui du raisonnement, et la sélection de C.

print(meilleur_sac([(9, 4), (12, 5), (15, 7), (20, 9)], 12))
print(rendu(38, DH))
print(selection([(8, 10), (9, 11), (10, 12)]))

Le programme affiche :

27
[20, 10, 5, 2, 1]
[(8, 10), (10, 12)]

Méthodes à retenir

On ne cherche pas de méthode avant d'avoir écrit les quatre lignes : données, solution, contraintes, objectif. Voir la méthode 1 et le cours, section 1.2.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 16 méthodes, 22 pièges corrigés, la carte mentale, 33 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Une question ? WhatsApp

Plan du cours

1. Problèmes d'optimisation
- 1.1 Charger un camion
- 1.2 Vocabulaire
- 1.3 La force brute
2. La stratégie gloutonne
- 2.1 Le principe
- 2.2 La structure d'une solution gloutonne
- 2.3 Le schéma trier puis parcourir
- 2.4 Trois questions, deux mots
3. Rendre la monnaie
- 3.1 Le modèle
- 3.2 L'idée et sa trace
- 3.3 Le code
- 3.4 Par quotients
- 3.5 Complexité
- 3.6 Les dirhams
4. Quand le glouton se trompe
- 4.1 Un contre-exemple
- 4.2 Ce que prouve un contre-exemple
- 4.3 Comment chercher un contre-exemple
- 4.4 Non optimal, ou échec
- 4.5 Vérifier contre une force brute
5. La propriété de sous-structure optimale
- 5.1 Sur le rendu de monnaie
- 5.2 Elle ne suffit pas
- 5.3 Vers la programmation dynamique
6. Le sac à dos binaire
- 6.1 Le modèle
- 6.2 Trois critères
- 6.3 Le code
- 6.4 Une heuristique
7. Le sac à dos fractionnaire
- 7.1 Le problème
- 7.2 Le glouton et sa figure
- 7.3 Pourquoi ce glouton est exact
- 7.4 Une borne pour le sac binaire
8. La sélection de créneaux
- 8.1 Le modèle
- 8.2 Des critères qui trompent
- 8.3 Finir le plus tôt
- 8.4 Pourquoi cette fois c'est exact
9. L'arbre de Huffman : un glouton exact
- 9.1 Rappel
- 9.2 En quoi c'est un glouton
- 9.3 Le coût d'un code
- 9.4 Pourquoi Huffman donne le code le plus court
10. Quand le meilleur candidat change : la file de priorité
- 10.1 Trier une fois ne suffit plus
- 10.2 Un exemple : le moins de salles possible
- 10.3 Coût
11. Complexité d'un algorithme glouton
- 11.1 Trois postes à compter
- 11.2 Meilleur et pire cas
- 11.3 Tous les gloutons n'ont pas la même complexité
12. Bilan
- 12.1 D'autres gloutons
- 12.2 Choisir sa méthode

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Reconnaître et modéliser un problème d'optimisation
Reconnaître une stratégie gloutonne et l'expliquer en deux phrases
Écrire un rendu de monnaie
Écrire le schéma trier puis parcourir, avec tri d'indices et clé
Écrire un glouton sur une matrice ou un graphe
Prendre le meilleur candidat avec une file de priorité
Dérouler un algorithme glouton en tableau de trace
Comparer plusieurs critères sur un même exemple
Trouver un contre-exemple de non-optimalité
Distinguer non optimal et échec
Vérifier un glouton contre une force brute
Expliquer la sous-structure optimale sur un exemple
Montrer qu'un glouton est optimal par échange
Calculer la complexité d'un glouton, au meilleur et au pire cas
Choisir entre glouton, force brute et programmation dynamique
Construire un arbre de Huffman et calculer $L$

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Trois problèmes à modéliser
Glouton ou non
Dérouler un rendu en dirhams
Écrire le rendu de monnaie
Un dictionnaire des pièces
sort, sorted et None
Quatre systèmes de pièces
Deux contre-exemples
Non optimal ou échec
Trois critères à la main
Un sac fractionnaire à la main
Deux créneaux compatibles
Trois complexités à justifier

Entraînement (15)

Le rendu récursif
Rendre avec les pièces de la caisse
Chercher un contre-exemple par programme
La somme qui demande le plus de pièces
Programmer le sac glouton
Découper une barre
Les cours de soutien d'une journée
Trois critères à écarter
Le plein du camion
Remplir des cageots
Un chemin qui se bloque
Regrouper des lots au moindre coût
Le coût d'un code de Huffman
Sous-structure : où elle sert, où elle ne suffit pas
Une sélection qui coûte trop cher

Approfondissement (5)

Le moins de salles possible
Livraisons par échéance
Pourquoi le glouton rend juste en dirhams
Améliorer par échanges
Le jeu de Röckse : un horizon plus long

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Réduire une image : le chemin vertical glouton
CNC 2025, filières MP et PSI, épreuve d'informatique, partie II « Réduction d'image, algorithme Seam Carving », section A « Chemin vertical dans une matrice », questions 22 à 24, complétée
Colorer les villes d'un réseau routier
CNC 2019, filière PSI, épreuve d'informatique, problème « Réseau routier », partie II « Coloration optimale des villes d'un réseau routier », questions 6 à 8, complétée
Le sac à dos glouton
Mines-Ponts 2025, filières MP, PC et PSI, épreuve d'informatique commune, partie 4 « Résolution approchée par un algorithme glouton », questions 7 à 11

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.