Favicon
NSI Première

Connexion élèves

Choisir le(s) module(s) à installer :

Algorithmes gloutons

Nous allons étudier une grande "classe" d'algorithmes : Les algorithmes gloutons (ou "greedy algorithm" en anglais).
Mais avant de définir les grandes lignes caractérisant cette classe, nous allons nous intéresser à un exemple classique, de la vie courante, où vous utilisez un algorithme gloutons sans le savoir.

Un exemple : Le rendu de monnaie

Présentation du problème

Le rendu de monnaie est un problème du quotidien. la question est la suivante :
vous devez rendre 4,24€ avec un système de pièces et de billets donnés en minimisant le nombre de pièce ou billets rendus.
rendu de monnaie
Vous avez déjà résolu ce problème de nombreuses fois, en suivant un algorithme "instinctif".
Nous allons essayer d'analyser votre résolution de ce problème et tenter de généraliser votre démarche à n'importe quelle somme et à n'importe quel système de monnaie (ensemble de pièces et de billets existants).
le problème du rendu de monnaie c'est :
  • Rendre une somme donnée
  • A partir d'un système de monnaie donné monnaie=[pièce1, pièce2, ..., billet1, billet2, ...]
  • En minimisant le nombre de pièces et de billets rendus.

Quelques exemples

Pour bien comprendre la démarche à suivre nous allons commencer par rendre quelques sommes "à la main".
Nous allons considérer notre système de monnaie européen (sans les centimes): [1, 2, 5, 10, 20, 50, 100, 200, 500].
  1. Trouver TOUTES les possibilités pour rendre 7€ (il y en a 6 différentes ).
  2. Déterminer la solution optimale pour rendre 7€.

SOLUTION

Cette exemple est "trivial", nous allons donc nous intéresser à un exemple plus difficile...
  1. Nous allons tenter de rendre 263 €, je ne vous demande pas de trouver toutes les solutions, puis de déterminer celle qui est optimale mais de donner, d'après vous, la solution optimale.
  2. Réalisez le même raisonnement pour 264 €.

SOLUTION

Une fois que vous avez réalisé ces deux exemples, nous allons nous orienter vers la formalisation de l'algorithme que vous utilisez instinctivement. Pour cela répondez aux questions suivantes :
  1. Quel est le premier billet à rendre dans les deux cas précédents ?
  2. Quels sont les deux critères pour choisir ce premier billet ?
  3. Une fois que ce billet est choisit, quel est le nouveau problème qui se pose à vous ?

SOLUTION

Premier programme "glouton"

Si vous avez répondu correctement aux questions précédentes, vous avez réussi à cerner algorithme que vous appliquez naturellement pour rendre la monnaie. Nous allons tenter de programmer cet algorithme.
Vous allez devoir coder une fonction répondant aux caractéristiques suivantes :
  • La fonction prendra en paramètre :
    • Le système de monnaie sous forme d'un tableau
    • La somme à rendre
    son entête sera donc def rendu_glouton(monnaie:list, somme:int):
  • La fonction affichera, dans un premier temps, la suite de billets et de pièces à rendre
L'algorithme à suivre sera donc le suivant, d'après vos recherches précédentes : 

tant que somme est positif
	si le premier billet est supérieur à somme
		passer au billet suivant
	sinon:
		afficher le billet
		enlever le billet à somme
Vous pourrez tester votre fonction sur les appels suivants, que vous avez déjà rencontré : 

rendu_glouton([100,50,20,10,5,2,1],7)
rendu_glouton([100,50,20,10,5,2,1],4)
rendu_glouton([100,50,20,10,5,2,1],263)			
rendu_glouton([100,50,20,10,5,2,1],264)
def rendu_glouton(monnaie:list, somme:int):

SOLUTION

rendu de monnaie

Les grands principes des algorithmes gloutons

un glouton ou 'gulo gulo'
Si votre fonction fonctionne vous avez réussi à programmer votre premier algorithme glouton, mais quelles sont les grand principes de cette classe d'algorithme ?

Un algorithme glouton est un algorithme qui fait un choix local optimal en espérant que cela conduise à une solution globale optimale.
Dans l'exemple précédent nous avons à chaque instant: Et dans notre cas CA MARCHE !!!.
Mais...les algorithmes gloutons ne "fonctionnent" pas toujours...
  1. Tentez de rendre 6€ avec le système suivant : [4,3,1], en suivant votre algorithme. Est-ce optimal ?
  2. Tentez de rendre 8€ avec le système suivant [10,5,2]

SOLUTION

Pour information, notre système de monnaie européen a été mis au point pour que l'algorithme de rendu de monnaie glouton soit toujours optimal !

Bonus : Pour aller plus plus loin

Vous devez ici améliorer votre fonction def rendu_glouton(monnaie:list, somme:int): en def rendu_glouton(monnaie:list, somme:int)->list:.
La fonction ne doit plus afficher les pièces et billets à rendre mais renvoyer un tableau contenant les pièces et les billets.
def rendu_glouton(monnaie:list, somme:int)->list:

SOLUTION

Le problème du sac à dos

Le problème du sac à dos est un problème d'optimisation classique de l'informatique que nous allons tenter de résoudre grâce aux algorithmes gloutons.

Présentation du problème

Nous allons imaginer un voleur en train de dévaliser un appartement.
  • Il ne peut pas porter un sac de plus de 30 kg
  • Il veut ramener un butin maximum
et il a devant lui une plusieurs objets :
  • objet 1 : poids 13 kg et valeur 700 €
  • objet 2 : poids 12 kg et valeur 400 €
  • objet 3 : poids 8 kg et valeur 300 €
  • objet 4 : poids 10 kg et valeur 300 €
Il doit donc optimiser le remplissage de son sac.
© Boulet

Un peu de force brute (à la main !)

Vous connaissez sûrement cette expression informatique de "force brute". Elle consiste à attaquer un problème frontalement et à explorer toutes les possibilités en profitant de la force de calcul d'un ordinateur.
C'est une technique qui peut, par exemple, être utilisée pour trouver un mot de passe inconnu, en testant toutes les possibilités.
En considérant la liste d'objets ci-dessus, répondre aux questions suivantes:
  1. Lister les chargements possibles du sac à dos sans se soucier du prix ou de la masse totale pour
    • 4 objets (1 solution c'est facile !)
    • 3 objets (4 solutions)
    • 2 objets (6 solutions)
    • 1 objet (4 solutions c'est facile !)
  2. En vous mettant par groupe de deux, calculer pour chaque chargement :
    • La masse du chargement en kg
    • Le gain du chargement
  3. Éliminez les sacs de plus de 30 kg
  4. Déterminez les chargement optimaux

SOLUTION

On peut remarquer qu'avec 4 objets le problème est déjà assez complexe !
Mais dès que l'on dépasse 40 objets, un ordinateur actuel est incapable de le résoudre raisonnablement de cette façon !
En effet la complexité de ce problème en en O(2n), où n est le nombre d'objets.
  1. Calculer 240
  2. Si une opération sur l'ordinateur prend 1µs=10-6s, combien de temps prendront 240 opérations ?

SOLUTION

Et l'algorithme glouton ?

Comme on vient de le voir il n'est pas envisageable de tester tous les cas, surtout si le nombre d'objets dépasse 30 ou 40.
Nous allons donc tenter d'appliquer la technique de l'algorithme glouton à ce problème.
Mais comment faire ?
Faut-il choisir initialement le plus petit objet, ou celui qui rapporte le plus ?
Et bien il faut OPTIMISER.
Nous allons donc calculer pour chaque objet son "gain massique" c'est à dire ce que rapportera un kg de cet objet. Ainsi la liste précédente sera agrémentée du gain massique :
  • objet 1 : poids 13 kg et valeur 700 €, gain massique : 700/13=53,8 €/kg
  • objet 2 : poids 12 kg et valeur 400 €, gain massique : 400/12=33,3 €/kg
  • objet 3 : poids 8 kg et valeur 300 €, gain massique : 300/8=37,5 €/kg
  • objet 4 : poids 10 kg et valeur 300 €, gain massique : 300/10=30 €/kg
Il ne reste plus qu'a trier cette liste d'objets et à commencer par celui qui rapporte le plus "au kg"...
  • Vérifier que le sac n'est pas trop lourd si on l'ajoute
  • Enlever cet objet de la liste
  • ...et recommencer !

Structure de données

Pour résoudre ce problème il faut d'abord penser à la structure de données qui pourra contenir la liste d'objets.
Sachant que chaque objet a trois caractéristiques : Il va donc être judicieux d'utiliser un tableau de tableau: 

objet1=[13,700,53.8]
objet2=[12,400,33.3]
objet3=[8,300,37.5]			
objet4=[10,300,30]
liste_objets=[objet1, objet2, objet3, objet4]
Mais, deux problèmes se posent à nous : Nous verrons un peu plus tard dans l'année différents algorithmes de tri, nous allons donc utiliser la méthode sort() de python. Testez le programme ci-dessous : 

tab=[4,3,1,9]
tab.sort()
print(tab)
tab.sort(reverse=True)
print(tab)
Vous avez compris la syntaxe, mais nous voulons trier un tableau de tableaux en choisissant un élément particulier comme critère de prix (la valeur massique).
Testez le code ci-dessous : 

tab=[[4,100],[3,200],[1,300],[9,400]]
tab.sort(reverse=True)
print(tab)
  1. Au vu des tests que vous avez fait, quel est le critère utilisé par la méthode sort() pour trier des tableaux de tableaux
  2. Grâce à cette remarque, comment doit être modifiée la structure de données proposée pour les objets

SOLUTION

Génération de liste d'objets

Nous avons maintenant une structure de données pour la liste des objets à mettre dans le cas à dos qui pourrait être la suivante : 

obj_test=[[None,13,700],[None,12,400],[None,8,300],[None,10,300]]
None représentant ici l'absence de valeurs, la valeur massique de chaque objet sera calculée dans la fonction sacAdos.
Grâce au tableau de tableaux obj_test nous allons pouvoir tester notre futur programme. Mais si l'on veut voir s'il "résiste" à une liste de 30 objets, il faudra générer automatiquement une telle liste.
Le code ci dessous est incomplet. Vous devez le compléter pour qu'il respecte la docstring.
from random import randint def listeobj(n:int)->list: ''' n est le nombre d'objets dans la liste la fonction renvoie une liste d'objets aléatoire pour le probleme du sac a dos ''' obj=[[None,randint(1,30), randint(10,100)]...] ....
vous pourrez tester ce code avec les deux appels suivants : 

print(listeobj(4))
print(listeobj(30))

SOLUTION

Le code sacAdos

Voici un code incomplet, complétez le et testez le en suivant les questions ci-dessous.
def sacAdos(objets:list,msac:int)-> list: ''' résolution du problème du sac à dos objets est la liste d'objets msac est la masse maximale du sac la fonction renvoie la somme présente dans le sac et la masse du sac ''' masse=0 somme=0 #parcours de la liste d'objet et calcul de la valeur massique for i in range(len(objets)): objets[i][0]=... #tri de la liste d'objets du plus rentable au moins rentable objets.sort(reverse=True) #parcours de la liste d'objets et choix de ceux à mettre dans le sac for element in objets: if masse+element[1] < msac: ... ... return ...
  1. Dans la première partie du programme, on calcule la valeur massique de chaque objet que l'on range à la case "0" du sous-tableau représentant chaque objet. Compléter les pointillés de la ligne 13 pour réaliser cette fonction.
  2. Tester grâce à un affichage cette partie du programme sur le tableau de tableau obj_test.
  3. Dans la deuxième partie du programme, on parcourt chaque élément de la liste et on teste si il est possible de l'ajouter dans le sac à dos (lignes 19 et 20). Si cela est possible, deux opérations sont à réaliser avant de passer à l'objet suivant. Compléter les lignes 21 et 22.
  4. Compléter enfin la ligne 24 en respectant la docstring.
  5. Pour finir testez votre programme sur obj_test et sur une liste de 30 objets aléatoires

SOLUTION

Analyse de l'efficacité de l'algorithme glouton

Mais au fait, est-ce que notre algorithme glouton nous propose "LA" solution optimale ?
Dans le cas de la liste "test" que vous avez utilisé pendant toute cette partie cela semble être le cas.
Si l'on considère deux objets, l'un de 1kg et l'autre de 30kg.

Attribuez à chacun une valeur qui fera que notre algorithme glouton ne sera pas optimal.

SOLUTION

Comme on l'a déjà la "force brute" ne permet pas de trouver une solution quand il y a trop d'objets.
L'algorithme glouton lui proposera toujours une solution, elle sera "pas trop mauvaise" mais ne sera pas toujours optimale...
Il existe des solutions algorithmiques optimales à ce problème, mais elle sont totalement hors programme !
Elle peuvent faire appel, par exemple à la programmation dynamique.