Les algorithmes gloutons
Les algorithmes gloutons
Le principe de tels algorithmes consiste à choisir des solutions locales optimales d'un problème dans le but d'obtenir une solution optimale globale au problème.
Découvrons cette méthode au travers de quelques exemples...
Le problème du rendu de monnaie
Ce problème est un grand classique de l'algorithmique.
Lorsque vous passez à la caisse d'un magasin quelconque, il n'est pas rare que le caissier doive vous rendre de l'argent car le montant que vous lui avez donné est supérieur à celui que vous devez payer.
Supposons qu'on doive vous rendre la somme de 2,63€.
Il y a plusieurs façons de procéder. On peut par exemple vous rendre 263 pièces de 1 cent, 125 pièces de 2 cents et 13 pièces de 1 cent ou encore 5 pièces de 50 cents, une de 10 cents, une de 2 cents et enfin une de 1 cent.
Il y a bien évidemment énormément de possibilités pour vous rendre la dite somme.
Il y a fort à parier que les solutions du type "263 pièces de 1 cent" ne vous conviennent pas, pour cause, personne n'a envie de remplir son porte monnaie avec autant de pièces...
Le problème qui se pose est donc de minimiser le nombre de pièces rendues pour un montant fixé.
Méthode : Solution naïve
La solution a laquelle on pense immédiatement est d'énumérer toutes les combinaisons possibles, de sélectionner celles qui impliquent un minimum de pièces et de choisir la meilleure.
Cette solution, dite de force brute, fonctionnera toujours mais est très loin d'être efficace.
En effet, si elle est simple dans certains cas, elle implique en général un nombre très important de combinaisons différentes, ce qui nuit grandement à l'efficacité de notre solution.
Notre tâche va donc être de formuler une solution plus efficace pour ce type de problème.
Méthode : La méthode gloutonne
La méthode gloutonne vise donc à optimiser la résolution d'un problème en partant du principe suivant :
Des choix locaux optimaux, étape après étape, devraient produire un résultat global optimal.
Dans notre cas, on va répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante.
Prenons un exemple concret, celui que nous avons introduit précédemment.
On doit donc nous rendre la somme de 2,63€ et on dispose du système de monnaie européen, à savoir ceci :
PIÈCES (en cents) : [1,2,5,10,20,50,100,200]
Appliquons donc la méthode gloutonne pour voir le choix à faire dans ce cas ci.
ÉTAPE 1 :
- Somme à rendre : 263 cents.
- Solution locale : 200.
- Pièces utilisées : 1*2€.
ÉTAPE 2 :
- Somme à rendre : 63 cents.
- Solution locale : 50.
- Pièces utilisées : 1*2€ + 1*50cents.
ÉTAPE 3 :
- Somme à rendre : 13 cents.
- Solution locale : 10.
- Pièces utilisées : 1*2€ + 1*50cents +1*10cents.
ÉTAPE 4 :
- Somme à rendre : 3 cents.
- Solution locale : 2.
- Pièces utilisées : 1*2€ + 1*50cents +1*10cents +1*2cents
ÉTAPE 5 :
- Somme à rendre : 1 cent
- Solution locale : 1
- Pièces utilisées : 1*2€ + 1*50cents +1*10cents +1*2cents +1*1cent
On a rendu toute la monnaie, on s'arrête là !
Le principe est donc extrêmement simple et conduit à une solution optimale dans ce cas-ci.
Nous verrons que ce n'est pas toujours le cas et nous verrons aussi pourquoi.
Simulation : L'algorithme
On va récupérer les données sous forme d'une liste (pour le système monétaire en vigueur) et d'un entier (pour le rendu).
De là :
Tant que le rendu est supérieur à la pièce de plus haute valeur (située en première position dans la liste) on retranchera la valeur de cette pièce au rendu et on ajoutera la pièce dans une liste qui constituera la solution.
Si le rendu est inférieur à la pièce de plus haute valeur en cours, on passe à la pièce suivante.
Et ce jusqu'à ce que le rendu soit nul
Votre travail : Réalisez ce programme (Processing ou Edupython )
Puis rajoutez ce qu'il faut pour que ce soit l'utilisateur qui rentre la somme à rendre
Méthode : Corrigé dans Processing
liste1=[0,0,0,0,0,0,0,0]
liste=[200,100,50,20,10,5,2,1]
def input(message=''):
from javax.swing import JOptionPane
return JOptionPane.showInputDialog(frame,message)
def monnaie(s):
global liste,liste1
for i in range(0,8):
liste1[i]=s//liste[i]
s=s%liste[i]
def setup():
global liste,somme
somme=int(input('Entrez le montant de la monnaie'))
print(somme)
monnaie(somme)
print(liste1)
Le problème du sac à dos
On dispose d'un ensemble d'objets.
Chaque objet possède une valeur b et un poids w.
On souhaiterait prendre une partie T de ces objets dans notre sac-à-dos, malheureusement, ce dernier dispose d'une capacité limitée W. On ne pourra pas toujours mettre tous les objets dans le sac étant donné que la somme des poids des objets ne peut pas dépasser la capacité maximale.
On va cependant chercher à maximiser la somme des valeurs des objets qu'on va emporter avec soi.
Méthode : Solution naïve
On pourrait être tenté d'énumérer toutes les combinaisons d'objets possibles qui satisfont à la capacité maximale du sac ou qui s'en rapprochent (le sac ne doit pas être obligatoirement rempli à fond). Néanmoins, on arrive rapidement à des calculs lourds, rendant le programme inefficace.
À nouveau, la solution de force brute fonctionne, mais ne doit pas être choisie.
Comme vous vous en doutez, on va résoudre ce problème au moyen de la méthode gloutonne.
Méthode : la méthode gloutonne
L'idée à suivre, si on veut développer une méthode gloutonne, est d'ajouter les objets de valeurs élevées en premier, jusqu'à saturation du sac.
Cette méthode est parfois efficace, mais parfois pas, on verra ses limites.
Prenons un exemple :
Supposons qu'on dispose d'un sac de capacité W=26 et des objets suivants :
Objets A B C D E F G H I J K L M N
Valeurs 4 3 8 5 10 7 1 7 3 3 6 12 2 4
Poids 2 2 5 2 7 4 1 4 2 1 4 10 2 1
En suivant la méthode, on obtient :
L(12,10) ; E(10,7) ; C(8,5) ; F(7,4)
Méthode : L'algorithme
À partir d'une liste, dont les éléments sont des triplets [objet,valeur,poids], triée selon l'ordre décroissant des valeurs, on va remplir le sac à dos jusqu'à saturation.
On va ainsi parcourir tous les éléments à notre disposition via la liste et on ajoutera ceux dont le poids, cumulé aux poids des objets déjà dans le sac, est inférieur à la capacité totale du sac.
Lorsque la capacité totale est dépassée, ça signifie soit que le sac est plein, soit que l'objet qu'on veut insérer est trop lourd.
Votre travail : Réalisez ce programme (Processing ou EduPython)
Méthode : Corrigé ( Processing)
# algo du knapsackmon_dico={'A':(4,2),'B':(3,2),'C':(8,5),'D':(5,2),'E':(10,7),'F':(7,4),'G':(1,1),'H':(7,4),'I':(3,2),'J':(3,1),'K':(6,4),'L':(12,10),'M':(2,2),'N':(4,1)}
#tri du dictionnaire par valeur 1 du tuple -->listedef get_val(mon_dico):
return mon_dico[1][0]
liste=sorted(mon_dico.items(),reverse=True,key=get_val)
# liste est une liste qui contient tuple(clé,tuple(valeur,poids))W_max=26
w=0
print(liste)
liste1=[]i=0
#print(liste[i][1][1])while i<len(liste):
if w<=W_max:
w=w+liste[i][1][1]
if w>W_max:
breakliste1.append(liste[i][0])
i=i+1
s=0
for i in range(0,len(liste1)):
s=s+liste[i][1][1]
print("le sac contient les objets : ",liste1," pour un poids de :",s,"kg")
Faiblesses des algorithmes gloutons
Les algorithmes gloutons présentent l'avantage d'une conception relativement aisée à mettre en œuvre.
Cependant la solution n'est pas toujours optimale.
Le problème du rendu de pièces
L'algorithme glouton est d'une bonne efficacité avec le système monétaire européen, il fournit la solution à laquelle on s'attend et qui est optimale.
Maintenant, imaginons un système monétaire dans lequel il y aurait seulement des pièces de 1, 3 et 4 unités.
Supposons qu'on doive me rentre 6 unités monétaires.
Tout le monde dira bien entendu qu'il faut rendre 2 pièces de 3 unités pour minimiser le nombre de pièces rendues.
Cependant, la méthode gloutonne rendra 1 pièce de 4 unités et 2 pièces de 1 unité.
En effet, elle va d'abord choisir la pièce de plus haute valeur en dessous du rendu, soit celle de 4 unités. Il restera ensuite 2 unités à rendre, la seule possibilité étant de fournir 2 pièces d'une unité.
On aura donc 3 pièces au lieu de 2, la solution n'est pas optimale.
Le problème du sac à dos
Les poids fourni dans notre exemple sont relativement équilibrés, de sorte que la solution fournie est probablement optimale.
Mais qu'en serait-il si les poids des objets étaient très déséquilibrés ?
Prenons un exemple
Objets A B C D E F
Valeurs 30 12 12 12 12 4
Poids 39 10 10 10 10 1
L'algorithme choisira l'objet A et l'objet F, ce qui fera une somme des valeurs de 34.
Pourtant, on remarque directement qu'en choisissant les 4 objets B,C,D,E; on aurait pu atteindre une somme des valeurs de 48, pour le même poids.
Comment faire pour avoir une solution optimale ?
Il n'y a pas de réponse miracle à cette question, tout dépend du problème.
Dans certains cas, les algorithmes gloutons produisent d'excellents résultats et sont appropriés au problème, dans d'autres cas, non.
Généralement, si les poids des objets sont très déséquilibrés, les algorithmes gloutons produiront une solution non optimale car de tels algorithmes ont une mauvaise vision globale du problème.
Il faut réfléchir à la solution à adopter en fonction du problème.
Pour un projet, trouver d'autres exemples que l'on peut traiter avec des algorithmes gloutons...
