Différences

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

--- les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/24 16:44]
et
+++ 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 ? ====
-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écisions. De 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     |     A      |     B      |     C     |     D      |
 ^      Masse     |    13Kg    |    12Kg    |    8Kg    |    10Kg    |
 ^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          |   A    |    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======

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page