{"id":189945,"date":"2021-07-08T13:22:35","date_gmt":"2021-07-08T11:22:35","guid":{"rendered":"https:\/\/sherpas.com\/blog\/algorithme-glouton\/"},"modified":"2025-01-07T17:37:25","modified_gmt":"2025-01-07T16:37:25","slug":"algorithme-glouton","status":"publish","type":"post","link":"https:\/\/sherpas.com\/blog\/algorithme-glouton\/","title":{"rendered":"[NSI] Qu\u2019est ce qu\u2019un algorithme glouton ? \ud83d\ude0b"},"content":{"rendered":"\n

Tu es curieux de savoir ce qu\u2019est un algorithme glouton ? Tu n\u2019as pas bien compris ton cours de NSI ? Ne t’inqui\u00e8te pas, nous sommes l\u00e0 pour t\u2019aider \u00e0 comprendre ce concept fondamental en informatique. <\/p>\n\n\n\n

Dans les probl\u00e8mes o\u00f9 l\u2019on a un syst\u00e8me dont on doit minimiser ou maximiser une caract\u00e9ristique, les algorithmes gloutons sont efficaces. \ud83d\udcaa<\/strong><\/p>\n\n\n\n

Passons tout de suite aux explications.<\/p>\n\n\n\n

Qu\u2019est-ce qu\u2019un algorithme glouton ? \ud83e\uddd0<\/h2>\n\n\n\n

La d\u00e9finition d’un algorithme glouton <\/h3>\n\n\n\n

\ud83d\udc49 Un algorithme glouton est un algorithme qui suit un principe permettant de trouver un optimum local. Par cela, il esp\u00e8re atteindre une solution optimale globale (du probl\u00e8me).<\/strong> Tu as l\u2019impression que je parle une autre langue ? Allons plus en d\u00e9tail avec un exemple.<\/p>\n\n\n\n

Prenons le tableau :
\n<\/p>\n\n\n\n\n\n\n\t\n\n\t\n\t
D\u00e9but<\/th>2<\/th>\n<\/tr>\n<\/thead>\n
3<\/td>5<\/td>\n<\/tr>\n
1<\/td>Fin<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

L\u2019objectif de ce probl\u00e8me est de rejoindre la case \u201cD\u00e9but\u201d \u00e0 la case \u201cFin\u201d en ayant un co\u00fbt de passage le plus faible (addition des chiffres dans les cases). Les d\u00e9placements autoris\u00e9s sont verticaux et horizontaux. Le chemin optimal est : D\u00e9but \u2192 3 \u2192 1 \u2192 Fin, avec un co\u00fbt de 4. <\/strong><\/p>\n\n\n\n

Pour autant, on pourrait construire l\u2019algorithme glouton cherchant \u00e0 chaque \u00e9tape le co\u00fbt minimal. Il ferait donc : D\u00e9but \u2192 2 \u2192 5 \u2192 Fin, avec un co\u00fbt de 7. Ce chemin n\u2019est pas le chemin optimal\u2026 \ud83d\ude25
\n <\/p>\n\n\n\n

Pourquoi choisir un algorithme glouton ?<\/h3>\n\n\n\n

Mais alors, pourquoi choisir un algorithme glouton ? Car les algorithmes gloutons ont une complexit\u00e9 plus faible.<\/strong> En effet, pour trouver dans l\u2019exemple ci-dessus le chemin optimal, l\u2019algorithme de recherche fonctionnera comme un arbre. En moyenne, il mettra plus de temps \u00e0 donner la solution. <\/strong><\/p>\n\n\n\n

Parfois l\u2019algorithme glouton peut donner la solution optimale, par exemple avec ce tableau et la m\u00eame r\u00e8gle que l\u2019on a utilis\u00e9e pr\u00e9c\u00e9demment :<\/p>\n\n\n\n\n\n\n\t\n\n\t\n\t
D\u00e9but<\/th>2<\/th>\n<\/tr>\n<\/thead>\n
3<\/td>1<\/td>\n<\/tr>\n
2<\/td>Fin<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

L\u2019algorithme glouton ferait : D\u00e9but \u2192 2 \u2192 1 \u2192 Fin. <\/p>\n\n\n\n

\ud83d\udc49 Pour autant, sans une autre v\u00e9rification, on ne peut pas conclure \u00e0 l\u2019optimalit\u00e9 d\u2019un chemin si on utilise un algorithme glouton. Il trouvera une solution au probl\u00e8me, mais celle-ci ne sera pas forc\u00e9ment la meilleure.<\/strong><\/p>\n\n\n

\n
\n \n
\n
\n
\n \"Logo\n <\/div>\n
\n
\n
\n
\n \n <\/div>\n

Fabien<\/p>

T\u00e9l\u00e9com Paris<\/p>

\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

20\u20ac\/h<\/p> <\/div>\n <\/div>\n

\n
\n \n <\/div>\n

Nicolas<\/p>

CentraleSup\u00e9lec<\/p>

\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

17\u20ac\/h<\/p> <\/div>\n <\/div>\n

\n
\n \n <\/div>\n

Louise<\/p>

Mines ParisTech<\/p>

\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

24\u20ac\/h<\/p> <\/div>\n <\/div>\n

\n
\n \n <\/div>\n

Fanny<\/p>

Ponts ParisTech<\/p>

\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n \n \n <\/svg>\n <\/div>\n

19\u20ac\/h<\/p> <\/div>\n <\/div>\n <\/div>\n <\/div>\n<\/div>\n

\n
\n \"Logo\n <\/div>\n

Besoin d’un prof particulier<\/span> d’informatique ? \u2728<\/span><\/p>\n<\/div>\n

Nos Sherpas sont l\u00e0 pour t’aider \u00e0 progresser et prendre confiance en toi !<\/p>\n<\/div>\n

\n \n JE PRENDS UN COURS OFFERT !\n <\/div>\n <\/div>\n <\/div>\n <\/div>\n <\/div>\n <\/section>\n\n\n\n

Exemple d\u2019un algorithme glouton : le rendu de monnaie \ud83d\udcb8<\/h2>\n\n\n\n

Explication de l’exemple du rendu de monnaie<\/h3>\n\n\n\n

L\u2019exemple principal sur les algorithmes gloutons du programme se base sur une situation d\u2019achat d\u2019un produit en esp\u00e8ces (pi\u00e8ces et billets) et du rendu de monnaie. \ud83d\udcb0<\/strong><\/p>\n\n\n\n

Tu vas dans une boulangerie acheter un g\u00e2teau pour l\u2019anniversaire d\u2019un de tes parents. Soit X le prix de ce g\u00e2teau. Afin de le payer, tu disposes dans ton portefeuille de pi\u00e8ces et de billets de 1, 2, 5, 10, 20 et 50 euros. Tu souhaites toujours avoir un maximum de pi\u00e8ces et de billets sur toi, tu vas donc essayer de payer le g\u00e2teau avec le plus petit nombre de pi\u00e8ces et de billets. <\/p>\n\n\n\n

Un algorithme glouton dans cette situation serait de : trouver la pi\u00e8ce ou le billet le plus grand qui soit inf\u00e9rieur au prix X, puis de r\u00e9p\u00e9ter l\u2019op\u00e9ration jusqu\u2019\u00e0 arriver \u00e0 0. <\/strong><\/p>\n\n\n\n

Par exemple, si le g\u00e2teau co\u00fbte 23\u20ac, l\u2019algorithme va chercher le plus grand billet inf\u00e9rieur \u00e0 23\u20ac : c\u2019est le billet de 20\u20ac. Il reste alors 3\u20ac. La pi\u00e8ce la plus grande, mais inf\u00e9rieure \u00e0 3\u20ac est la pi\u00e8ce de 2\u20ac. Il reste 1\u20ac. Tu paieras donc avec un billet de 20\u20ac, une pi\u00e8ce de 2\u20ac et une pi\u00e8ce de 1\u20ac.
\n <\/p>\n\n\n\n

Le code Python simplifi\u00e9 de l’exemple du rendu de monnaie<\/h3>\n\n\n\n

\ud83d\udc49 En python, on pourrait \u00e9crire cet algorithme avec la fonction renduMonnaie ci-dessous : <\/strong>
\n<\/code>\n<\/code><\/p>\n\n\n\n

def renduMonnaie(prix: int) : \n\tportefeuille = [50,20,10,5,2,1]  \n\ti = 0                             \n\ta_rendre = []             \n        k=0                        \n\t\n\twhile(prix>0) :      \n\t\tif(portefeuille[i]>prix) :     \n\t\t\ti = i+1              \n\t\telse :                     \n\t\t\ta_rendre[k] = portefeuille[i] \n\t\t\tk = k+1                      \n\t\t\tprix = prix-portefeuille[i]  \n\treturn a_rendre               \n<\/code><\/pre>\n\n\n\n
Cette fonction prend en valeur d\u2019entr\u00e9e un entier (le prix) et renvoie en sortie un tableau d\u2019entiers comprenant les billets et pi\u00e8ces \u00e0 utiliser pour payer ce prix. <\/strong><\/p>\n\n\n\n
Le tableau \u00ab\u00a0portefeuille\u00a0\u00bb comprend les valeurs de nos pi\u00e8ces et billets. \u00ab\u00a0a_rendre\u00a0\u00bb sera le tableau renvoy\u00e9 en fin de fonction. Les variables \u00ab\u00a0i\u00a0\u00bb et \u00ab\u00a0k\u00a0\u00bb vont nous permettre d’incr\u00e9menter la boucle While et de se d\u00e9placer dans \u00ab\u00a0a_rendre\u00a0\u00bb.<\/p>\n\n\n\n
La boucle \u00ab\u00a0While\u00a0\u00bb (tant que) marche tant que le prix est sup\u00e9rieur \u00e0 0. En effet, le prix est diminu\u00e9 \u00e0 chaque occurence de la boucle si le billet\/pi\u00e8ce (i-\u00e8me case de \u00ab\u00a0portefeuille\u00a0\u00bb) est inf\u00e9rieur au prix (le \u00ab\u00a0else\u00a0\u00bb). Dans ce cas, on ajoute le billet\/pi\u00e8ce \u00e0 \u00ab\u00a0a_rendre\u00a0\u00bb et on incr\u00e9mente \u00ab\u00a0k\u00a0\u00bb pour que le prochain billet\/pi\u00e8ce soit mis dans la case suivante du tableau.<\/p>\n\n\n\n
Sinon, si le billet\/pi\u00e8ce est sup\u00e9rieur au prix, on incr\u00e9mente \u00ab\u00a0i\u00a0\u00bb. Cela permet de changer le billet\/pi\u00e8ce \u00e0 comparer au prix. On rep\u00e8te ces op\u00e9rations tant que le prix est sup\u00e9rieur \u00e0 0. <\/p>\n\n\n\n
Avec ce code simplifi\u00e9, on suppose que les prix pr\u00e9sent\u00e9s sont d\u00e9nombrables \u00e0 partir des pi\u00e8ces et billets de notre portefeuille.<\/strong><\/p>\n\n\n\n
Exercice suppl\u00e9mentaire : complexifie l\u2019algorithme ! \ud83e\udd2f<\/h3>\n\n\n\n
\ud83d\udca1 Si tu te sens \u00e0 l\u2019aise avec la premi\u00e8re solution, je te conseille d\u2019essayer de complexifier l\u2019algorithme afin de jongler avec les notions de python, tout en conservant bien en t\u00eate l\u2019objectif de ton algorithme glouton sur ce probl\u00e8me de rendu de monnaie.<\/strong><\/p>\n\n\n
\n
\"algorithme
\u00c0 toi de coder !<\/figcaption><\/figure>\n<\/div>\n\n\n
Par exemple, tu pourrais changer la boucle While par une boucle For<\/strong>. Tu peux aussi ajouter de nouveaux billets et pi\u00e8ces. Si tu ne souhaites pas utiliser de centimes, tu pourrais essayer de trouver la meilleure approximation en utilisant des divisions euclidiennes<\/strong>. <\/p>\n\n\n\n
Enfin, tu pourrais instaurer un dialogue avec l\u2019utilisateur<\/strong> qui va renseigner \u00e0 la fois le prix du g\u00e2teau et le type de pi\u00e8ces qu\u2019il a dans son porte-monnaie. \ud83d\ude09<\/p>\n\n\n\n
Pour finir, une derni\u00e8re version un peu plus complexe consisterait en cr\u00e9ant un portefeuille sous forme de matrice<\/strong> de telle sorte qu\u2019il y ait un nombre limit\u00e9 de chaque valeur de pi\u00e8ces.  <\/p>\n\n\n
\n        
\n            \n                                                
\n                                                                        
\n    
\n        \"Logo\n    <\/div>\n    
\n        
\n                                            
\n                    
\n                        \n                    <\/div>\n                         
Margot<\/p>                          
Arts et M\u00e9tiers ParisTech<\/p>                                                     
\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
22\u20ac\/h\/h<\/p>                     <\/div>\n                <\/div>\n                                            
\n                    
\n                        \n                    <\/div>\n                         
Bastien<\/p>                          
Polytechnique<\/p>                                                     
\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
26\u20ac\/h<\/p>                     <\/div>\n                <\/div>\n                                            
\n                    
\n                        \n                    <\/div>\n                         
Hugo<\/p>                          
Insa Lyon<\/p>                                                     
\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
16\u20ac\/h<\/p>                     <\/div>\n                <\/div>\n                                            
\n                    
\n                        \n                    <\/div>\n                         
Thibault<\/p>                          
ENS Paris Ulm<\/p>                                                     
\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                                    \n                                        \n                                    <\/svg>\n                                                            <\/div>\n                                                 
20\u20ac\/h<\/p>                     <\/div>\n                <\/div>\n                    <\/div>\n    <\/div>\n<\/div>\n                                                    
\n                                                            
\n                                    \"Logo\n                                <\/div>\n                                                                                        
Ton premier cours particulier<\/span> d’informatique est offert<\/span> ! \ud83c\udf81<\/span><\/p>\n<\/div>\n                                                                                        
Tous nos profs sont pass\u00e9s par les meilleures \u00e9coles de France !<\/p>\n<\/div>\n                                                        
\n                                                                                                    \n                                        J\u2019EN PROFITE !\n                                    <\/div>\n                                                            <\/div>\n                                                    <\/div>\n                                    <\/div>\n                                    <\/div>\n    <\/section>\n\n\n\n
Algorithme glouton : la solution optimale ? \ud83e\udd29<\/h2>\n\n\n\n
\ud83d\udc49 Comme d\u00e9j\u00e0 dit pr\u00e9c\u00e9demment, un algorithme glouton ne conduit pas toujours \u00e0 une solution optimale globale. Pour autant, par d\u00e9finition il cherche une succession d\u2019optimum locaux.<\/strong><\/p>\n\n\n\n
Et, dans beaucoup de probl\u00e8mes, un bon algorithme glouton trouvera la solution optimale. Mais ce n\u2019est pas forc\u00e9ment le cas ! L\u2019avantage r\u00e9side surtout dans les temps de calcul largement inf\u00e9rieurs, car les diff\u00e9rents cas ne sont pas test\u00e9s. <\/strong><\/p>\n\n\n\n
Pour s\u2019assurer de l\u2019optimisation d\u2019une solution, la complexit\u00e9 de l\u2019algorithme utilis\u00e9 sera plus grande. Pour cela, plusieurs solutions algorithmiques existent, tu en verras certaines si tu poursuis tes \u00e9tudes d\u2019informatique !<\/p>\n\n\n\n
Pour aller plus loin, je vais t\u2019introduire \u00e0 un autre probl\u00e8me c\u00e9l\u00e8bre : le probl\u00e8me du sac \u00e0 dos.<\/strong> Consid\u00e8re un sac \u00e0 dos qui a une capacit\u00e9 de 20 kg. Et supposes que tu as 3 objets poss\u00e9dant chacun une masse et un prix.<\/p>\n\n\n\n\n\n\n\t\n\n\t\n\t
Objet<\/th>A<\/th>B<\/th>C<\/th>\n<\/tr>\n<\/thead>\n
Masse (kg)<\/td>7<\/td>18<\/td>3<\/td>\n<\/tr>\n
Prix (Euros)<\/td>13<\/td>20<\/td>6<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n
\ud83d\udc49 L\u2019objectif de ce probl\u00e8me est d\u2019avoir au final la plus grande valeur dans ton sac, sans que le poids des objets d\u00e9passe la capacit\u00e9 de ton sac.<\/strong> <\/p>\n\n\n\n
\ud83d\udca1 Plusieurs strat\u00e9gies gloutonnes sont faisables<\/strong>, les plus communes sont : <\/p>\n\n\n\n