Algorithme glouton

• Un algorithme glouton tente d'optimiser chaque étape de résolution d'un problème.
• Un algorithme exhaustif essaie toutes les possibilités pour trouver la meilleure.

L'exemple présenté ici vise à montrer les différences fondamentales entre ces deux algorithmes :

• Le temps d'exécution
• La réussite à trouver une solution optimale.

Il s'agit dans cet exemple de rendre de la monnaie avec un minimum de pièces.

Pour les besoins de la démonstration, des pièces n'existant pas réellement, comme des pièces de 3 ou 4 €, peuvent être utilisées.
Pour information, on utilise des pièces de 25 cent aux États-Unis où des pièces de 3 cent ont circulé entre 1851 et 1873.
Il a également existé des pièces de 3 roubles et 3 kopecks en Russie, 3 lei et 3 banis en Roumanie.

Pour rendre les temps de calcul raisonnable, le nombre maximal de pièces utilisées est limité à 7 pour l'algorithme exhaustif.

Questions :

1. Quel est l'algorithme le plus rapide ? pourquoi ?
2. Tester la configuration suivante : rendre 6 € avec des pièces de 4€, 3€ et 50 cent. Que remarque-t-on ?
3. Les deux algorithmes proposés sont-ils toujours optimaux ?
4. Combien de cycles de calculs sont nécessaires pour trouver une solution à partir de 8 pièces différentes en utilisant au maximum 7 pièces avec un algorithme exhaustif ?
5. Le système monétaire européen est-il toujours optimal pour l'algorithme glouton ? pourquoi ? (aide : preuve avec des sommes de 1 à 10 cent)
6. A votre avis, quel est l'algorithme utilisé dans les systèmes automatiques de rendu de monnaie (boulangerie, péage autoroutier, distributeur de boissons...) ? pourquoi ?
7. Décrire le fonctionnement de l'algorithme glouton dans le cas présenté.
8. Pourquoi est-il conseillé de ne pas utiliser plus de 10 pièces différentes ?

Auteur : Laurent Thumser

Choisir parmi les pièces ci-dessous, celle qui peuvent être utilisées pour rendre la monnaie (ne pas utiliser plus de 10 pièces !) :