Algorithmes Gloutons 22 23

🧠 Algorithmes Gloutons
Stratégies d'optimisation par choix locaux

🎯 Définitions et Concepts

🔍 Algorithmes Gloutons
Les algorithmes gloutons sont des algorithmes qui ont pour principe de choisir à chaque étape de leur résolution la meilleure solution locale.
⚡ Principe d'optimisation
Ils peuvent répondre au problème d'optimisation en cherchant pour chaque itération un extremum qui minimise ou maximise (suivant le problème) chacune des sous-étapes.
🎯
Solution Locale vs Globale
En général, ces opérations de recherche d'extremum ne sont pas coûteuses mais l'ensemble de celles-ci n'est pas forcément la solution optimale globale.
⚡
Efficacité vs Force Brute
Cette méthode est en général plus efficace que la méthode par force brute. La méthode bruteforce donnera (théoriquement) la solution optimale en testant toutes les combinaisons possibles si la machine a les ressources nécessaires.
💡 Lien avec le chapitre précédent : On peut faire le lien avec un algorithme vu dans le chapitre précédent : _______

📚 Exemples Illustratifs

🏔️
Exemple de l'Alpiniste
Prenons le cas d'un alpiniste qui gravit la chaîne de montagne Kaizen. Il cherche à monter par les plus grands sommets qui se trouvent à sa droite ou sa gauche. Les conditions météorologiques ne sont pas les meilleures et il y a beaucoup de nuages par plateau qui l'empêchent de voir derrière chacun des pics qu'il rencontre.
🔢
Nombre le Plus Grand
On dispose d'une liste de chiffres quelconques et on cherche à construire le nombre le plus grand sans trier la liste. Une solution à ce problème est de trouver le chiffre le plus grand de la liste, le mettre dans la "colonne" la plus à gauche du nombre et le retirer de la liste. On réalise cette opération jusqu'à ce que la liste soit vide.

Exemple :
Liste de départ = [4,2,9,6]
On cherche le chiffre le plus grand : ___
On le retire de la liste et on le rajoute dans une chaîne de caractères.
On réalise cela pour chaque chiffre dans la liste, tant que celle-ci n'est pas vide.
On obtient : "9642"

💰 Le Problème du Rendu de Monnaie

🎯 Principe du Problème
Le problème du rendu de monnaie consiste à rendre une certaine somme en limitant le nombre de pièces (ou billets) à rendre. On a une somme qui nous est donnée et on doit rendre la monnaie. On considère que (dans ce monde utopique), on dispose d'une infinité de billets/pièces de chaque coupure.

💶 Système Monétaire de Référence

1 2 5 10 20 50 100 200 500

📝 Exemple : Rendre 42€

Étapes Liste de monnaies rendues Somme restante à rendre
Initialisation monnaie = [ ] Monnaie_restante = ...
Étape 1 monnaie = [ ] Monnaie_restante = ...
Étape 2 monnaie = [ ] Monnaie_restante = ...
Étape 3 monnaie = [ ] Monnaie_restante = ...

🤔 Exercices de Réflexion

On souhaite rendre 49€ à un client.

1. On dispose d'un système monétaire tel que Système 1 = {1,2,5,10,20,50}.
Quelle solution serait obtenue par l'algorithme glouton grâce au Système 1 ?
Est-elle optimale ?
Si non, donner une solution optimale.
2. On dispose d'un système monétaire tel que Système 2 = {1,3,6,12,24,30}.
Quelle solution serait obtenue par l'algorithme glouton grâce au Système 2 ?
Est-elle optimale ?
Si non, donner une solution optimale.
💡 Idée de l'Algorithme
L'algorithme de rendu de monnaie suit une approche gloutonne en sélectionnant à chaque étape la plus grande pièce ou billet possible ne dépassant pas le montant restant à rendre. Voici les étapes principales :

1. On initialise une liste vide pour stocker les pièces/billets à rendre triée.

2. Pour chaque valeur de pièce/billet, en commençant par la plus grande :
    • Tant que la valeur de la pièce/billet est inférieure ou égale au montant restant
    • On ajoute cette pièce/billet à la solution
    • On soustrait sa valeur du montant restant

3. On continue jusqu'à ce que le montant restant soit nul et on renvoie la liste de billets / pièces à rendre.
### Exercice : Rendu de monnaie !!! fox_exercice **Écrire une fonction `rendu_monnaie(montant, systeme)` qui :** - Prend en paramètre un montant à rendre et un système monétaire - Retourne la liste des pièces/billets à rendre - Utilise le moins de pièces possible **Exemple** : 
systeme = [50,20,10,5,2,1]
print(rendu_monnaie(53, systeme))  # Devrait afficher [50, 2, 1]
!!! fox_exercice_test "Tester différents systèmes et montants" **Tester votre fonction avec les systèmes monnaie suivants :** - Système 1 = [50, 20, 10, 5, 2, 1] - Système 2 = [25, 20, 10, 5, 4, 1] - Système 3 = [100, 50, 20, 12, 7, 1] **Pour chaque système, tester avec différents montants et analyser si la solution trouvée est optimale.** ______

📅 Problème de la Planification de Tâches

🎯 Présentation du Problème
Le problème de la planification de tâches consiste à sélectionner un ensemble de tâches à exécuter de manière à maximiser le nombre de tâches accomplies, sachant que chaque tâche a une heure de début et une heure de fin, et qu'aucune tâche ne peut se chevaucher.

📊 Exemple de Tâches

Tâche Heure de début Heure de fin
A9h0010h30
B10h0011h00
C11h0012h00
D10h3012h30
E12h0013h00
🎯 Stratégie Gloutonne
Pour résoudre ce problème, nous utilisons la stratégie suivante :

1. Trier les tâches par heure de fin croissante
2. Sélectionner la première tâche
3. Pour chaque tâche suivante, la sélectionner si elle ne chevauche pas avec la dernière tâche sélectionnée
🔧 Algorithme de Planification
def planification_taches(taches):
    # Trier les tâches par heure de fin
    taches_triees = sorted(taches, key=lambda x: x[2])  # x[2] = heure de fin

    taches_selectionnees = []
    derniere_fin = 0

    for tache in taches_triees:
        nom, debut, fin = tache
        if debut >= derniere_fin:
            taches_selectionnees.append(tache)
            derniere_fin = fin

    return taches_selectionnees

💼 Le Problème du Sac à Dos

🎯 Principe
Le problème du sac à dos consiste à remplir un sac avec une capacité maximale donnée en choisissant parmi différents objets ayant chacun une masse et une valeur.

L'objectif est de maximiser la valeur totale des objets dans le sac tout en respectant la contrainte de capacité.

On considère que chaque objet est unique et ne peut être fractionné.

🎒 Exemple : Sac à dos de capacité 15kg

Objet A B C D
Masse 4 7 5 3
Valeur 10 15 8 5

📝 Résolution par Stratégie Gloutonne

Étapes Objets dans le sac Masse totale Valeur totale
Initialisation [] 0 0
Étape 1 [B] 7 15
Étape 2 [B, A] 11 25
Étape 3 [B, A, D] 14 30
⚖️
Stratégie par Masse
Choisir d'abord les objets les plus légers pour maximiser le nombre d'objets dans le sac.
💎
Stratégie par Valeur
Choisir d'abord les objets de plus grande valeur pour maximiser rapidement la valeur totale.
📊
Stratégie par Rapport
Choisir les objets ayant le meilleur rapport valeur/masse pour optimiser l'efficacité.
💡 Idée de l'Algorithme
1. On initialise un sac vide avec une masse totale et une valeur totale à 0.

2. Pour chaque objet selon la stratégie choisie :
    • Si l'ajout de l'objet ne dépasse pas la capacité du sac :
        - On ajoute l'objet au sac
        - On met à jour la masse totale
        - On met à jour la valeur totale

3. On continue jusqu'à ce qu'aucun objet ne puisse plus être ajouté.