La programmation gloutonne est une stratégie de résolution de problèmes d'optimisation combinatoire où l'on fait des choix localement optimaux à chaque étape, sans revenir en arrière. Contrairement à la programmation dynamique, qui résout des sous-problèmes pour construire une solution globale, la programmation gloutonne prend des décisions immédiates en espérant qu'elles mènent à une solution globale optimale.
Avantages :
Exemple : Dans un graphe pondéré, pour trouver un chemin de poids minimal, un algorithme glouton pourrait choisir à chaque étape l'arête de plus faible poids.
Un arbre couvrant de poids minimal (ACPM) est un sous-ensemble d'arêtes d'un graphe connexe qui :
Propriété : Pour toute coupe d'un graphe pondéré, l'arête de poids minimal qui traverse cette coupe fait partie de l'ACPM.
Cela permet de construire l'ACPM en ajoutant à chaque étape l'arête de poids minimal qui ne forme pas de cycle.
O(m log n) (avec m = nombre d'arêtes, n = nombre de sommets).Union-Find).O(m log n).O(m + n log n) avec une file de priorité.La coloration de graphes consiste à attribuer une couleur à chaque sommet de sorte que deux sommets adjacents n'aient pas la même couleur. L'objectif est de minimiser le nombre de couleurs utilisées.
Problème : Cet algorithme ne garantit pas une solution optimale, car le nombre de couleurs dépend de l'ordre de traitement des sommets.
Complexité : O(n^2) (avec n = nombre de sommets).
Exemple : Le graphe de Petersen (figure 4.3) peut être colorié avec 3 couleurs, mais l'algorithme glouton peut en utiliser 4 selon l'ordre des sommets.
Le problème du choix d'activités consiste à sélectionner un ensemble maximal d'activités compatibles (non chevauchantes) parmi un ensemble donné. Chaque activité a une date de début et de fin.
Plusieurs critères peuvent être utilisés, mais seul l'un d'eux garantit une solution optimale :
O(n log n) (à cause du tri initial).Pour prouver que le critère "date de fin la plus précoce" est optimal, on montre que :
Pour concevoir un algorithme glouton optimal, il faut :
| Critère | Programmation Gloutonne | Programmation Dynamique |
|---|---|---|
| Approche | Descendante (choix local → solution globale) | Ascendante (sous-problèmes → problème global) |
| Complexité | Souvent polynomiale | Souvent exponentielle ou polynomiale |
| Optimalité | Pas toujours garantie | Toujours garantie (si bien conçue) |
| Exemple | Algorithme de Kruskal | Algorithme de Fibonacci |
À la fin de ce chapitre, vous devriez être capable de :
Remarque : La programmation gloutonne ne fonctionne pas pour tous les problèmes (ex : problème du voyageur de commerce, coloration optimale de graphes). Dans ces cas, on utilise des heuristiques ou des algorithmes d'approximation.
Répondez à toutes les questions pour valider votre maîtrise du chapitre.