Différences

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

--- les_programmes_a_connaitre:algorithmique_premiere:glouton [2023/01/24 17:39]
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é.
-==== L'algorithme ====
+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).
+==== L'algorithme dans le cas Général ====
 <code>
@@ Ligne 11: / Ligne 14: @@
 x : un entier
-l : une liste dans l'ordre croissant
+f : une liste ordonnée
 r : une liste
@@ Ligne 18: / Ligne 21: @@
 ALGORITHME_GLOUTON(x, l) :
     compteur ← 1
-    tant que x < 1 ou x > l:
+    tant que x > 0:
-        si l[compteur] > x:
+        si f[compteur] > x:
             compteur ← compteur + 1
         sinon:
             x ← x - f[compteur]
-            r.append(f[compteur])
+            ajouter(f[compteur], r)
             compteur ← compteur + 1
         fin si
     fin tant que
-fin
+FIN
 </code>
-Ci-dessous un exemple d'utilisation de celui-ci :
+====Ci-dessous un exemple d'utilisation :====
-==== Problème du voleur ====
+=== Problème du voleur ===
 ^      Objet     |     A      |     B      |     C     |     D      |
@@ Ligne 46: / Ligne 49: @@
 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 :
-re étape : A (13 Kg)
+  * 1re étape : A (13 Kg)
-e étape : C (13+8=21 Kg)
+  * 2e étape : C (13+8=21 Kg)
-e étape : B (13+8+12=33 Kg) => impossible, on dépasse les 30 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