Imprimer
Affichages : 2175

Vote utilisateur: 5 / 5

Etoiles activesEtoiles activesEtoiles activesEtoiles activesEtoiles actives
 

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 : 

 

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.

 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 on 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 ?

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, contenue dans 49 euros.
    En l’occurence, quatre fois une pièce de 10 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.

rendu monnaie exemple

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 ?

  Top

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


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.

 rendu monnaie exemple

 

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.

 


  • Etape 1
    • Définissons le système de pièces à l’aide d’un tableau nommé  systeme constitué des valeurs des pièces classées par valeurs croissantes (de plus petite pièce 1).
    • On définit aussi une valeur à tester, les 49 euros de l'exemple ci-dessus, dans la variable valeur.
    • Ainsi que l'indice i de la plus grande des pièces de systeme.
# 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

 

  • Etape 2 : Fonctionnement de l'algorithme
    • On cherche à déterminer les pièces à rendre pour la variable valeur.
    • Initialisations
      • La somme à rendre à rendre est initialement stockée dans la variable somme_a_rendre. On l'initialise donc à  valeur.
      • liste_pieces, la liste des pièces à rendre est initialisée à une liste vide
      • i = len(systeme) - 1 : indice de la première pièce à comparer à la somme à rendre
    • On boucle tant que somme_a_rendre > 0
      • La variable piece prend la valeur de la pièce de systeme d'indice i
      • Si somme_a_rendre < piece
        • Alors i pend la valeur i-1
      • Sinon
        • alors on ajoute la piece à la liste des pièces à rendre liste_pieces
        • on enlève la valeur de piece de somme_a_rendre
    • On renvoie la liste : liste_pieces

 

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.

Knapsack PB Sac a dos algo glouton

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 : 

 

Un TP sur problème du sac à dos

 

 

Articles Connexes