Outils pour utilisateurs

Outils du site


les_programmes_a_connaitre:algorithmique_premiere:glouton

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision
Révision précédente
les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/18 11:14]
fm
les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/30 08:28] (Version actuelle)
et
Ligne 4: Ligne 4:
 ==== C'est quoi un algorithme glouton ? ==== ==== C'est quoi un algorithme glouton ? ====
  
-L'algorithme ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape. Il existe d'autre algorithme plus optimiser que l'algorithme ''Glouton''.+L'algorithme ''Glouton'' est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape sans revenir sur ses décisionsDe ce fait, le résultat final n'est pas toujours le plus optimisé.
  
-Ci-dessous un exemple d'utilisation de celui-ci :+Pour sa complexité, si les objets sont déjà triés par ordre décroissant de valeur, alors la boucle bornée de 1 à n correspond à une complexité de l'ordre de O(n). Par contre si la liste des objets n'est pas triée on passe à une compléxité de l'ordre de O(n logn).
  
-==== Problème du voleur ====+==== L'algorithme dans le cas Général ==== 
 + 
 +<code> 
 +VARIABLE 
 + 
 +x : un entier 
 +f : une liste ordonnée  
 +r : une liste 
 + 
 +DEBUT 
 + 
 +ALGORITHME_GLOUTON(x, l) : 
 +    compteur ← 1 
 +    tant que x > 0: 
 +        si f[compteur] > x: 
 +            compteur ← compteur + 1 
 +        sinon: 
 +            x ← x - f[compteur] 
 +            ajouter(f[compteur], r) 
 +            compteur ← compteur + 1 
 +        fin si 
 +    fin tant que 
 +FIN 
 +</code> 
 + 
 +====Ci-dessous un exemple d'utilisation :==== 
 + 
 +=== Problème du voleur ===
  
 ^      Objet              |          |                  |   ^      Objet              |          |                  |  
 ^      Masse        13Kg    |    12Kg    |    8Kg    |    10Kg    | ^      Masse        13Kg    |    12Kg    |    8Kg    |    10Kg    |
 ^Valeur marchande|    700€    |    400€    |    300€      300€    | ^Valeur marchande|    700€    |    400€    |    300€      300€    |
 +
 +Le voleur à un sac avec une capacité de 30Kg.
 +
 +Sachant que l'on cherche à maximiser le gain, commençons par établir un tableau nous donnant la "valeur massique" de chaque objet (pour chaque objet on divise sa valeur par sa masse) :
 +^ Objet          |      |    B    |    C    |    D    |
 +^ Valeur Massique|54 €/Kg | 33 €/Kg | 38 €/Kg | 30 €/Kg | 
 +
 +On classe ensuite les objets par ordre décroissant de valeur massique : A - C - B - D
 +Enfin, on remplit le sac en prenant les objets dans l'ordre et en s'arrêtant dès que la masse limite est atteinte. C'est ici que ce fait "le choix glouton", à chaque étape, on prend l'objet ayant le rapport "valeur-masse" le plus intéressant au vu des objectifs :
 +  * 1re étape : A (13 Kg)
 +  * 2e étape : C (13+8=21 Kg)
 +  * 3e étape : B (13+8+12=33 Kg) => impossible, on dépasse les 30 Kg.
 +
 +Le sac est donc composé de 2 objets : A et C pour un montant total de 1000 € et une masse totale de 21 Kg.
 +
 +On remarque que ce n'est pas la combinaison la plus optimisé, celle-ci serait A,B (1100€ pour 25Kg) et non A,C (1000€ pour 21Kg).
  
 ======Implémentation en Python====== ======Implémentation en Python======
Ligne 72: Ligne 115:
 </code> </code>
  
-======Explication du programme :======+=====Explication du programme :=====
  
  
les_programmes_a_connaitre/algorithmique_premiere/glouton.1674036860.txt.gz · Dernière modification: 2023/01/18 11:14 de fm