Python

Les algorithmes gloutons sont une partie très concrète du programme de Python. En effet, ils cherchent à résoudre un véritable problème d’optimisation classique et sont utilisés dans plusieurs entreprises et administrations. Pour résoudre un problème et te permettre de trouver une solution optimale, il faut parfois que tu passes en revue toutes les possibilités afin de choisir la meilleure. Cependant cette méthode peut être longue et fastidieuse. C’est là qu’interviennent les algorithmes gloutons : ils te permettent de trouver une solution obtenue par « optimisations successives ». En revanche, cette solution n’est pas toujours la plus adaptée, car les algorithmes gloutons optimisent la résolution du problème étape par étape.

Exemples de problèmes

  • Répartition optimale d’un emploi du temps avec plusieurs contraintes (salle, professeurs, classes…).
  • Rendre de la monnaie avec le moins de pièces possible.
  • Le « problème du sac à dos », qui consiste à vouloir remplir un sac à dos avec des objets plus ou moins utiles, en prenant en compte les dimensions et le poids du sac.
  • La recherche du plus court chemin dans un graphe (qui nécessite la compréhension de la notion de graphe, que tu pourras retrouver dans cet article).

Explication de la méthode gloutonne

Avant, il est nécessaire que je te fasse une rapide présentation de la méthode gloutonne et des trois caractéristiques qui la composent.

Tout d’abord, la méthode gloutonne résout étape par étape et au fur et à mesure un problème déterminé, ce qui fait que le problème devient de plus en plus « petit ». Ensuite, l’algorithme construit la solution finale en additionnant les solutions intermédiaires trouvées à chaque étape. Enfin, lorsqu’il effectue un choix à l’étape n, il ne peut plus le modifier à l’étape n+1. On dit alors qu’il n’y a pas de rétroaction possible.

Dans ce cas, tu pourrais te demander : pourquoi utilise-t-on cette méthode si elle n’est pas toujours optimale ? On l’utilise, car ces types d’algorithmes sont faciles à mettre en place et peu coûteux en temps. Ils sont très utiles pour automatiser certaines tâches, comme celles présentées précédemment. Le principal inconvénient reste qu’ils ne permettent pas toujours de trouver la meilleure solution.

Je vais ainsi te présenter trois situations concrètes qui pourront te servir d’exercices types pour mieux appréhender cette notion et te permettre, par la suite, d’être capable de l’utiliser.

Présentation des différentes situations

Situation 1 : le rendu d’une monnaie

L’objectif ici est d’entrer comme argument une valeur à rendre. Puis, la fonction va être capable de renvoyer une liste de billets et de pièces égale à la valeur à rendre.

Remarque : il est important que tu précises le système de monnaie, c’est-à-dire s’il existe des billets de 5, 10, 20, 50, 100, etc. (et de la même manière pour les pièces).

Voici les six étapes pour réaliser un programme glouton permettant de résoudre ce problème :

  1. On crée une liste « liste_rendu » vide qui permettra d’inscrire les différents billets et pièces rendus.
  2. On parcourt le système de monnaie en partant du plus grand au plus petit (de 500 € à 1 €).
  3. Tant que la somme à rendre est supérieure à la valeur inscrite sur le billet (ou la pièce, en fonction de l’étape à laquelle est la boucle)…
  4. On rajoute à la liste le billet (ou la pièce) sélectionné(e).
  5. On soustrait la valeur du billet à la somme.
  6. On renvoie finalement la liste des pièces et billets à rendre.


Exemple

Avec le système de monnaie : euro = [500, 200, 100, 50, 20, 10, 5, 2, 1], si tu renvoies la fonction rendu_monnaie(127,euro), tu obtiens [100, 20, 5, 2].

Remarque : si le système n’est pas optimal, alors le programme ne va pas toujours chercher à renvoyer le minimum de pièces. Par exemple, si le système de monnaie ne contient que des billets de 60 € et des pièces de 1 € et qu’on lui demande de rendre 100 €, il va bien rendre un billet de 60 € et 40 pièces de 1 €.

Situation 2 : remplir un sac à dos

On dispose d’un sac à dos qui peut contenir maximum 30 kg ainsi que de quatre objets notés respectivement A, B, C et D et dont les caractéristiques sont les suivantes :

A pèse 15 kg et coûte 80 €

B pèse 13 kg et coûte 60 €

C pèse 8 kg et coûte 40 €

D pèse 6 kg et coûte 15 €

Comme je te l’ai évoqué précédemment, la méthode gloutonne va prendre successivement l’objet qui coûte le plus cher et qui peut rentrer dans le sac.

Voici les cinq étapes pour réaliser un programme glouton permettant de résoudre ce problème :

  1. Tu crées une liste de listes « L » contenant l’ensemble des caractéristiques de chaque objet, c’est-à-dire le nom, le poids et le prix, rangées dans l’ordre croissant.
  2. Tu définis une fonction « sac_a_dos(L,Max) », sachant que, lors de l’appel de la fonction, Max représente la capacité maximale du sac à dos.
  3. Tu crées une liste vide rangement, qui va contenir les différents éléments du sac à dos.
  4. Tu crées deux variables initialisées à 0 qui vont par la suite contenir le poids du sac à dos et la valeur de ce qu’il contient.
  5. Tu crées une boucle qui va parcourir la liste « L » et qui vérifie si l’objet rentre dans le budget et permet de ne pas dépasser le poids, dans ce cas elle l’ajoute dans la liste rangement.

Exemple

Avec la liste : L=[[“A”,13,70],[“B”,12,60],[“C”,8,50],[“D”,6,30]], si tu renvoies la fonction sac_a_dos_range(L,30), tu obtiens ([‘A’, ‘B’], 140).

Situation 3 : allocation d’une salle de conférence

Plusieurs réunions doivent avoir lieu le même jour, mais les collaborateurs imposent chacun une heure de début et une heure de fin qui doivent être respectées. Il faut donc trouver une solution pour qu’un maximum de réunions puissent se dérouler au cours de la journée.

Voici les quatre étapes pour réaliser un programme glouton permettant de résoudre ce problème :

  1. Tu crées une fonction « choix_de_reunion(C) » avec C étant une liste de listes comprenant les différentes réunions rangées dans l’ordre de celle qui commence le plus tôt à celle qui finit le plus tard.
  2. Tu crées une liste vide qui va accueillir les conférences choisies.
  3. Tu crées une variable initialisée à 0 qui va prendre comme argument successif l’horaire de fin de chaque réunion.
  4. Tu crées une boucle qui va ajouter à la liste initialement vide un arrangement optimal et dans l’ordre des réunions qui doivent se tenir pour qu’un maximum de réunions ait lieu.

Exemple 

Avec la liste de conférence : C=[[8,9,“C1”], [8.45,10.3,“C2”], [8.1,11.3,“C3”], [11.15,11.45,“C4”], [12,12.45,“C5”], [11,13,“C6”], [12.3,14,“C7”], [16,17,“C8”]], si tu renvoies la fonction choix_de_reunion(C), tu obtiens [‘C1’, ‘C4’, ‘C5’, ‘C8’].

Conclusion

Les algorithmes gloutons offrent une méthode rapide et simple pour résoudre des problèmes d’optimisation. Bien qu’ils ne garantissent pas toujours la solution optimale, ils permettent d’obtenir un résultat satisfaisant en un temps réduit. N’hésite pas à t’entraîner sur des annales dès que possible. Tu peux retrouver de manière plus générale tous les articles de maths ici !

Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !