Algorithmes gloutons
Un algorithme glouton s'engage sur un choix localement préférable sans le remettre en cause. Cette stratégie n'est correcte que si la structure du problème permet de prouver qu'une solution optimale contient ce choix.
Démarche de conception
- Définissez précisément les solutions admissibles et l'objectif.
- Énoncez la règle de choix local et le problème qui subsiste ensuite.
- Prouvez que le choix est sûr.
- Montrez que le problème résiduel conserve la même structure.
- Déduisez la complexité des structures de données employées pour la sélection et les mises à jour.
Schémas de preuve courants
- Argument d'échange : remplacez une partie d'une solution optimale par le choix glouton sans la détériorer.
- Rester en avance : après chaque préfixe de choix, le glouton est au moins aussi bon que tout concurrent selon une mesure utile.
- Propriété de la coupe : une arête localement légère est sûre à travers une partition appropriée.
- Induction : après avoir prouvé que le premier choix est sûr, appliquez le même raisonnement à l'instance résiduelle.
Problèmes représentatifs
Sur des instances arbitraires, le rendu de monnaie glouton, le profit immédiat maximal ou le coût immédiat minimal peuvent échouer. Une règle plausible reste une conjecture tant qu'une preuve ou un théorème structurel connu ne l'étaye pas.
Algorithmes gloutons et programmation dynamique
La programmation dynamique compare les possibilités entre des états réutilisables. Un algorithme glouton les ramène à un seul choix grâce à un théorème de sûreté. Lorsque la propriété d'échange échoue, il peut être nécessaire de conserver davantage d'état.
Une règle réfutée et l'état à conserver
Avec les dénominations 1, 3 et 4 utilisables sans limite, prendre la plus grande rend 6 par 4+1+1, alors que 3+3 emploie moins de pièces. La règle locale élimine ce dernier choix sans échange valide : remplacer deux 3 par un 4 laisse un reste exigeant deux pièces supplémentaires.
Un programme dynamique conserve dp[t], le nombre minimal de pièces pour le montant exact t, et essaie chaque dernière pièce : dp[t] = min(1+dp[t-c]) parmi les dénominations c ne dépassant pas t. Initialisez dp[0]=0 et les montants impossibles à l'infini. Pour 0..6, la table est [0,1,2,1,1,2,2]. Ce modèle à entiers positifs et usage illimité se résout en O(Tk) en temps et O(T) en espace. L'échec du glouton n'impose pas toujours la programmation dynamique : une recherche exhaustive ou un autre algorithme structurel peut mieux convenir.