Algorithmes gloutons

Introduction

On dit greedy algorithms en anglais, l'adjectif « greedy » signifiant avare/glouton.

Algorithmes gloutons et optimalité

Faire le meilleur choix (local) à chaque étape nous conduit-il nécessairement à la meilleure solution globale ?

Commençons par quelques exemples pour répondre à cette question.

Exemples simples

Moralité

Néanmoins, une stratégie gloutonne permet d'aboutir rapidement à une solution, en espérant qu'il s'agisse d'une bonne solution globale (à défaut d'être optimale).

Pourquoi se contenter d'une solution non optimale ?
Un peu de patience, nous en discuterons à la fin.

Voyons deux problèmes classiques qui peuvent être résolus par un algorithme glouton.

Le problème du rendu de monnaie

Énoncé

Moralité : L'algorithme glouton du rendu de monnaie :

• ne donne pas nécessairement la solution optimale au problème, cela dépend du système monétaire
• ne donne pas nécessairement une solution exacte au problème, même lorsque celle-ci existe

Implémentation

Voici une implémentation possible :

def rendu_glouton(somme_a_rendre, pieces):
    solution = []
    i = 0  # i est l'indice de la pièce à tester
    while somme_a_rendre > 0:  # tant qu'on n'a pas tout rendu
        if pieces[i] <= somme_a_rendre:  # si on peut rendre une pièce
            solution.append(pieces[i])  # on le fait
            somme_a_rendre = somme_a_rendre - pieces[i]  # et on la déduit de la somme
        else:
            i = i + 1  # sinon on passe à la suivante
    return solution

On peut vérifier que cela fonctionne bien :

>>> rendu_glouton(147, [500, 200, 100, 50, 20, 10, 5, 2, 1])
[100, 20, 20, 5, 2]

Comme déjà évoqué, la solution gloutonne n'est pas toujours optimale :

>>> rendu_monnaie_glouton(8, [6, 4, 1])
[6, 1, 1]  # on pouvait rendre seulement 2 pièces : [4, 4]

Et s'il n'y a pas de pièce unité ?

Notre algorithme ne convient pas s'il n'y a pas de pièce unité. En effet, il se peut alors que l'on ne puisse pas rendre de manière exacte la somme avec notre système monétaire, ce qui impliquerait que l'indice i va dépasser la dernière pièce et on aura une erreur de type IndexError: list index out of range. Pour éviter ce problème, on peut rajouter une seconde condition à la boucle while pour la stopper après avoir testé la dernière pièce :

while somme_a_rendre > 0 and i < len(pieces):

Mais dans ce cas, la solution construite n'est pas toujours exacte :

>>> rendu_glouton(8, [5, 2])
[5, 2]  # on rend 7 au lieu de 8 (c'était possible !)

while somme_a_rendre > 0 and i < len(pieces):

Le problème du sac à dos

On dit Knapsack Problem en anglais, souvent abrégé KP.

Moralité : Résoudre le problème du sac à dos de manière gloutonne :

• peut se faire selon plusieurs stratégies, et selon les exemples, l'une ou l'autre se révélera meilleure que les autres.
• ne garantit pas d'obtenir une solution optimale

Pourquoi se contenter d'une solution non optimale ?

Comme nous venons de le voir dans les différents problèmes abordés, la stratégie gloutonne ne donne pas forcément un résultat optimal. On peut alors se demander s'il n'est pas possible de trouver la meilleure solution, à coup sûr, pour résoudre un problème d'optimisation.

Une telle approche existe, il s'agit de la stratégie de force brute (ou énumérative) qui consiste à passer en revue toutes les options possibles et retenir la meilleure.

Pourquoi n'utilise-t-on pas toujours la force brute ?

Car ce n'est pas toujours possible !

Le plus simple est de l'expliquer sur un exemple : prenons le problème du sac à dos.

Chaque objet est pris ou pas : il s'agit donc d'une donnée binaire. Avec 3 objets, il y a donc $2^3$ combinaisons d'objets possibles, c'est-à-dire 8, ce qui est tout à fait acceptable.

De manière générale, avec $n$ objets, il y aurait $2^n$ combinaisons à énumérer et tester. On obtient une complexité dite exponentielle et c'est là le problème : avec 80 objets, on obtient $2^{80}$ combinaisons à tester, c'est-à-dire environ $10^{24}$ combinaisons, soit de l'ordre de grandeur du nombre d'étoiles dans l'Univers observable, ou de gouttes d'eau dans la mer, ou du nombre de grains de sables au Sahara... (référence : https://fr.wikipedia.org/wiki/Ordres_de_grandeur_de_nombres).

Pour le problème du sac à dos, la stratégie force brute est donc inapplicable si trop d'objets sont en jeu. Il en est de même pour les autres problèmes d'optimisation dès que le taille des données est trop importante.

Autres problèmes classiques

Il existe de nombreux autres problèmes d'optimisation pouvant être résolu par un algorithme glouton (pas forcément de manière optimale) :

• problème du voyageur (plus court chemin)
• coloration d'un graphe
• coloriage de carte (voir le deuxième exemple de cette vidéo)
• organisation (de planning)
• ...

Certains sont abordés dans les exercices.

Conclusion

• Nous avons vu que les algorithmes gloutons fournissent une stratégie pour résoudre des problèmes d'optimisation : à chaque étape, faire le meilleur choix (local).
• Ils donnent rapidement une solution satisfaisante à un problème mais pas nécessairement la solution optimale puisque les choix successifs ne sont jamais remis en cause.
• La stratégie de force brute permettrait à coup sûr d'obtenir une solution optimale mais devient inapplicable dès que la taille des données est trop importante. Dans ce cas, une solution gloutonne peut être privilégiée (on s'en contente, faute de mieux).
• Lorsque la solution gloutonne n'est pas optimale, on dit que l'algorithme glouton est une heuristique de résolution (il fournit une solution approchée).
• Il existe d'autres méthodes algorithmiques pour résoudre des problèmes d'optimisation : certaines seront abordées en Terminale.

---

Références :

• Document ressource de l'équipe éducative du DIU EIL de l'Université de Nantes, diffusé sous licence CC BY : Algorithmes gloutons (Bloc 2, Séance 5).
• Prepabac, spécialité NSI 1ère, C. ADOBET, G. CONNAN, G. ROZSAVOLGYI, L. SIGNAC.
• Numérique et Sciences Informatiques, 1re, T. BALABONSKI, S. CONCHON, J.-C. FILLIATRE, K. NGUYEN, éditions ELLIPSES : Site du livre
• Cours de G. LASSUS sur les algorithmes gloutons : lien Github vers son notebook
• Ressources Eduscol : Algorithmes gloutons et Le problème du sac à dos

---

Germain BECKER & Sébastien POINT, Lycée Mounier, ANGERS