Prenons l'exemple ci-dessous correspondant à un problème d'optimisation :

Il s'agit de trouver un chemin partant de la racine de l'arbre et dont la somme des étiquettes est la plus grande possible.

La solution optimale est indiquée ici en vert.

Principe d'un algorithme Glouton.

On utilise ce type d'algorithme lorsqu'on est confronté à un problème d'optimisation pour lequel la recherche de la solution optimale est difficile. En algorithmique, difficile veut dire qu'on ne peut pas résoudre le problème en un temps raisonnable. Habituellement cela veut dire que la complexité est plus que polynomiale. Pour pouvoir utiliser un algorithme glouton, il faut qu'on puisse fournir de multiples solutions, certaines optimales, certaines bonnes et d'autres plutôt mauvaises. S'il n'y a qu'une solution UNIQUE, ce n'est pas de l'optimisation !

Dans le cas de la recherche de notre chemin dans un arbre, l'algorithme glouton sélectionne le plus grand nombre disponible à chaque étape.

Notons que le terme anglais "greedy" se traduit également par cupide, avide, qui illustre bien l'idée de cet algorithme qui est de choisir la grande valeur possible à chaque étape.

Limites de l'algorithme.

Cependant, comme nous pouvons le voir dans l'animation ci-dessous, cette approche ne parvient toujours pas à trouver la somme la plus élevée, En effet l'algorithme prend des décisions uniquement en fonction des informations dont il dispose à chaque étape, sans tenir compte du problème global.

Notons, que les algorithmes Gloutons réussissent assez bien dans certains problèmes, tels que l' encodage de Huffman, utilisé pour compresser les données, ou l'algorithme de Dijkstra , qui permet de trouver le chemin le plus court dans un graphe.

Quoiqu'il en soit, même si la stratégie gourmande ne produit pas toujours une solution optimale, elle permet de proposer une solution.

C'est le cas par exemple dans le problème dit "du sac à dos" et dans le problème dit "du rendu de monnaie" que nous allons étudier.

Le problème du sac à dos.

Le problème consiste à remplir un sac à dos, ne pouvant supporter plus d'une certaine masse, avec tout ou partie d'un ensemble donné d'objets ayant chacun une masse et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser la masse maximum.

Algorithme

Une astuce consiste à trier les objets dans l'ordre décroissant de leur valeur.

Un cambrioleur possède un sac à dos d'une contenance maximum de 30 Kg. Au cours d'un de ses cambriolages, il a la possibilité de dérober 4 objets A, B, C et D. Voici un tableau qui résume les caractéristiques de ces objets :

Ce genre de problème est un grand classique en informatique, on parle de problème d'optimisation. Il existe toujours plusieurs solutions possibles à un problème d'optimisation (dans le problème du sac à dos, on peut choisir A+B ou A+C ou B+C+D... toutes les combinaisons sont possibles à partir du moment où la masse totale ne dépasse pas 30 Kg), mais on ne cherche pas n'importe quelle solution, on cherche une solution dite optimale : dans notre exemple on cherche le plus grand gain possible. Souvent, dans les problèmes d'optimisation, il n'existe pas une solution optimale, mais plusieurs solutions optimales, résoudre un problème d'optimisation c'est donc trouver une des solutions optimales.

Il existe différentes méthodes algorithmiques permettant de trouver une solution optimale à un problème d'optimisation : il peut, en effet, être intéressant "d'automatiser" la résolution des problèmes d'optimisation à l'aide d'algorithme (dans notre cas, trouver un algorithme qui trouve une solution optimale au problème du sac à doc).

En apparence, la solution la plus simple dans le cas du sac à dos serait d'écrire un algorithme qui teste toutes les combinaisons d'objets possibles et qui retient les solutions qui offrent un gain maximum. Dans notre cas précis, avec seulement 4 objets, cette solution pourrait être envisagée, mais avec un plus grand nombre d'objets, le temps de calculs, même pour un ordinateur très puissant, deviendrait trop important. En effet l'algorithme qui testerait toutes les combinaisons possibles aurait une complexité en temps en O(aⁿ) avec a une constante et n les nombre d'objets. On parle d'une complexité exponentielle. Les algorithmes à complexité exponentielle ne sont pas efficaces pour résoudre des problèmes, le temps de calcul devient beaucoup trop important quand n devient très grand.

À la place de cette méthode "je teste toutes les possibilités", il est possible d'utiliser une méthode dite gloutonne (greedy en anglais).

• Sachant que l'on cherche à maximiser le gain, commençons par établir un tableau nous donnant la "valeur massique" de chaque objet (pour chaque objet on divise sa valeur par sa masse) :

  valeur massique des objets

  objet	A	B	C	D
  valeur massique	54 €/Kg	33 €/Kg	38 €/Kg	30 €/Kg

  
  
• On classe ensuite les objets par ordre décroissant de valeur massique : A - C - B -D
• Enfin, on remplit le sac en prenant les objets dans l'ordre et en s'arrêtant dès que la masse limite est atteinte. C'est ici que ce fait "le choix glouton", à chaque étape, on prend l'objet ayant le rapport "valeur-masse" le plus intéressant au vu des objectifs :
  • 1re étape : A (13 Kg)
  • 2e étape : C (13+8=21 Kg)
  • 3e étape : B (13+8+12=33 Kg) => impossible, on dépasse les 30 Kg.

Le sac est donc composé de 2 objets : A et C pour un montant total de 1000 € et une masse totale de 21 Kg.

Cette méthode gloutonne peut être "automatisée", il est donc possible d'écrire un algorithme glouton (un algorithme qui est basé sur une méthode gloutonne) afin de trouver une solution au problème du sac à dos avec n'importe quelles valeurs (nombre d'objets, masse des objets, valeur des objets, masse maximum).

La solution trouvée ci-dessus est-elle optimale ?

On constate rapidement que la réponse est non, car le couple A+B permet d'atteindre une valeur de 1100 € pour une masse de 25 Kg. Dans notre problème, la méthode gloutonne ne nous donne pas une solution optimale.

Plus généralement , il est important de bien comprendre qu'un algorithme glouton ne donne pas forcement une solution optimale. Pour certains types de problèmes, il est possible de démontrer qu'un algorithme glouton donnera toujours une solution optimale, mais cela dépasse largement le cadre de ce cours.

Rendu de monnaie

Autre problème typique : le rendu de monnaie.

Imaginons une somme de 5,50 euros à rendre.

Nous avons à disposition le billet de 5 euros, la pièce de 2 euros, la pièce de 1 euro, la pièce de 50 cents, la pièce de 20 cents, la pièce de 10 cents, la pièce de 5 cents.

Pour le transformer en problème d'optimisation, il faut rajouter une condition : on veut une solution pour laquelle on rend le moins de pièces ou de billets possibles.

Pour un humain, ça ne pose pas de problème : un billet de 5 euros et une pièce de 50 cents.

Mais vous vous rendez bien compte des possibilités possibles à comparer pour une machine...

Nous allons donc appliquer une stratégie gloutonne en choisissant cette solution locale optimale : toujours compléter la somme à rendre avec le billet ou la pièce la plus grande utilisable.

Et voilà. Ca fonctionne toujours pourvu qu'on ai une pièce correspondant à la plus petite somme à rendre mais ça ne donne pas toujours la solution optimale. De toutes manières, évaluer toutes les possibilités ne devrait pas faire diminuer significativement le nombre de pièces à rendre.

                                
les_choix = [100, 50, 20, 10, 5, 2, 1]
 
def rendre(a_rendre, choix=les_choix):
    reponse = []
    return reponse
                                
                            

                                    
les_choix = [100, 50, 20, 10, 5, 2, 1]
 
def rendre(a_rendre, choix=les_choix):
    reponse = []
    reste = a_rendre
    index = 0
    while ... :
        if ... :
            ....
            ....
        else :
            ...
    return reponse                                    
                                

                                    
les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.01]
 
def rendre(a_rendre, choix=les_choix):
    reponse = []
    reste = round(a_rendre, 2)
    index = 0
    while reste > 0 :
        if reste >= choix[index] :
            reste = round(reste - choix[index], 2)
            reponse.append(choix[index])
        else :
            index = index + 1
    return reponse                                    
                                

                                    
les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.01]
 
def rendre(a_rendre, choix=les_choix):
    choix_en_cents = [round(valeur*100) for valeur in choix]
    reponse = []
    reste = round(a_rendre*100)
    index = 0
    while reste > 0 :
        if reste >= choix_en_cents[index] :
            reste = reste - choix_en_cents[index]
            reponse.append(choix[index])
        else :
            index = index + 1
    return reponse                                    
                                    

                                    
les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.01]
 
def rendre(a_rendre, choix=les_choix):
    assert a_rendre > 0, "La somme à rendre doit être positive ou nulle à la limite"
    choix_en_cents = [round(valeur*100) for valeur in choix]
    reponse = []
    reste = round(a_rendre*100)
    index = 0
    while reste > 0 :
        if reste >= choix_en_cents[index] :
            reste = reste - choix_en_cents[index]
            reponse.append(choix[index])
        else :
            index = index + 1
    return reponse