N.S.I. WorkSpace Compétence,Notions,P-Th-G,Première G5 – Algorithmes gloutons

G5 – Algorithmes gloutons

Définition

Le principal avantage d’un algorithme glouton est sa facilité de mise en œuvre.
Un algorithme glouton fournit un résultat à un problème posé, généralement un problème d’optimisation:
dans certaines situations dites canoniques, il s’agit de la meilleure des solutions optimales ;
mais dans d’autres situations, la réponse apportée tout en étant optimale, n’est pas nécessairement la meilleure des solutions optimales.

La recherche d’une solution est obtenue en effectuant successivement des choix locaux, jamais remis en cause.
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.

Écrire des algorithmes gloutons

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 il est convenu que le terme « pièce » désignent indifféremment les véritables pièces que les billets.
Supposons qu’un achat induise un rendu de 49€.
Quelles pièces peuvent être rendues?
La réponse, bien qu’évidente, n’est pas unique. Quatre pièces de 10€, 1 pièce de 5€ et deux pièces de 2€ conviennent.
Mais une pièce de 5 € et vingt-deux pièces de 2€ ou encore quarante-neuf pièces de 1€ conviennent également !
Si la question est de rendre la monnaie avec un minimum de pièces, le problème change de nature.
Mais la réponse reste simple : c’est la première solution proposée.

Toutefois, comment parvient-on à un tel résultat ?
Quels choix ont été faits qui optimisent le nombre de pièces rendus ?

C’est le problème du rendu de monnaie dont la solution dépend du système de monnaie utilisé.

On dispose d’un système monétaire comportant les pièces ayant les valeurs suivantes : 10, 5, 2 et 1.
Un commerçant doit rendre la somme de : 9.
Quel est le plus petit nombre de pièces qu’il peut rendre ?
Et s’il doit rendre 23 ?

Pour résoudre ce problème, toute personne sans s’en rendre compte met en œuvre un algorithme glouton :
choix : elle choisit d’abord la pièce dont la valeur est immédiatement inférieure à celle du montant à rendre, soit 5 pour 9 et 10 pour 23 ;
résolution d’une partie du problème : elle effectue un calcul : soustraction de la valeur de la pièce choisie du montant à rendre ( 1 pièce de 5) ou division du montant à rendre par la valeur de la pièce choisie (2 pièces de 10) ;
résolution du reste du problème : le problème est maintenant de rendre respectivement 4 et 3 : elle réitère les étapes précédentes jusqu’à ce que le montant à rendre soit égal à zéro.

ALGORITHME "rendu de monnaie : solution 1"

SOIT :
* s un système monétaire
* n le rang d'une valeur de s
* v la valeur de rang n
* m un montant à rendre

DEBUT
    n PREND LA VALEUR 1
    TANT QUE m EST DIFFÉRENT DE zéro (0)
        FAIRE la DIVISION ENTIÈRE de m par v
        AFFICHER le quotient de cette division
        m PREND LA VALEUR du reste de cette division
        INCRÉMENTER la valeur de n
    FIN TANT QUE
FIN
ALGORITHME "rendu de monnaie : solution 2"

SOIT :
* s un système monétaire
* n le rang d'une valeur de s
* v la valeur de rang n
* m un montant à rendre

DEBUT
    n PREND LA VALEUR 1
    TANT QUE m EST DIFFÉRENT DE zéro (0)
        SI m EST SUPÉRIEUR OU ÉGAL A v
            SOUSTRAIRE v de m
            AFFICHER v
            m PREND LA VALEUR du résultat de cette soustraction
        SINON
            INCRÉMENTER la valeur de n
    FIN TANT QUE
FIN

Notons que ces algorithmes ne peuvent aboutir à une solution optimale que si :
les valeurs des pièces du système monétaire sont triées par valeurs décroissantes ;
la plus petite valeur du système monétaire est l’unité (valeur 1).

Considérons maintenant le système monétaire suivant : 30, 24, 12, 6, 3, 1, et le montant à rendre : 49.
Quelle est la solution fournie par les algorithmes précédents ?
Est-ce la solution optimale ? Justifier la réponse.