[NSI] Qu’est ce qu’un 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 :

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 :

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 !

JE PRENDS 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.

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

Tous nos profs sont passés par les meilleures écoles de France !

J’EN PROFITE !

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.

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