Chapitre 4: Algorithmes gloutons

Contenus Capacités attendues Commentaires
Algorithmes gloutons Résoudre un problème grâce à un algorithme glouton.

Exemples : problèmes du sac à dos ou du rendu de monnaie.

Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale.

Nous allons voir dans ce chapitre comment résoudre des problèmes d’optimisation à l’aide d’algorithmes.

Un problème d’optimisation consiste à minimiser ou maximiser une fonction sur un ensemble.

La particularité des algorithmes gloutons est qu’ils donnent généralement une solution assez satisfaisante relativement rapidement, mais ce n’est pas forcément la meilleure.

Comment rendre 36 centimes avec le minimum de pièces? Etudier tous les rendus possibles et trop long, on applique un rendu de monnaie qui est optimal si le jeu de pièces est bien fait(C'est le cas heureusement).
Comment rendre 36 centimes avec le minimum de pièces? Etudier tous les rendus possibles et trop long, on applique un rendu de monnaie qui est optimal si le jeu de pièces est bien fait(C'est le cas heureusement).
 Public domain via Wikimedia Commons

1 Le problème du sac à dos

Il s’agit d’un problème classique d’introduction aux algorithmes gloutons.

En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack problem) est un problème d’optimisation combinatoire. Il modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble donné d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.

Article Wikipedia

Illustration du problème du sac à dos
Illustration du problème du sac à dos
©  CC BY-SA 2.5 via Wikimedia Commons

2 Exploration systématique(force brute)

L’exploration de toutes les possibilités consiste à construire un arbre d’exploration binaire.

arbre binaire interstices CC-BY-SA-NC

À chaque fois qu’un objet est ajouté à la liste des objets possibles, la taille de l’arbre est multipliée par 2.

Il s’agit d’une complexité exponentielle ce qui rend cette méthode de résolution inutilisable dans la pratique(Pensez au nombre de routes entre votre maison et le lycée!).

3 Méthode approximative: l’algorithme glouton

L’algorithme le plus simple est un algorithme glouton. L’idée est d’ajouter en priorité les objets les plus efficaces, jusqu’à saturation du sac :

trier les objets par ordre décroissant d'efficacité
w_conso := 0

placer les objets dans le sac par ordre décroissant d'efficacité
pour i de 1 à n
  si w[i] + w_conso ≤ W alors
    x[i] := 1
    w_conso := w_conso + w[i]
  sinon
    x[i] := 0
  fin si
fin pour

Les deux étapes de cet algorithme: A trier les objets par ordre décroissant d'efficacité puis B placer les objets dans le sac dans cet ordre si possible
Les deux étapes de cet algorithme: A trier les objets par ordre décroissant d'efficacité puis B placer les objets dans le sac dans cet ordre si possible
©  CC BY-SA 2.5 via Wikimedia Commons

On obtient ici une solution de 11$ pour 11 kg alors que la solution optimale est de 12$ et 14 kg.

4 Le problème du rendu de monnaie

Examinons un autre problème d’optimisation : le problème du rendu de monnaie

Nous sommes des commerçants, nous avons à notre disposition un nombre illimité de pièces de:

  • 1 centime
  • 2 centimes
  • 5 centimes
  • 10 centimes
  • 20 centimes
  • 50 centimes
  • 1 €
  • 2 €

Nous devons rendre la monnaie à un client à l’aide de ces pièces. La contrainte est d’utiliser le moins de pièces possible.

  1. Trouvez une méthode gloutonne permettant d’effectuer un rendu de monnaie (en utilisant le moins possible de pièces).
  2. Vous devez rendre la somme de 2,63 €, appliquez la méthode que vous venez de mettre au point.
  3. Combien de pièces avez-vous utilisées ?