Algorithme glouton
.
Généralités
.
Optimiser un problème, c’est déterminer les conditions dans lesquelles ce problème présente une caractéristique spécifique. Par exemple, déterminer le minimum ou le maximum d’une fonction est un problème d’optimisation. On peut également citer la répartition optimale de tâches suivant des critères précis, 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. De nombreuses techniques informatiques sont susceptibles d’apporter une solution exacte ou approchée à ces problèmes. Certaines de ces techniques, comme l’énumération exhaustive de toutes les solutions, ont un coût machine qui les rend souvent peu pertinentes au regard de contraintes extérieures imposées (temps de réponse de la solution imposé, moyens machines limités).
Les techniques de programmation dynamique ou d’optimisation linéaire, certaines algorithmes numériques peuvent apporter une solution. Les algorithmes gloutons constituent une alternative dont le résultat n’est pas toujours optimal. Plus précisément, ces algorithmes déterminent une solution optimale 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. Une différence essentielle avec la programmation dynamique est que celle-ci peut remettre en cause des solutions déjà établies. Au lieu de se focaliser sur un seul sous-problème, elle explore les solutions de tous les sous-problèmes pour les combiner finalement de manière optimale.
Le principal avantage des algorithmes gloutons est leur facilité de mise en œuvre.
.
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\) .
.
Programme en python
.
