Introduction à l'algorithme
glouton
• Dans ce cours nous allons aborder la notion d'optimisation d'un
problème.
• Un problème d'optimisation :
• est un problème pour lequel on cherche la meilleure solution (selon un critère
défini) dans un ensemble de solutions possibles.
• Quelques exemples de problèmes d'optimisation :
• Rendre la monnaie avec un minimum de pièces.
• Ranger le maximum d'éléments : sac à dos, colis dans un camion, etc.
• Réservation de véhicules dans une société pour minimiser la taille du parc
nécessaire.
• Parcourir un ensemble de lieux en minimisant le temps ou la distance
nécessaire.
• Et d'autres.
• On parle de solution optimale toute une solution qui fait partie des
solutions possibles et qui est la meilleure des solutions selon le critère
défini.
• Pour un rendu de monnaie, le critère pour la solution optimale sera le
nombre de pièces et/ou billets.
• Pour un parcours de lieux, le critère peut être le nombre de lieux ou la
distance parcourue (minimale, maximale).
• Pour un système de réservation, le critère peut être le nombre de
réservations ou la durée de réservation.
• Etc.
• Les algorithmes gloutons sont souvent utilisés pour résoudre ces
problèmes d'optimisation . On cherche une solution optimale en
effectuant le meilleur choix possible à chaque étape de l'algorithme.
Dans ce type de résolution, il n'y a pas de retour en arrière. Lorsqu'un
choix est fait, il n'est pas modifié par la suite. On se retrouve donc à
chaque étape, avec un problème de plus en plus petit à résoudre.
• Attention toutefois, cette méthode ne fournit pas systématiquement
la solution optimale au problème proposé.
Exemple classique : le rendu de monnaie.
• Nous allons étudier un problème d'optimisation classique : le
problème du rendu de monnaie de manière optimale. On cherche à
rendre la monnaie avec un nombre minimal de pièces et billets.
• Voici notre système de monnaie (exprimé en euros) :
• Pièces : 0,01 ; 0,02 ; 0,05 ; 0,1 ; 0,2 ; 1 ; 2 .
• Billets : 5 ; 10 ; 20 ; 50 ; 100 ; 200; 500.
• On cherche par exemple à rendre 53 euros. On peut dans un tableau
énumérer quelques solutions possibles et choisir celle qui minimise le
nombre de pièces et de billets.
L'utilisation de ce type de méthode est très coûteux en temps de calcul car il faut explorer toutes les
possibilités avant de trouver la solution optimale.
L'algorithme glouton
• Définition:
• Un algorithme glouton est un algorithme dans lequel on procède étape par
étape en faisant, à chaque étape, le meilleur choix possible.
On ne remet jamais en cause les choix faits aux étapes passées.
• Dans notre cas nous allons rendre la monnaie en commençant par la
pièce ou le billet avec la plus grande valeur possible (en restant
inférieur à la somme à rendre).
• Cela correspond à notre dernière ligne de tableau
(1×50+1×1+1×2€1×50+1×1+1×2€). On recommence ainsi jusqu'à
obtenir une valeur nulle.
• On note :
• systeme : liste des pièces et des billets
• somme : montant à obtenir
• somme_restante : montant qui reste à rendre
• monnaie : liste qui contient les valeurs rendues
• Algorithme glouton de rendu de monnaie :
• initialiser monnaie à une liste vide
• initialiser la somme_restante à somme
• tant que somme_restante >0 :
• On choisit la plus grande valeur dans systeme inférieure à somme_restante
• on ajoute cette valeur à monnaie
• on retire cette valeur à somme_restante
• renvoyer monnaie
• Reprenons notre exemple avec somme=53 et
systeme=[0.01,0.02,0.05,0.1,0.2,1,2,5,10,20,50
• Voici la liste des étapes :
• Exercice 1:
• Traiter comme précédemment le rendu de monnaie dans
le cas d'un système S = [1,2,5,50,100] et d'une somme
: 27€.
• Comment gérer le rendu de monnaie dans le cas d'un
système S = [1,2,5,50,100] et d'une somme : 27€dans le
cas où l'on ne dispose que de quatre pièces de chaque
type ?
Implémentation de l'algorithme glouton
Programmer l'algorithme glouton de rendu de monnaie en langage
python.
Pour cela, programmer une fonction rendu_monnaie_glouton qui
possède comme paramètres
•un système de pièces et de billet systeme sous forme de liste de nombres ;
•une somme à rendre somme.
Cette fonction renvoie une liste de nombres qui caractérise la monnaie
à rendre.
• Exercice 2 : Problème du sac à dos
• On considère un sac à dos dont le volume maximal est noté V , et l’on dispose de plusieurs
• objets de valeur et de volume donnés. On cherche à transporter dans le sac plusieurs de ces
• objets (sans répétition) sans dépasser le volume maximal et en maximisant la valeur totale des objets
introduits. Les objets sont modélisés par une liste de listes S : S[i][0] désigne la valeur de l’objet i et
S[i][1] son volume. On suppose que tous les volumes sont entiers et que la liste S est triée par valeur
décroissante.
•
• 1. La méthode gloutonne consiste à faire rentrer dans le sac à chaque étape un objet de valeur
maximale parmi ceux qui peuvent encore rentrer. Écrire une fonction itérative sac(V,S) prenant en
entrée un entier V correspondant au volume maximal du sac et une liste de listes S contenant les
valeurs et volumes des objets et qui applique la stratégie ci-dessus.
• On renverra la liste des indices des objets introduits ainsi que la valeur totale de ceux-ci.
•
• 2. Cette stratégie vous semble-t-elle optimale ? Donner un exemple où elle ne renvoie pas un
ensemble de valeur maximale.
•
• 3. Variante : au lieu de prendre l’objet de plus grande valeur, on prend celui de plus grand rapport
valeur/volume et on considère que S est triée par ordre décroissant de ce rapport.
• En considérant la liste [[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]] et un sac de volume V = 30,
• montrer que cette stratégie ne fonctionne pas toujours non plus.
Problème du sac à dos
• Pour partir en randonnée, vous disposez d'un sac à dos. Afin de pouvoir marcher
longtemps chaque jour, vous décidez de limiter la masse totale transportée à
17kg. Cette limitation ne vous permet pas de pouvoir transporter tous les
éléments que vous aimeriez emporter.
Vous décidez de donner une note "utilité" à chacun des objets.
• Vous cherchez à maximiser l'utilité totale des objets emportés dans votre sac à
dos.
Exercice 2 : Occupation d’une salle de spectacles
On dispose d’une salle de spectacle et d’une liste de listes L contenant pour chaque
spectacle d’indice i le couple d’entiers [di, fi] où di désigne l’heure de début et fi l’heure
de fin du spectacle.
On suppose que la liste L est triée par date de fin croissante. On cherche à maximiser le
nombre de spectacles dans la salle (mais pas forcément le temps d’occupation).
1. On adopte la stratégie gloutonne suivante : on commence par le premier spectacle de la
liste, puis on choisit au fur et à mesure le spectacle dont l’intervalle est compatible avec
celui du spectacle précédent et dont l’heure de fin est la plus petite. Appliquer à la main
cette stratégie à la liste L = [[0, 2], [1, 3], [2, 4], [1, 5], [3, 6], [4, 7], [5, 9], [6, 11], [9,
12]].
2. Écrire une fonction gestion(L) prenant en entrée la liste de listes L représentant les
heures de début/fin des spectacles et qui retourne la liste des indices des spectacles retenus
avec la stratégie ci-dessus. Tester sur l’exemple précédent.
