Certains algorithmes ne permettent pas toujours d'obtenir le résultat optimal. Prenons le problème du sac à dos.

Un voleur doit amasser des objets de valeurs et les mettre dans son sac à dos ne supporte qu'une charge de 15 kg. Quels objets devra-t-il emporter pour partir avec la valeur la plus élevée ?

   

Un algorithme glouton choisit, à chaque étape, la meilleure option immédiate dans l’espoir d’obtenir une solution globale optimale.

Une première solution consiste à calculer le rapport valeur/poids de chaque objet, puis de les amasser sans dépasser 15 kg.      

Principe :

• Calculer le rapport valeur/poids pour chaque objet
• Trier les objets par ordre décroissant de ce rapport
• Ajouter les objets dans le sac tant que la capacité le permet

Exemple Après tri :

On remplit le sac jusqu'à atteindre la capacité maximale.

Algorithme glouton :

1. Créer la liste contenant les objets
2. Créer une fonction calcule_rapport qui prend en paramètre une liste d'objets t, qui ajoute une clé rapport et une valeur correspondant au rapport valeur/poids.
3. Créer une fonction tri par insertion qui prend en paramètre la liste des d'objets t et qui retourne une liste triée par ordre décroissant du rapport valeur/poids.
4. Créer une fonction remplir_sac qui prend en paramètre un tableau t et entier poids_maxi.
5. Créer une procédure qui affiche les objets contenus dans le sac, le poids et la valeur totale des objets amassés.
Cette fonction retournera une liste sac qui contiendra les dictionnaires des objets que contiendra le sac.
6. Trier les objets selon le rapport valeur/poids décroissant,
7. Afficher le contenu du sac.

Programme Python :

objets = [ {"nom": "A", "poids": 12, "valeur": 7}, {"nom": "B", "poids": 7, "valeur": 3}, {"nom": "C", "poids": 9, "valeur": 10}, {"nom": "D", "poids": 2, "valeur": 1}, {"nom": "E", "poids": 5, "valeur": 2}, ]

Exécuter

Limite de l'algorithme glouton :

Cette méthode nous permet d'amasser 11$ pour un poids de 11 kg. Mais est-ce pour autant meilleure la solution ? Non !, trouvez la meilleure solution.

Conclusion : un algorithme glouton est rapide mais parfois sous-optimal.

On considère la liste d'objets suivante :

objets = [
    {"nom": "A", "poids": 12, "valeur": 7},
    {"nom": "B", "poids": 7, "valeur": 3},
    {"nom": "C", "poids": 9, "valeur": 10},
    {"nom": "D", "poids": 2, "valeur": 1},
    {"nom": "E", "poids": 5, "valeur": 2},
]

Un chromosome est une liste de bits dont la longueur dépend du nombre d'objets :

[1, 0, 1, 0, 1]

1 signifie que l'objet est pris
0 signifie qu'il n'est pas pris

Écrire une fonction entier_vers_chromosome(valeur, taille) qui :

• prend un entier valeur en paramètre et un entier correspondant au nombre d'objets taille
• retourne un tableau binaire de taille len(objets)
• utilise des divisions successives par 2 pour convertir la valeur décimale en binaire.

Exemple :

entier_vers_chromosome(9,5) retourne [0,1,0,0,1]

la fonction doit répéter 5 divisions par 2 et ajouter le reste dans un tableau :
9/2 = 4 reste 1	-> ajouter au tableau :	[1]
4/2 = 2 reste 0 -> ajouter au tableau :	[0,1]
2/2 = 1 reste 0 -> ajouter au tableau :	[0,0,1]
1/2 = 0 reste 1	-> ajouter au tableau :	[1,0,0,1]
0/2 = 0 reste 0	-> ajouter au tableau :	[0,1,0,0,1]
retourne le tableau

Écrire une fonction creer_individu(objets, capacite) qui retourne un la liste des dictionnaires :

{
    "chromosome": [...],
    "objets": [...]
    "valeur": ...,
    "poids": ...
}

dont le poids est inférieur ou égal à la capacité passée en paramètre.

• chromosome : tableau binaire
• objets : tableau des noms des objets
• valeur : somme des valeurs des objets sélectionnés
• poids : somme des poids

À l’aide d’une boucle, générer tous les individus possibles :

for i in range(2**len(objets)):

Stocker les individus dans une liste appelée population.

On souhaite trier la population par ordre décroissant de valeur.

Vous pouvez réutiliser et adapter la fonction de tri vue précédemment.

Consigne :

• Adapter la condition du while pour comparer les valeurs dans le dictionnaire
• On comparera : population[j]["valeur"]

Le premier individu valide sera la meilleure solution.

Combien de solutions ont été générées ? Quelle est la complexité de cet algorithme ? Pourquoi cette méthode garantit-elle la meilleure solution ? Comparer avec l’algorithme glouton : avantages / inconvénients

Traduire l'algorithme en langage python

Exécuter

Dans le jeu jumanji nos 4 aventuriers sont poursuivis par le chasseur Van Pelt. Il fait nuit noire et n'ont qu'une heure d'avance sur Van Pelt qui veut les éliminer.

Nos 4 aventuriers doivent traverser une passerelle en très mauvais état et ne possèdent qu'une seule torche pour s'éclairer. Vu l'état de la passerelle, seulement 2 aventuriers peuvent la traverser à la fois. L'un d'eux devra rapporter la torche pour faire traverser les suivants.

• Ruby Roundhouse connait très bien la passerelle et met 5 minutes pour la traverser
• Smolder Braveston est rapide et peut traverser le pont en 10 minutes
• Franklin "Mouse" Finbar et  Shelly Oberon ont le vertige et mettent respectivement 20 et 25 minutes pour traverser.

Dans quel ordre faudra-t-il faire passer nos aventuriers pour qu'ils ne se fassent pas tuer par le chasseur et pour qu'ils puissent couper la passerelle avant l'arrivée du chasseur.

Sans perdre de temps, Franklin "Mouse" Finbar sort une tablette de son sac, écrit quelques lignes de codes de programmation, introduit les données, lance le programme et leur annonce l'ordre de passage. Mais qu'a-t-il bien pu programmer ?

Voici son raisonnement :

Trois traversées sont nécessaires et il compte sur la vitesse de calcul du microprocesseur pour résoudre le problème par le hasard.

1. il prend au hasard deux personnes et les fait traverser.
   
2. il ajoute au temps de la traversée le temps de l'aventurier le moins rapide
3. on complète une variable de type chaine de caractère avec un texte indiquant qui a traversé
   
4. s'il reste des aventuriers à faire traverser :
   
1. au hasard, l'un d'entre eux revient
2. il ajoute au temps de la traversée le temps de l'aventurier qui effectue le retour
3. on complète une variable de type chaine de caractère avec un texte indiquant qui est revenu
   

4. on répète 3 fois à partir de 1
   
5. tant que la durée de la traversée n'est pas inférieure ou égale à 1h, on réinitialise toutes les variables et  on recommence à partir de 1
6. On affiche le résultat
   

• un dictionnaire avec le nom des aventuriers et les temps de passages respectifs : personnages = {'Ruby':5,...}
• une liste depart contenant le nom des personnages voulant traverser la passerelle
• une liste arrivee contenant le nom des personnages qui ont traversé la passerelle
• une variable contenant le temps de la traversée
  

importer la bibliothèque random
personnages ← {'Ruby':5,'Smolder':10,'Franklin':20,'Shelly':25}
tps_traversee ← 100
tant que tps_traversee est supérieur à 60
    depart ← la liste des clés du dictionnaire # list(personnages.keys())
    mélanger la liste de départ    # depart.shuffle()
    arrivee ← []
    tps_traversee ← 0
    texte ← ""
    pour i variant de 0 à 3 exclus
        si le temps du premier personnage est supérieur au temps du second personnage pris dans la liste de départ
            ajouter au temps de la traversée le temps du premier personnage ayant pris le départ
        sinon
            ajouter au temps de la traversée le temps du second personnage ayant pris le départ
        fin si
        ajouter à la liste d'arrivée le nom du premier personnage
        ajouter à la liste d'arrivée le nom du second personnage
        enlever à la liste de depart le nom du dernier personnage arrivé         #indice -1
        enlever à la liste de depart le nom de l'avant dernier personnage arrivé    #indice -2
        ajouter à la variable texte  le nom des personnages ayant traversés et le temps déjà écoulé
        s'il y a encore des personnages dans la liste de départ:
            mélanger la liste arrivée
            ajouter à tps_traverse le temps du 1er personnage de la liste arrivee
            ajouter le nom du 1er personnage de la liste arrivee à la liste depart
            enlever le 1er personnage de la liste arrivee
            ajouter à la variable texte : le nom du personnage qui vient de traverser et le temps déjà écoulé
        fin si
    fin pour
fin tant que 
Afficher le texte constitué et "Smolder coupe les cordes de la passerelle"

Traduire l'algorithme en langage python, puis cliquez sur enregistrer:

Exécuter

Exécuter plusieurs fois le programme et mettre un compteur permettant de connaître la complexité.

Pourquoi le compteur ne donne-t-il pas toujours le même résultat ?

Combien y a-t-il de solutions possibles ? lesquelles ?

Quelle est la condition d'arrêt du programme ?

Que se passe-t-il si je remplace tant que tps_traversee est supérieur à 60 par tant que tps_traversee est supérieur à 55