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

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

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.

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 glouton

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 ! 🎓