Algorithme glouton :

Principe :

Le principe de l’algorithme glouton (greedy algorithm) :

 faire toujours un choix localement optimal dans l’espoir que ce choix mènera à une solution globalement optimale.

Exercice :

 Comment rendre la monnaie. Nous considérons des pièces de monnaie de 1, 2, et 5 centimes. Notons\(N\left( x \right)\)  le nombre minimum de pièces pour obtenir\(x\) centimes.

 Question 1 :

Quelle est la valeur de\(N\left( 0 \right),\ N\left( 1 \right),\ N\left( 2 \right),\ N\left( 3 \right),\ N\left( 4 \right),\ N\left( 5 \right)\)  ?

Correction

\(~N\left( 0 \right)\ = \ 0,\ N\left( 1 \right)\ = \ 1,\ N\left( 2 \right)\ = \ 2,\ N\left( 3 \right)\ = \ 2,\ N\left( 4 \right)\ = \ 2,\ N\left( 5 \right)\ = \ 1\)

Question 2 :

Donner un algorithme qui calcule\(N\left( x \right)\)  et sa complexité en termes d’opérations.

** Correction Algorithme Glouton :**

·        Trier les types de pièces par valeur décroissante.

·        Pour chaque valeur de pièce, maximiser le nombre de pièces choisies.

Plus formellement, soit  \(R\)  la somme restante, initialisé à\(S\) .

 Pour chaque valeur\(~v_{i}\)  ,\(c_{i} = \frac{\left( {R - R{mod}\,\,\, v_{i}} \right)}{v_{i}}\) , on prend \(c_{i}\) pièces\(v_{i}\)

Et on pose   \(\left. R\leftarrow R - v_{i} \times c_{i} \right.\)

Pour prouver l’optimalité de l’algorithme glouton avec les valeurs\(5,2\)  et\(1\) :

·        Au plus une pièce de\(1\)  (sinon une de\(2\) )

·        Au plus deux pièces de\(2\)  (sinon une de\(5\)  et une de\(1\) )

·        Le nombre de pièces de\(5\) est donc\(\frac{x - x{mod}5}{x}\)

·        Conclure avec ce qui précède

Question 3 :

 Appliquer cet algorithme qui calcule\(N\left( 14 \right)\)  en considérant maintenant qu’on dispose des pièces de monnaies de\(1,\text{~5}\)  et\(10\)  centimes. Que constatez-vous ?

Correction :

Si on utilise l’algorithme précédent, alors on utilise une pièce de\(10\)  et quatre pièces de\(1\) .