Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer le principe d’un algorithme glouton et distinguer un choix local d’une solution globale ;
• identifier les candidats, la fonction de sélection, le test de faisabilité et la fonction objectif ;
• construire progressivement une solution sans retour en arrière ;
• reconnaître la propriété du choix glouton et la sous-structure optimale ;
• justifier la correction d’une stratégie par un argument d’échange, une preuve par induction ou une propriété de coupe ;
• appliquer la méthode au rendu de monnaie, à la sélection d’activités, à la planification de tâches et au codage de Huffman ;
• produire des contre-exemples lorsqu’un choix local ne conduit pas à l’optimum ;
• comparer une solution gloutonne avec une solution fondée sur la programmation dynamique ;
• analyser la complexité temporelle et spatiale d’un algorithme glouton.

Prérequis

• tableaux, listes, ensembles et dictionnaires ;
• fonctions, procédures, récursivité et invariants ;
• algorithmes de tri et notion de file de priorité ;
• complexités O(1), O(log n), O(n) et O(n log n) ;
• notions de preuve de correction et de solution optimale.

Organisation indicative

13.1 Principe

Définition générale

Un algorithme glouton construit une solution étape par étape. À chaque étape, il sélectionne le candidat qui optimise un critère local, vérifie que ce candidat peut être ajouté sans rendre la solution invalide, puis poursuit avec les candidats restants.

La méthode est dite « gloutonne » parce qu’elle cherche à obtenir le meilleur gain immédiat, sans examiner toutes les conséquences futures du choix.

Choix local

Le choix local est la décision considérée comme la meilleure à l’étape courante. Il est déterminé par une règle simple : plus petite pièce, plus grande valeur, date de fin la plus proche, fréquence la plus faible, rapport valeur/poids maximal, etc.

Solution construite progressivement

Après chaque sélection, la solution partielle doit rester faisable. Elle est étendue jusqu’à ce qu’aucun candidat ne puisse être ajouté ou jusqu’à ce que l’objectif soit atteint.

Absence de retour en arrière

Contrairement au retour sur trace, un algorithme glouton ne supprime pas un choix précédent pour explorer une autre branche. Cette absence de retour réduit fortement le coût de calcul, mais elle rend la qualité du critère local décisive.

Invariant de construction

Un invariant utile est : « après chaque itération, la solution partielle est faisable et peut encore être complétée ». La faisabilité ne suffit toutefois pas à garantir l’optimalité ; elle garantit seulement que les contraintes ne sont pas violées.

13.2 Conditions d’utilisation

Pourquoi une preuve est nécessaire

Un algorithme glouton peut être très convaincant sur quelques exemples et néanmoins échouer sur une instance particulière. Avant d’affirmer qu’il est optimal, il faut montrer que ses choix locaux sont compatibles avec une solution globale optimale.

Propriété du choix glouton

La propriété du choix glouton affirme qu’il existe au moins une solution optimale commençant par le choix local effectué par l’algorithme. Le premier choix peut donc être fixé sans perdre l’optimalité.

Sous-structure optimale

Après avoir effectué un choix glouton, le problème restant doit être une instance plus petite du même problème. Une solution optimale du problème initial est alors formée du choix effectué et d’une solution optimale du sous-problème résiduel.

Méthodes de preuve de correction

1. Argument d’échange

On part d’une solution optimale quelconque. Si son premier choix diffère du choix glouton, on remplace ce choix par le choix glouton et on montre que la solution reste faisable et ne devient pas moins bonne. On obtient ainsi une solution optimale compatible avec l’algorithme.

2. Preuve par induction

On montre que le choix initial est sûr, puis que le sous-problème possède la même structure. L’hypothèse d’induction garantit que les choix suivants produisent une solution optimale du sous-problème.

3. Méthode « rester en avance »

On compare, étape par étape, la solution gloutonne à une solution optimale. On prouve qu’après chaque étape, la solution gloutonne n’est jamais en retard selon une mesure adaptée.

4. Propriété de coupe

Dans certains problèmes de graphes, une coupe sépare les sommets en deux groupes. On prouve qu’une arête de poids minimal traversant cette coupe est sûre et peut appartenir à un optimum.

Comment chercher un contre-exemple ?

• tester de petites instances permettant une énumération complète des solutions ;
• modifier légèrement les poids, durées ou valeurs pour créer un conflit entre gain immédiat et gain futur ;
• examiner les cas où deux choix locaux sont proches mais conduisent à des sous-problèmes très différents ;
• comparer la solution gloutonne à une recherche exhaustive ou à une programmation dynamique ;
• tester les égalités et les règles de départage.

13.3 Exemples

Exemple 1 — Rendu de monnaie

Le problème consiste à rendre un montant avec le plus petit nombre de pièces. Une stratégie gloutonne naturelle choisit toujours la plus grande pièce ne dépassant pas le montant restant.

Trace avec les pièces {25, 10, 5, 1} et le montant 63

Le résultat contient six pièces. Pour de nombreux systèmes monétaires usuels, la stratégie est optimale. Elle ne l’est cependant pas pour tous les ensembles de pièces.

Complexité

Si l’on utilise des divisions entières pour calculer directement le nombre de pièces de chaque valeur, le coût est O(k), où k est le nombre de types de pièces. Avec une boucle retirant une pièce à la fois, le coût dépend aussi du nombre total de pièces rendues.

Exemple 2 — Sélection d’activités

On dispose d’activités utilisant une même ressource. Chaque activité possède une heure de début et une heure de fin. L’objectif est de sélectionner le plus grand nombre d’activités compatibles.

La stratégie optimale consiste à choisir, parmi les activités compatibles, celle qui se termine le plus tôt. Ce choix laisse le maximum de temps disponible pour les activités suivantes.

Exemple de trace

La sélection obtenue est {A1, A4, A6, A7}.

Esquisse de preuve par échange

1.  Soit G l’activité qui se termine le plus tôt et O la première activité d’une solution optimale.

2.  Comme fin(G) ≤ fin(O), remplacer O par G ne rend aucune activité ultérieure incompatible.

3.  La solution transformée contient autant d’activités et commence par G.

4.  Le problème restant est le même problème sur les activités commençant après fin(G).

5.  En répétant l’argument, la sélection gloutonne est optimale.

Exemple 3 — Planification de tâches

Considérons des tâches de durée unitaire. Chaque tâche possède une échéance et un profit obtenu si elle est exécutée avant ou à son échéance. L’objectif est de maximiser le profit total.

Une stratégie classique trie les tâches par profit décroissant et place chaque tâche dans le créneau libre le plus tardif qui respecte son échéance. Placer tardivement une tâche préserve les créneaux précoces pour les tâches ayant des échéances plus contraintes.

Exemple

Le planning final est [T2, T1, T4] et le profit total vaut 210.

Analyse

Avec une recherche linéaire du créneau libre, le coût est O(n log n + nD), où D est la plus grande échéance. Une structure d’ensembles disjoints permet d’accélérer la recherche du dernier créneau libre.

Exemple 4 — Codage de Huffman simplifié

Le codage de Huffman construit un code binaire préfixe dans lequel les symboles fréquents possèdent des codes courts. La stratégie fusionne répétitivement les deux nœuds de fréquence minimale.

Une file de priorité minimale permet d’extraire rapidement les deux fréquences les plus faibles et de réinsérer leur somme.

Exemple de fusions

Génération des codes

On étiquette conventionnellement les arêtes gauches par 0 et les arêtes droites par 1. Le code d’un symbole est la suite des bits rencontrés de la racine à sa feuille. Aucun code n’est préfixe d’un autre, ce qui garantit un décodage sans séparateur.

Comparaison des quatre exemples

13.4 Limites des algorithmes gloutons

Choix local non optimal

Un choix offrant le meilleur gain immédiat peut empêcher une combinaison future plus avantageuse. La stratégie échoue lorsque les décisions interagissent fortement et qu’un bénéfice local masque une perte globale.

Contre-exemples fondamentaux

Rendu de monnaie non canonique

Pour les pièces {4, 3, 1} et le montant 6, choisir 4 conduit à trois pièces, alors que 3 + 3 en utilise deux.

Sac à dos 0/1

Dans le sac à dos fractionnaire, choisir le meilleur rapport valeur/poids est optimal parce qu’un objet peut être fractionné. Dans le sac à dos 0/1, le même critère peut échouer puisque chaque objet doit être pris entièrement ou rejeté.

Avec une capacité de 50, le glouton par rapport choisit A puis B pour une valeur 160. La solution optimale choisit B et C pour une valeur 220.

Plus proche voisin pour le voyageur de commerce

Choisir systématiquement la ville la plus proche produit rapidement une tournée, mais un choix court au début peut forcer une très longue arête à la fin. La méthode est une heuristique, sans garantie d’optimalité générale.

Comparaison avec la programmation dynamique

Glouton exact ou heuristique ?

Lorsque la correction est démontrée, la méthode gloutonne est un algorithme exact. Lorsqu’aucune preuve n’existe mais que la solution est généralement acceptable, elle devient une heuristique. Il faut alors évaluer expérimentalement la qualité des résultats et, si possible, fournir une borne d’approximation.

Erreurs fréquentes

• confondre faisabilité et optimalité ;
• décrire un critère local ambigu ou dépendant d’un ordre non défini ;
• oublier les égalités et les règles de départage ;
• prouver seulement que l’algorithme termine ;
• généraliser un résultat valable pour une variante à une autre variante ;
• ignorer le coût du tri ou de la file de priorité ;
• utiliser un glouton comme solution exacte sans preuve ni mesure de qualité.

Applications guidées

Application 1 — Concevoir un rendu de monnaie

On dispose des pièces {1, 2, 5, 10, 20, 50}. Concevoir une stratégie gloutonne pour rendre 87, produire la trace et préciser la complexité.

Résultat : 50 + 20 + 10 + 5 + 2, soit cinq pièces. Le parcours des k types de pièces est O(k).

Application 2 — Réserver une salle

Une salle ne peut accueillir qu’une activité à la fois. L’objectif est de maximiser le nombre de réservations acceptées. La règle de fin la plus proche permet de libérer la salle le plus tôt possible.

Application 3 — Compresser un message

À partir des fréquences des caractères d’un message, construire un arbre de Huffman, générer les codes et calculer la longueur totale du message codé.

Application 4 — Ordonner des interventions urgentes

Une file de priorité peut sélectionner la prochaine intervention selon un score local combinant urgence, échéance et ancienneté. Ce système est glouton au sens opérationnel, mais il n’est optimal que si l’objectif et le modèle de tâches correspondent à une variante démontrée.

Travaux dirigés

TD 1 — Identifier les composants d’un glouton

Pour le problème de sélection d’activités, identifier les candidats, le critère de sélection, le test de faisabilité, la fonction objectif et le critère d’arrêt.

TD 2 — Rendu de monnaie canonique

Appliquer la stratégie gloutonne au montant 289 avec les pièces {100, 50, 20, 10, 5, 2, 1}. Donner le rendu et le nombre de pièces.

TD 3 — Construire un contre-exemple

Montrer que le système de pièces {1, 5, 6, 9} n’est pas toujours compatible avec le choix de la plus grande pièce. Chercher un montant inférieur ou égal à 15.

TD 4 — Sélection d’activités

Sélectionner un nombre maximal d’activités parmi : A(0,3), B(1,2), C(3,5), D(4,7), E(5,7), F(7,9), G(8,10). Présenter la trace.

TD 5 — Argument d’échange

Rédiger une preuve concise montrant que choisir l’activité qui termine le plus tôt est un choix sûr.

TD 6 — Planification avec profits

Planifier les tâches unitaires T1(échéance 2, profit 60), T2(1, 100), T3(3, 20), T4(2, 40), T5(1, 20). Donner le planning et le profit total.

TD 7 — Huffman

Construire les fusions de Huffman pour les fréquences A:2, B:3, C:7, D:8, E:12. Proposer un code binaire valide et calculer son coût pondéré.

TD 8 — Glouton ou programmation dynamique ?

Pour chacun des problèmes suivants, proposer la méthode la plus adaptée et justifier : rendu de monnaie général, sélection d’activités, sac à dos 0/1, sac à dos fractionnaire, plus longue sous-suite commune.

TD 9 — Analyse de complexité

Analyser la complexité d’un algorithme de sélection d’activités avec tri, puis celle de Huffman avec une file de priorité binaire.

TD 10 — Évaluer une heuristique

On utilise la méthode du plus proche voisin pour construire une tournée. Proposer un protocole expérimental permettant de comparer cette heuristique à l’optimum sur de petites instances.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

Correction du TD 2

289 = 2×100 + 1×50 + 1×20 + 1×10 + 1×5 + 2×2. Le rendu contient 8 pièces : 100, 100, 50, 20, 10, 5, 2, 2.

Correction du TD 3

Pour le montant 11, le glouton choisit 9 + 1 + 1, soit 3 pièces. La solution 6 + 5 utilise seulement 2 pièces. Le système n’est donc pas canonique.

Correction du TD 4

Après tri par date de fin : B(1,2), A(0,3), C(3,5), D(4,7), E(5,7), F(7,9), G(8,10).

Sélection : B, C, E, F, soit quatre activités.

Correction du TD 5

Soit O une solution optimale dont la première activité est X. Soit G l’activité qui se termine le plus tôt. Comme fin(G) ≤ fin(X), remplacer X par G conserve la compatibilité avec toutes les activités suivantes de O. On obtient donc une solution optimale commençant par G. Le même raisonnement s’applique au sous-problème restant.

Correction du TD 6

Tri par profit : T2(100), T1(60), T4(40), T3(20), T5(20).

Planning : [T2, T1, T3]. Profit total : 100 + 60 + 20 = 180.

Correction du TD 7

Un codage possible dépend du départage des fréquences égales. Par exemple : E=0, D=10, C=111, A=1100, B=1101. Le coût pondéré vaut 12×1 + 8×2 + 7×3 + 2×4 + 3×4 = 69 bits.

Correction du TD 8

Correction du TD 9

Sélection d’activités : tri O(n log n), parcours O(n), soit O(n log n) et O(n) de mémoire si une nouvelle liste est créée. Huffman : k insertions ou construction initiale du tas, puis k−1 fusions avec deux extractions et une insertion, soit O(k log k).

Correction du TD 10

1.  Générer de petites instances de 5 à 10 villes avec des distances symétriques.

2.  Calculer la tournée du plus proche voisin à partir de chaque ville possible.

3.  Calculer l’optimum par énumération des permutations, uniquement pour ces petites tailles.

4.  Comparer le coût absolu, l’écart relatif et le temps de calcul.

5.  Répéter sur plusieurs distributions de points et présenter moyenne, maximum et écart-type de l’erreur.

Travail pratique — Glouton, optimum et contre-exemples

Objectifs

• implémenter plusieurs stratégies gloutonnes ;
• construire une solution exacte de référence sur de petites instances ;
• mesurer la qualité et le temps de calcul ;
• identifier automatiquement des contre-exemples ;
• présenter une preuve ou conclure que la stratégie n’est qu’une heuristique.

Partie A — Rendu de monnaie

1.  Implémenter le rendu glouton avec des pièces triées en ordre décroissant.

2.  Implémenter une programmation dynamique calculant le nombre minimal de pièces.

3.  Tester les systèmes {1,2,5,10,20,50}, {1,3,4} et {1,5,6,9}.

4.  Générer les montants de 1 à 200 et relever les premiers contre-exemples.

5.  Comparer le temps et la mémoire des deux méthodes.

Partie B — Sélection d’activités

1.  Générer un ensemble d’intervalles aléatoires.

2.  Implémenter le glouton par fin croissante.

3.  Pour n ≤ 20, calculer l’optimum par exploration de tous les sous-ensembles.

4.  Vérifier expérimentalement que les cardinalités coïncident.

5.  Rédiger un argument d’échange indépendant des tests.

Partie C — Huffman

1.  Compter les fréquences des caractères d’un texte.

2.  Construire l’arbre avec une file de priorité minimale.

3.  Produire le dictionnaire caractère → code.

4.  Encoder puis décoder le texte.

5.  Comparer la taille obtenue à un codage fixe de 8 bits par caractère.

Jeux d’essai minimaux

Livrables

• code source organisé et documenté ;
• description des structures de données utilisées ;
• tableau des résultats glouton / optimum ;
• liste des contre-exemples trouvés ;
• analyse de complexité ;
• courte justification de correction pour la sélection d’activités et Huffman ;
• discussion sur les limites de l’expérimentation.

Grille d’évaluation

Synthèse du chapitre

Glossaire

Auto-évaluation