CHAPITRE 6 : LES DEUX CONDITIONS, ET COMMENT LE PROUVER
Nous avons vu le glouton réussir trois fois et échouer une fois. Il est temps de dire pourquoi, et de donner la méthode qui permet de trancher avant d'écrire une ligne de code.
Le bilan des quatre problèmes
| Problème | Critère glouton | Optimal ? |
|---|---|---|
| Rendu de monnaie (FCFA) | la plus grosse coupure | oui |
| Rendu de monnaie {1, 3, 4} | la plus grosse coupure | non |
| Sac à dos en sacs entiers | le plus rentable au kilo | non |
| Sac à dos fractionnaire | le plus rentable au kilo | oui |
| Choix d'activités | finit le plus tôt | oui |
Notez les lignes 1 et 2 : même critère, même algorithme, et pourtant l'un est exact et l'autre non. Ce n'est donc pas l'algorithme qui décide, c'est la structure du problème.
Première condition : la propriété du choix glouton
Propriété du choix glouton. Il existe toujours une solution optimale qui contient le premier choix du glouton.
Autrement dit : en prenant le meilleur candidat immédiat, on ne se ferme jamais la porte de l'optimum. On peut toujours compléter ce choix pour arriver à une meilleure solution possible.
Vérifions sur le choix d'activités. Le glouton prend l'activité qui finit le plus tôt. Existe-t-il une solution optimale qui la contient ? Oui, c'est exactement ce que la démonstration du chapitre 5 a établi par échange.
Vérifions sur le sac à dos en sacs entiers. Le glouton prend le poivre, puis le safou. Existe-t-il une solution optimale contenant le safou ? Non : l'unique optimum est poivre + miel. La propriété est violée, et c'est pour cela que le glouton échoue.
Seconde condition : la sous-structure optimale
Sous-structure optimale. Une solution optimale du problème contient des solutions optimales de ses sous-problèmes.
Autrement dit : une fois le premier choix fait, ce qui reste à résoudre est un problème de même nature, plus petit, et il faut le résoudre optimalement, lui aussi.
Pour le choix d'activités : après avoir retenu l'activité qui finit à 10 h, il reste à caser le maximum d'activités commençant après 10 h. C'est le même problème, sur moins de données.
Les deux conditions réunies garantissent qu'un algorithme glouton est exact. L'une sans l'autre ne suffit pas.
La nuance avec la programmation dynamique. Elle aussi exige la sous-structure optimale. La différence est dans le moment du choix :
- La programmation dynamique résout d'abord les sous-problèmes, puis décide, en s'appuyant sur leurs résultats.
- Le glouton décide d'abord, puis résout le sous-problème qui en découle.
C'est tout l'écart : le glouton se passe de la propriété du choix glouton… ou plutôt, il la suppose. Quand elle est fausse, il se trompe.
La méthode, en quatre questions
Avant d'écrire un glouton, posez-vous ceci dans l'ordre :
- Quel est exactement l'objectif ? Le plus grand nombre d'activités, ou la plus longue occupation ? Le moins de pièces, ou le moins d'espèces en caisse ? Une formulation floue garantit un mauvais algorithme.
- Quel critère de choix ? Énumérez-en plusieurs. Nous en avons vu trois pour les activités, trois pour le sac à dos.
- Cherchez un contre-exemple. Prenez trois ou quatre données et essayez de mettre le critère en défaut. C'est l'étape la plus rentable : elle coûte cinq minutes et évite des jours de débogage.
- Si vous n'en trouvez pas, démontrez. Par argument d'échange, comme aux chapitres 4 et 5.
L'argument d'échange, en trois lignes
La démonstration suit toujours le même canevas :
1. Soit O une solution optimale, differente de celle du glouton G.
2. Montrer qu'on peut modifier O pour qu'elle contienne le premier
choix de G, SANS la degrader.
3. Recommencer sur le sous-probleme restant.
Conclusion : G est au moins aussi bonne que O, donc G est optimale.Le point 2 est le cœur. Si vous n'arrivez pas à faire l'échange sans perdre de valeur, c'est souvent que la propriété est fausse, et que votre glouton se trompe.
Les trois approches, côte à côte
| Force brute | Prog. dynamique | Glouton | |
|---|---|---|---|
| Principe | tout essayer | retenir les calculs | décider tout de suite |
| Résultat | optimal | optimal | optimal si les deux conditions tiennent |
| Sac à dos 0-1 | O(2ⁿ) | O(n·W) | O(n log n) |
| Mémoire | faible | élevée | faible |
| À écrire | facile | délicat | facile |
| À prouver | trivial | moyen | difficile |
Le glouton est le plus simple à écrire et le plus difficile à justifier. C'est exactement l'inverse de ce qu'on croit en le découvrant.
Quand le glouton n'est pas optimal : s'en servir quand même
Un glouton qui se trompe reste souvent utile :
- Comme approximation assumée. Le sac à dos glouton garantit au moins la moitié de l'optimum. Sur notre exemple, il en donnait 92 %.
- Comme point de départ. On part de la solution gloutonne et on l'améliore par échanges successifs, c'est le principe des métaheuristiques.
- Comme borne. Dans les algorithmes exacts de type séparation-évaluation, la solution gloutonne sert à élaguer l'arbre de recherche.
Le péché n'est pas d'utiliser un glouton qui se trompe. C'est de croire qu'il ne se trompe pas.
À retenir
- Deux conditions : propriété du choix glouton, et sous-structure optimale.
- Le glouton décide avant de résoudre ; la programmation dynamique résout avant de décider.
- Avant de démontrer, cherchez un contre-exemple : c'est plus rapide et souvent concluant.
- La preuve se fait par argument d'échange, toujours selon le même canevas.
- Un glouton non optimal reste utile comme approximation, comme point de départ ou comme borne.
Exercices d'application
(a) Rendre la monnaie avec {1, 5, 10, 25}
(b) Trouver le plus court chemin entre deux villes
(c) Remplir un camion de sacs de ciment tous identiques
Voir le corrigeMasquer le corrige
(a) Oui. Ce système est canonique, c'est celui du dollar américain. On peut le vérifier montant par montant, ou invoquer le fait que chaque coupure est un multiple « suffisamment grand » de la précédente. Attention : la canonicité ne se lit pas à l'œil nu, {1, 3, 4} le montre.
(b) Oui, avec le bon glouton. L'algorithme de Dijkstra est un glouton : à chaque étape, il fixe définitivement la ville la plus proche encore inexplorée. Il est démontré optimal : à condition que les distances soient positives. Avec des distances négatives, il échoue, et il faut Bellman-Ford.
(c) Oui, trivialement. Si tous les sacs sont identiques, il n'y a aucun choix à faire : on en met autant que le camion peut en porter. Le problème n'a plus de structure combinatoire ; n'importe quel ordre donne le même résultat.
Ce dernier cas rappelle une chose utile : quand tous les candidats se valent, la question de l'optimalité ne se pose même pas.
Voir le corrigeMasquer le corrige
Notons G la valeur obtenue par le glouton, O l'optimum en sacs entiers, et F l'optimum fractionnaire.
Étape 1. Le fractionnaire est au moins aussi bon que l'entier, puisqu'il autorise tout ce que l'entier autorise, et plus encore :
O ≤ F
Étape 2. Le glouton fractionnaire prend les mêmes objets entiers que le glouton 0-1, plus une fraction d'un dernier objet, appelons-le x. Donc :
F ≤ G + valeur(x)
Étape 3. Par hypothèse, x tient dans le sac à lui seul. Le glouton aurait donc pu le prendre s'il n'avait rien pris d'autre, ce qui donne :
G ≥ valeur(x)
Conclusion. En combinant :
O <= F <= G + valeur(x) <= G + G = 2G
donc G >= O / 2Le glouton garantit au moins la moitié de l'optimum. ∎
Sur l'exemple du chapitre 3, il donnait 110 000 sur 120 000, soit 92 % : bien au-dessus de la garantie. La borne est pessimiste, mais c'est une garantie, pas une estimation.
Voir le corrigeMasquer le corrige
1. Formuler l'objectif sans ambiguïté. Qu'est-ce qui est maximisé ou minimisé ? Quelles sont les contraintes ? Beaucoup d'erreurs viennent d'un énoncé mal lu : « le plus d'activités » et « la plus longue occupation » n'ont pas la même réponse.
2. Estimer la taille. Dix objets ? La force brute suffit, et elle est exacte. Dix mille ? Il faut autre chose.
3. Chercher un critère glouton et tenter de le casser. Prenez trois ou quatre données construites exprès pour le piéger. Si vous trouvez un contre-exemple, vous venez d'économiser beaucoup de temps.
4. Si le glouton résiste, démontrer par argument d'échange. Si la démonstration bloque, c'est souvent qu'un contre-exemple existe et que vous ne l'avez pas encore trouvé.
5. Sinon, passer à la programmation dynamique si le problème a une sous-structure optimale, ou accepter le glouton comme approximation en mesurant son écart sur des données réelles.
L'erreur la plus coûteuse est de sauter l'étape 3. Un glouton faux fonctionne correctement sur les jeux d'essai et se trompe en production : sans jamais lever d'erreur.
Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.
Questions / Réponses
Ajouter un commentaire