[NSI] Qu’est ce qu’un algorithme glouton ? 😋

Sofiane MaziĂšres - Mis Ă  jour le 08/07/2021
algorithme glouton

Tu es curieux de savoir ce qu’est un algorithme glouton ? Tu n’as pas bien compris ton cours de NSI ? Ne t’inquiĂšte pas, nous sommes lĂ  pour t’aider Ă  comprendre ce concept fondamental en informatique.

Dans les problĂšmes oĂč l’on a un systĂšme dont on doit minimiser ou maximiser une caractĂ©ristique, les algorithmes gloutons sont efficaces. đŸ’Ș

Passons tout de suite aux explications.

Qu’est-ce qu’un algorithme glouton ? 🧐

La dĂ©finition d’un algorithme glouton

👉 Un algorithme glouton est un algorithme qui suit un principe permettant de trouver un optimum local. Par cela, il espĂšre atteindre une solution optimale globale (du problĂšme). Tu as l’impression que je parle une autre langue ? Allons plus en dĂ©tail avec un exemple.

Prenons le tableau :

DĂ©but2
35
1Fin

L’objectif de ce problĂšme est de rejoindre la case “DĂ©but” Ă  la case “Fin” en ayant un coĂ»t de passage le plus faible (addition des chiffres dans les cases). Les dĂ©placements autorisĂ©s sont verticaux et horizontaux. Le chemin optimal est : DĂ©but → 3 → 1 → Fin, avec un coĂ»t de 4.

Pour autant, on pourrait construire l’algorithme glouton cherchant Ă  chaque Ă©tape le coĂ»t minimal. Il ferait donc : DĂ©but → 2 → 5 → Fin, avec un coĂ»t de 7. Ce chemin n’est pas le chemin optimal
 đŸ˜„
 

Pourquoi choisir un algorithme glouton ?

Mais alors, pourquoi choisir un algorithme glouton ? Car les algorithmes gloutons ont une complexitĂ© plus faible. En effet, pour trouver dans l’exemple ci-dessus le chemin optimal, l’algorithme de recherche fonctionnera comme un arbre. En moyenne, il mettra plus de temps Ă  donner la solution.

Parfois l’algorithme glouton peut donner la solution optimale, par exemple avec ce tableau et la mĂȘme rĂšgle que l’on a utilisĂ©e prĂ©cĂ©demment :

DĂ©but2
31
2Fin

L’algorithme glouton ferait : DĂ©but → 2 → 1 → Fin.

👉 Pour autant, sans une autre vĂ©rification, on ne peut pas conclure Ă  l’optimalitĂ© d’un chemin si on utilise un algorithme glouton. Il trouvera une solution au problĂšme, mais celle-ci ne sera pas forcĂ©ment la meilleure.

Fabien

Télécom Paris

20€/h

Nicolas

CentraleSupélec

17€/h

Louise

Mines ParisTech

24€/h

Fanny

Ponts ParisTech

19€/h

Besoin d’un prof particulier d’informatique ? ✹

Nos Sherpas sont lĂ  pour t’aider Ă  progresser et prendre confiance en toi.

PRENDRE UN COURS GRATUIT

Exemple d’un algorithme glouton : le rendu de monnaie 💾

Explication de l’exemple du rendu de monnaie

L’exemple principal sur les algorithmes gloutons du programme se base sur une situation d’achat d’un produit en espùces (piùces et billets) et du rendu de monnaie. 💰

Tu vas dans une boulangerie acheter un gñteau pour l’anniversaire d’un de tes parents. Soit X le prix de ce gñteau. Afin de le payer, tu disposes dans ton portefeuille de piùces et de billets de 1, 2, 5, 10, 20 et 50 euros. Tu souhaites toujours avoir un maximum de piùces et de billets sur toi, tu vas donc essayer de payer le gñteau avec le plus petit nombre de piùces et de billets.

Un algorithme glouton dans cette situation serait de : trouver la piĂšce ou le billet le plus grand qui soit infĂ©rieur au prix X, puis de rĂ©pĂ©ter l’opĂ©ration jusqu’à arriver Ă  0.

Par exemple, si le gĂąteau coĂ»te 23€, l’algorithme va chercher le plus grand billet infĂ©rieur Ă  23€ : c’est le billet de 20€. Il reste alors 3€. La piĂšce la plus grande, mais infĂ©rieure Ă  3€ est la piĂšce de 2€. Il reste 1€. Tu paieras donc avec un billet de 20€, une piĂšce de 2€ et une piĂšce de 1€.
 

Le code Python simplifiĂ© de l’exemple du rendu de monnaie

👉 En python, on pourrait Ă©crire cet algorithme avec la fonction renduMonnaie ci-dessous :

def renduMonnaie(prix: int) : 
	portefeuille = [50,20,10,5,2,1]  
	i = 0                             
	a_rendre = []             
        k=0                        
	
	while(prix>0) :      
		if(portefeuille[i]>prix) :     
			i = i+1              
		else :                     
			a_rendre[k] = portefeuille[i] 
			k = k+1                      
			prix = prix-portefeuille[i]  
	return a_rendre               

Cette fonction prend en valeur d’entrĂ©e un entier (le prix) et renvoie en sortie un tableau d’entiers comprenant les billets et piĂšces Ă  utiliser pour payer ce prix.

Le tableau « portefeuille » comprend les valeurs de nos piĂšces et billets. « a_rendre » sera le tableau renvoyĂ© en fin de fonction. Les variables « i » et « k » vont nous permettre d’incrĂ©menter la boucle While et de se dĂ©placer dans « a_rendre ».

La boucle « While » (tant que) marche tant que le prix est supérieur à 0. En effet, le prix est diminué à chaque occurence de la boucle si le billet/piÚce (i-Úme case de « portefeuille ») est inférieur au prix (le « else »). Dans ce cas, on ajoute le billet/piÚce à « a_rendre » et on incrémente « k » pour que le prochain billet/piÚce soit mis dans la case suivante du tableau.

Sinon, si le billet/piÚce est supérieur au prix, on incrémente « i ». Cela permet de changer le billet/piÚce à comparer au prix. On repÚte ces opérations tant que le prix est supérieur à 0.

Avec ce code simplifié, on suppose que les prix présentés sont dénombrables à partir des piÚces et billets de notre portefeuille.

Exercice supplĂ©mentaire : complexifie l’algorithme ! đŸ€Ż

💡 Si tu te sens Ă  l’aise avec la premiĂšre solution, je te conseille d’essayer de complexifier l’algorithme afin de jongler avec les notions de python, tout en conservant bien en tĂȘte l’objectif de ton algorithme glouton sur ce problĂšme de rendu de monnaie.

algorithme de glouton
À toi de coder !

Par exemple, tu pourrais changer la boucle While par une boucle For. Tu peux aussi ajouter de nouveaux billets et piĂšces. Si tu ne souhaites pas utiliser de centimes, tu pourrais essayer de trouver la meilleure approximation en utilisant des divisions euclidiennes.

Enfin, tu pourrais instaurer un dialogue avec l’utilisateur qui va renseigner à la fois le prix du gñteau et le type de piùces qu’il a dans son porte-monnaie. 😉

Pour finir, une derniĂšre version un peu plus complexe consisterait en crĂ©ant un portefeuille sous forme de matrice de telle sorte qu’il y ait un nombre limitĂ© de chaque valeur de piĂšces.  

Margot

Arts et MĂ©tiers ParisTech

22€/h/h

Bastien

Polytechnique

26€/h

Hugo

Insa Lyon

16€/h

Thibault

ENS Paris Ulm

20€/h

Ton premier cours particulier d’informatique est offert ! 🎁

Fais-toi guider par un étudiant passé par une des meilleures écoles de France.

J’EN PROFITE MAINTENANT

Algorithme glouton : la solution optimale ? đŸ€©

👉 Comme dĂ©jĂ  dit prĂ©cĂ©demment, un algorithme glouton ne conduit pas toujours Ă  une solution optimale globale. Pour autant, par dĂ©finition il cherche une succession d’optimum locaux.

Et, dans beaucoup de problĂšmes, un bon algorithme glouton trouvera la solution optimale. Mais ce n’est pas forcĂ©ment le cas ! L’avantage rĂ©side surtout dans les temps de calcul largement infĂ©rieurs, car les diffĂ©rents cas ne sont pas testĂ©s.

Pour s’assurer de l’optimisation d’une solution, la complexitĂ© de l’algorithme utilisĂ© sera plus grande. Pour cela, plusieurs solutions algorithmiques existent, tu en verras certaines si tu poursuis tes Ă©tudes d’informatique !

Pour aller plus loin, je vais t’introduire Ă  un autre problĂšme cĂ©lĂšbre : le problĂšme du sac Ă  dos. ConsidĂšre un sac Ă  dos qui a une capacitĂ© de 20 kg. Et supposes que tu as 3 objets possĂ©dant chacun une masse et un prix.

ObjetABC
Masse (kg)7183
Prix (Euros)13206

👉 L’objectif de ce problĂšme est d’avoir au final la plus grande valeur dans ton sac, sans que le poids des objets dĂ©passe la capacitĂ© de ton sac.

💡 Plusieurs stratĂ©gies gloutonnes sont faisables, les plus communes sont :

  • prendre l’objet avec la plus grande valeur n’excĂ©dant pas la capacitĂ© restante
  • prendre l’objet avec la plus faible masse
  • prendre l’objet avec le plus grand rapport valeur/masse n’excĂ©dant pas la capacitĂ© restante

Essaie d’appliquer ces 3 stratĂ©gies au problĂšme et trouve la meilleure dans ce cas. Compare les Ă  la solution optimale (2 objets A et 2 objets C faisant un prix de 38 euros et 20kg soit prĂ©cisĂ©ment la capacitĂ© du sac).

Tu peux Ă©videmment retravailler ce problĂšme en changeant les valeurs de masse et de prix des objets. Tu trouveras facilement des variantes avec leurs solutions sur internet.

Conclusion sur les algorithmes gloutons 👀

Tu connais donc maintenant les avantages et inconvĂ©nients des algorithmes gloutons. L’exemple du rendu de monnaie est au programme de NSI, Ă  toi de bien prendre le temps de le comprendre. N’hĂ©site pas Ă  le recoder sur ta machine ! đŸ’»

Globalement, les algorithmes gloutons sont efficaces dans les problĂšmes d’ordonnancement. Par exemple, pour Ă©valuer le chargement d’un sac en y mettant le moins d’objets. L’optimisation de la solution n’est pas garantie par les algorithmes gloutons.

👉 Bref, qu’on Ă©tudie le chargement d’un sac ou un rendu de monnaie, plusieurs solutions existent, et les stratĂ©gies gloutonnes proposent des approximations qualitatives et rapides.

Si tu souhaites trouver la solution optimale, l’utilisation d’un arbre de recherche sera nĂ©cessaire !

A bientĂŽt pour un nouvel article !

4.7/5 - (4 votes)
profile picture
Sofiane MaziĂšres
En 3ᔉ annĂ©e du Double Cursus INSA-Sciences Po Rennes, passionnĂ© par la musique, je suis rĂ©dacteur stagiaire chez les Sherpas. J’espĂšre que mes conseils t’aideront Ă  rĂ©ussir !

Laisse-nous un commentaire !

Des questions ? Des bons plans Ă  partager ? Nous validons ton commentaire et te rĂ©pondons en quelques heures ! 🎉

Ebook

Notre ebook pour t’aider au lycĂ©e

TĂ©lĂ©charge notre guide pour progresser et rĂ©ussir toutes les Ă©preuves au lycĂ©e ! 🎓