Vous êtes sur une version archivée de lyceum.fr de l'année 2022/2023. Revenir au présent.
Programme Officiel
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.

Lien vers le programme complet

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.

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

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!).

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

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

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 ?