Aller au contenu

Chapitre 13 : Algorithmes gloutons⚓︎

I. Qu’est-ce qu’un algorithme glouton⚓︎

A savoir

Les algorithmes gloutons (greedy algorithm en anglais) sont une catégorie d’algorithmes permettant de résoudre les problèmes d’optimisation : trouver parmi les différentes solutions d’un problème une des solutions parmi les meilleures possibles (appelées solutions optimales) tout en respectant une contrainte donnée.

Monsieur glouton

Pour résoudre le problème, la méthode gloutonne va construire une solution étape par étape en effectuant une succession de choix :

  • En faisant à chaque étape le choix qui semble le meilleur (choix optimal) : de moindre coût ou de meilleur gain.
  • Sans revenir sur les choix passés et sans prendre en compte les choix futurs : il n’explore pas toutes les voies possibles comme le ferait un algorithme de force brute.

Les algorithmes gloutons sont intuitifs et faciles à mettre en œuvre.

Ils mettent en œuvre une succession de choix optimaux en espérant construire une solution optimale.

Cependant, ils n’aboutissent pas toujours à la meilleure solution pour tous les problèmes mais dans la plupart des cas celle-ci est suffisamment optimisée pour être acceptable.

▶️ Capsule : les algorithmes gloutons

II. le problème du rendu de monnaie⚓︎

A savoir

Dans le problème du rendu de monnaie, le but est de choisir un ensemble de pièces dont la somme est égale à un certain montant à rendre : l’optimisation consiste à rendre ce montant avec le moins de pièces possible.

A chaque étape l’algorithme doit déterminer, en faisant un choix glouton (le choix optimal):

  • Quelle est la pièce de plus grande valeur qui ne dépasse pas le montant restant.
  • Combien de pièces il est possible de rendre sans dépasser le montant restant.

Suivant le système de pièces, l'algorithme glouton est optimal ou pas.

Exemple

On souhaite rendre la somme de 6 centimes avec le système de pièces suivant :

Un système de pièces
Le système de pièces

À chaque étape :

  1. On sélectionne la pièce de plus grande valeur inférieur à la somme à rendre

  2. On mémorise cet élément.

  3. On sosutrait cette pièce à la somme à rendre

  4. On reprend à l'étape 1 avec la nouvelle somme à rendre

Un exemple du rendu de monnaie
Un exemple du rendu de monnaie

Dans ce système de pièces l'algorithme glouton n'est pas optimal mais il donne une solution acceptable en 3 pièces au lieu de 2. En effet pour un montant de 6 à rendre on peut avoir les deux solutions suivantes.

Deux solutions possibles
Deux solutions possibles

▶️ Capsule : le problème du rendu de monnaie

III. le problème du sac à dos⚓︎

A savoir

Un voleur dispose d’un sac pouvant supporter une masse maximale de 15kg dans lequel il va mettre des objets qui ont une certaine masse et une certaine valeur. L’objectif est de choisir les objets pour maximiser la valeur du butin mais sans dépasser la capacité maximale du sac (on dit qu'il s'agit d'un problème d'optimisation avec contrainte, ici la contrainte de poids).

Le probleme du sac a dos
Le problème du sac a dos

Il y a plusieurs stratégies gloutonnes possibles :

  • Stratégie 1 : prendre toujours l'objet de plus grande valeur possible sans dépasser la capacité maximale (il faut trier préalablement par valeur décroissante).
  • Stratégie 2 : prendre toujours l'objet de plus faible masse possible (il faut trier préalablement par masse croissante).
  • Stratégie 3 : prendre toujours l'objet de plus grand taux de valeur (=valeur/masse) n'excédant pas la capacité restante (il faut trier préalablement par rapport au taux de valeur décroissant).

Selon les exemples, l'une des stratégies se révélera meilleure que les autres mais ne garantit pas d'obtenir une solution optimale

IV. Pourquoi se contenter d'une solution non optimale ?⚓︎

A savoir

Dans les deux problèmes abordés, la stratégie gloutonne ne donne pas forcément un résultat optimal. Mais alors, est-il 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 qui consiste à passer en revue toutes les options possibles et retenir la meilleure mais cette option n’est pas forcément toujours possible !!!

Dans le cas du 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= 8\) combinaisons d'objets possibles ce qui est tout à fait acceptable en terme de complexité.
  • Avec n objets, il y a \(2^n\) combinaisons à énumérer et tester : on obtient une complexité dite exponentielle. Avec 80 objets, on obtient \(2^8\) combinaisons à tester, c'est-à-dire environ 1024 combinaisons, soit de l'ordre de grandeur du nombre d'étoiles dans l'Univers observable (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.

V. Autres problèmes classiques⚓︎

A savoir

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

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