NSI - Numérique et Sciences Informatiques
Algorithmes gloutons

Présentation des d'algorithmes gloutons avec exemples et TD.

1. Présentation de la notion d'algorithme glouton.
   1. Les problèmes d'optimisation.
   2. Résoudre un problème d'optimisation : les algorithmes gloutons
2. Le problème du rendu de monnaie.
3. Le TD sur les algorithmes gloutons et le rendu de monnaie.
4. Le problème du sac à dos.

1. Présentation de la notion d'algorithme glouton

Les problèmes d'optimisation

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble.

Les problèmes d'optimisation classiques sont par exemple : 

• la répartition optimale de tâches suivant des critères précis (emploi du temps avec plusieurs contraintes) ;
• le problème du rendu de monnaie ;
• le problème du sac à dos ;
• la recherche d’un plus court chemin dans un graphe ;
• le problème du voyageur de commerce.

Résoudre un problème d'optimisation : les algorithmes gloutons

De nombreuses techniques informatiques sont susceptibles d’apporter une solution exacte ou approchée à ces problèmes.

• Recherche de toutes les solutions
  La technique la plus basique pour résoudre ce type de problème d'optimisation consiste à énumérer de façon exhaustive toutes les solutions possibles, puis à choisir la meilleure. Cette approche par force brute, impose souvent un coût en temps trop important pour être utilisée.
      
• Les algorithmes gloutons
  Un algorithme glouton (greedy algorithm) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local.
  Au cours de la construction de la solution, l’algorithme résout une partie du problème puis se focalise ensuite sur le sous-problème restant à résoudre.
  La méthode gloutonne consiste à choisir des solutions locales optimales d'un problème dans le but d'obtenir une solution optimale globale au problème.
  • Le principal avantage des algorithmes gloutons est leur facilité de mise en œuvre.
  • Le principal défaut est qu'ils ne renvoient pas toujours la solution optimale nous le verrons.
  • Dans certaines situations dites canoniques, il arrive qu’ils renvoient non pas un optimum mais l’optimum d’un problème

 Top

2. Le problème du rendu de monnaie

Un achat dit en espèces se traduit par un échange de pièces et de billets. Dans la suite, les pièces désignent indifféremment les véritables pièces que les billets.

Supposons qu’un achat induise un rendu de 49 euros en considérant pour simplifier que les 'pièces' prennent les valeurs 1, 2, 5, 10, 20, 50, 100 euros. Quelles pièces peuvent être rendues ?

• \(49=4\times10+1\times 5 + 2\times2\) soit 7 pièces au total
  (Quatre pièces de 10 euros, 1 pièce de 5 euros et deux pièces de 2 euros.)
• ou \(49=9\times 5 + 2\times2\)  soit 11 pièces au total
• ou \(49=9\times 5 + 4\times1\)  soit 13 pièces au total
• ou \(49=49\times1\)  soit 49 pièces au total

Le problème du rendu de monnaie consiste à déterminier la solution avec le nombre minimal de pièces.

Rendre 49 euros avec un minimum de pièces est un problème d’optimisation. En pratique, tout individu met en œuvre un algorithme glouton.

1. Il choisit d’abord la plus grandeur valeur de monnaie, parmi 1, 2, 5, 10, 20 contenue dans 49 euros.
   En l’occurence, deux fois une pièce de 20 euros.
2. La somme de 9 euros restant à rendre, il choisit une pièce de 5 euros,
3. Puis deux pièces de 2 euros.

Solution optimale et système canonique du rendu de monnaie

Cette stratégie gagnante pour la somme de 49 euros l’est-elle pour n’importe quelle somme à rendre ?

• Un système canonique
  
  • On peut montrer que l'algorithme glouton du rendu de monnaie renvoie une solution optimale pour le système monétaire français
    $$\left \lbrace1 ,  2 , 5  , 10 , 20 , 50,100\right \rbrace$$
  • Pour cette raison, un tel système de monnaie est qualifié de canonique.
    
    
• Des systèmes non canoniques
  • D’autres systèmes ne sont pas canoniques. L’algorithme glouton ne répond alors pas de manière optimale.
  • Par exemple, avec le système \(\left \lbrace1 ,  3 , 6  , 12 , 24 , 30\right \rbrace\), l’algorithme glouton répond en proposant le rendu :
    \(49=30+12+6+1\) soit 4 pièces
    alors que la solution optimale est \(49=2\times24+1\), soit 3 pièces. 

  Top

3. Le TD sur les algorithmes gloutons et le rendu de monnaie

• Prérequis au TD

  • Python : liste, parcours de listes.
      

On cherche à implémenter un algorithme glouton de rendu de monnaie en ne considérant que des valeurs entières des pièces du système.
Par ailleurs, la plus petite pièce du système sera toujours 1, on est ainsi certain de pouvoir rendre la monnaie quelque soit la somme choisie.

Fonctionnement de l'algorithme glouton du rendu de monnaie

1. On choisit un système de monnaies, par exemple  $$systeme = \left \lbrace1 ,  2 , 5  , 10 , 20 , 50,100\right \rbrace$$
2. On choisit une valeur, par exemple \(valeur=49\) euros .
3. On choisit la plus grande 'pièce' du système inférieure à la valeur et on l'ajoute à la liste des pièces à rendre.
4. On calcule le reste à rendre et on recommence jusqu'à obtenir un reste à rendre nul.

Exercice 1

1. Ecrire une une fonction python qui reçoit deux arguments – la somme à rendre et le système de monnaie – et qui renvoie la liste des pièces choisies par l’algorithme glouton.
2. Tester votre fonction avec les valeurs et les systèmes proposés dans les exemples du cours ci-dessus.
3. Inventez un système non canonique différent de celui de l'exemple (mais toujours de valeur minimale 1) et trouver un exemple qui le prouve.
   Votre fonction devra donc donner une solution mais qui n'est pas optimale.
4. Complément : créer un programme (ou une autre fonction) qui va afficher toutes les informations suivantes :
   \(49=4\times10+1\times 5 + 2\times2\)
   Soit 7 pièces au total
   C'est à dire : Quatre pièces de 10 euros, 1 pièce de 5 euros et deux pièces de 2 euros.

Aide pour l'exercice 1

# valeurs des pièces du système choisi
systeme = [1,2,5,10,20,50,100]
# valeur à tester (par exemple 49 euros)
valeur=49
# indice de la première pièce à comparer à la somme à rendre
i = len(systeme) - 1

Exercice 2

• On cherche maintenant à généraliser notre algorithme avec le système de pièces et de billets utilisées en Europes et des valeurs décimales.
• On va donc considérer un système composé de pièces et de billets :
  • Les pièces (en euros) : 0,01 - 0,02  - 0,05 - 0,10 - 0,20 - 0,50 - 1 - 2 ;
  • Les billets (en euros)  : 5 - 10 - 20 - 50 - 100 - 200 - 500.

1. Modifier donc votre programme afin qu'il affiche le nombre les pièces à rendre et les billets.*
2.  Tester les avec plusieurs exemples.
3. Et si il n'y avait ni billet de 5, ni billet de 10 euros.
   Montrer avec un exemple bien choisi que la solution donnée par l'algorithme n'est pas optimale

Exercice 3 - Une pièce de 7 euros

• On peut se demander pourquyoi il n'y a pas de pièce de 7 euros par exemple.
• En fait c'est parce que si tel était le cas, l'algorithme glouton de rendu de monnaie ne serait plus optimal.

1. Tester votre algorithme en ajoutant une pièce de 7 euros dans le système.
2. Trouver un exemple qui renvoie une solution qui n'est pas optimale.

  Top

4. Le problème du sac à dos

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.

Remarque historique

Le problème du sac à dos est l'un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972. Il est intensivement étudié depuis le milieu du XXe siècle et on trouve des références dès 1897, dans un article de George Ballard Mathews. La formulation du problème est fort simple, mais sa résolution est plus complexe.

Description du problème du sac à dos et stratégies

On dispose d’un sac pouvant supporter un poids maximal donné et de divers objets ayant chacun une valeur et un poids.
Il s’agit de choisir les objets à emporter dans le sac afin d’obtenir la valeur totale la plus grande tout en respectant la contrainte du poids maximal.

Ce problème peut se résoudre parforce brute, c’est-à-dire en testant tous les cas possibles. Mais ce type de résolution présente un problème d’efficacité. Son coût en fonction du nombre d’objets disponibles croît de manière exponentielle.

Nous pouvons envisager une stratégie gloutonne. Le principe d’un algorithme glouton est de faire le meilleur choix pour prendrele premier objet, puis le meilleur choix pour prendre le deuxième, et ainsi de suite. Plusieurs stratégies sont possibles : 

• Prendre l’objet qui a la plus grande valeur ;
• Prendre l’objet qui a le plus petit poids ;
• Prendre l’objet qui a le rapport valeur/poids le plus grand.

Un TP sur problème du sac à dos

• Un tp est disponible : le problème du sac à dos.

Articles Connexes 

• NSI (Numérique et Sciences Informatiques) : réseaux