Chapitre16
Algorithmes gloutons
16.1 Concepts généraux - Définition
Un algorithme glouton (greedy algorithm en anglais) est un algorithme qui suit le principe de faire,
étape par étape, un choix optimum local dans l’espoir d’obtenir un résultat optimum global.
Des fois l’algorithme glouton correspond à la solution optimale d’un problème, mais souvent ce n’est
pas le cas. Il s’agit alors d’un compromis, sans être la solution idéale, l’algorithme glouton apporte une
solution proche de celle-ci et dans un temps raisonnable. C’est donc une méthode pour trouver des
solutions aux problèmes d’optimisation d’un algorithme.
16.2 Un exemple : le voyageur de commerce
Un employeur impose a son représentant de commerce, basé à Périgueux, de voyager dans quatre
villes voisines : Bordeaux, Guéret, Toulouse et Clermont-Ferrand et que cela lui coûte le moins cher
possible afin de minimiser les coûts. Cela revient donc à minimiser la distance totale parcourue par le
voyageur. Si le représentant par de Périgueux, il souhaite bien évidemment y revenir à la fin.
Périgueux Bordeaux Guéret Toulouse Clermont-F.
Périgueux 137 245 274 251
Bordeaux 137 297 245 375
Guéret 245 297 374 177
Toulouse 274 245 374 376
Clermont-F. 251 375 177 376
Le problème se ramène à trouver un ordre de visite des quatre villes pour lequel la somme des
distances données est aussi petite que possible. Pour vous montrer à quel point cela peut-être fastidieux,
vous le ferez dans le premier exercice de la liste en fin de chapitre. Cela devient inenvisageable pour
une liste de quelques villes supplémentaires. Pour vous donner un ordre d’idée, pour 15 villes à visiter
il y a 43 milliards de possibilités, à partir de 71 villes, il y a plus de combinaisons que d’atomes dans
l’Univers !
La stratégie de l’algorithmie gloutonne appliquée à ce problème est de dire qu’une fois dans une
ville, le meilleur choix pour la prochaine ville est d’aller à celle qui est le plus près.
La solution obtenue n’est pas celle qui est l’idéale, le chemin le plus court réel est différent. Toutefois, la
solution obtenue est plutôt correcte pour le problème posé (on ne trouve pas la route la plus longue !),
et surtout elle a été trouvée très rapidement sans passer en revue toutes les solutions possibles. Voir
deuxième exercice de la liste et comparer le temps que cela vous a pris par rapport à faire le premier.
16.3 Problème du rendu de monnaie
Dans certains cas, la stratégie gloutonne donne toujours la solution idéale. Le système de monnaie
de l’euro a d’ailleurs était découpé afin de satisfaire ce problème : les valeurs des billets et des pièces
en circulation ont été choisies pour cela.
92
Spécialité NSI 2024-2025
Le problème est celui d’un commerçant qui doit rendre la monnaie a un de ses clients. Par exemple
le produit acheté vaut 11e et le client paie avec un billet de 20e. Le commerçant doit lui rendre 9e,
mais comment doit-il s’y prendre en utilisant le moins de billets et de pièces ?
L’approche gloutonne de ce problème et de dire qu’il doit donner la plus grande valeur possible et le
maximum de fois possibles avant de passer à la valeur inférieure.
Dans ce cas concret, cela suppose que le marchand possède à sa disposition toutes les valeurs de pièces
et de billets possibles. (Laissons les centimes de côté volontairement.)
Etape Encore à rendre Utilisé
1 9 1 billet de 5e
2 4 1 pièce de 2e
3 2 1 pièce de 2e
4 0 /
16.4 Exercices
Exercice 97
Créer un fichier sous un tableur (OpenOffice Calc) et calculer toutes les combinaisons possibles de
trajet. Si vous êtes curieux, lancer un chronomètre et à la fin de l’exercice noter le temps mis pour le
résoudre. Quelle est la solution du problème du voyageur ?
Exercice 98
Donner le parcours à suivre obtenu avec une approche du problème par la stratégie d’un algorithme
glouton. Si vous êtes curieux, lancer un nouveau chronomètre et comparer ! Pour un ordinateur avec
un algorithme, c’est bien évidement le même constat.
Exercice 99
Créer une fonction Python qui donne la solution au problème de rendu de monnaie
euros = [ 500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1 ]
def monnaie_a_rendre(somme):
'''combien de pièces-billets faut-il utiliser'''
Il faut partir sur une boucle non-bornée. En effet, il y a de la monnaie à rendre tant que la somme
encore à rendre n’est pas égale à 0.
Exercice 100
Les problèmes de remplissage de sac (Bin packing en anglais dans le texte) sont aussi un classique
de problèmes traités par une approche gloutonne. Un randonneur possède un sac à dos, mais la masse
qu’il peut transporter est limitée. Sur une liste d’objets à prendre, il faut affecter une utilité (choisie
arbitrairement, votre choix ne sera pas forcément le mien) à des objets ayant une certaine masse.
Objet livre jumelles couverture eau nourriture lampe matelas cartes
masse (kg) 0.3 1.3 1 3 4.3 0.5 1.5 0.5
utilité 2 9 6 20 15 10 4 8
Pour illustrer le problème, mettons que vous ne pouvez transporter que 8 kg. Quelle est la liste optimale
d’objets à prendre ? Refaire de nouveaux le problème mais en utilisant vos propres coefficients d’utilité,
votre masse maximale transportable.
Chapitre 16 page 93 OT
