Algorithmes gloutons
Les algorithmes gloutons avancent par choix local optimal, mais leur correction doit être prouvée.
1
Principe
Idée générale
Un algorithme glouton construit la solution étape par étape en choisissant le meilleur candidat local.
- Choix local optimal à chaque étape.
- Construction progressive sans retour en arrière.
- Objectif : atteindre un optimum global si le problème le permet.
Critère
- Le critère de gloutonnerie doit être explicite.
- Il peut porter sur l’ordre, le coût, le profit ou la priorité.
2
Correction
Idée de preuve
- 1
Comparer la solution gloutonne à une solution optimale.
- 2
Montrer qu’un échange conserve la faisabilité.
Outils
Preuve d’échange
- On remplace un choix par un meilleur choix local.
- Elle montre que l’optimum peut adopter le choix glouton.
Invariant
- Une propriété reste vraie après chaque étape.
- Il aide à garantir la correction de la construction.
3
Exemples
Cas classiques
| Problème | Idée gloutonne |
|---|---|
| Rendu de monnaie | Prendre les plus grosses pièces possibles. |
| Ordonnancement | Choisir selon échéance, durée ou priorité. |
| Arbre couvrant minimal | Ajouter l’arête la moins chère compatible. |
| Plus court chemin | Étendre d’abord le sommet le plus proche. |
4
Illustration
Exemple concret
Rendu de monnaie avec les pièces 10, 5 et 1 pour rendre 18.
- Prendre 10, il reste 8.
- Prendre 5, il reste 3.
- Prendre 1 trois fois, le reste devient 0.
La solution gloutonne utilise 10, 5, 1, 1, 1, mais elle n’est optimale que pour certains systèmes monétaires.
5
Limites
Quand ça échoue
Réflexe examen
- Identifier le critère de gloutonnerie.
- Chercher un contre-exemple simple.
Mémo
Local ne veut pas dire global. Vérifie toujours la preuve avant d’annoncer l’optimalité.
Bilan
Résumé
- Le glouton choisit localement le meilleur candidat selon un critère précis.
- Il est rapide et simple, mais sa correction doit être démontrée.
- Il fonctionne bien pour certains problèmes, pas pour tous.