Algorithmes dits gloutons | Exercices corrigés

Concepts & Exercices

\(\text{Glouton}(problème) \rightarrow \text{solution}_{\text{locale}}\)

Stratégie d'optimisation locale

Stratégie

Optimale local

Choix immédiat

Complexité

O(n)

Généralement

Optimalité

Problème dépendant

🎯

Définition : Algorithme glouton = stratégie qui fait le meilleur choix local à chaque étape.

📏

Principe : Ne jamais revenir en arrière sur les choix faits.

📋

Applications : Rendu de monnaie, sac à dos fractionnaire, arbres couvrants.

⚡

Avantage : Simplicité d'implémentation et rapidité.

💡

Conseil : Utilisez des algorithmes gloutons pour des problèmes avec propriété de sous-structure optimale

🔍

Attention : Ne garantissent pas toujours la solution optimale globale

⚡

Astuce : Trier les données peut améliorer l'efficacité des algorithmes gloutons

📋

Méthode : Identifier le critère de choix optimal local

Exercice 1

Rendu de monnaie avec pièces de différentes valeurs

Exercice 2

Sac à dos fractionnaire (version gloutonne)

Exercice 3

Problème d'intervalle (choix d'activités)

Exercice 4

Analyse de la complexité des algorithmes gloutons

Exercice 5

Comparaison glouton vs optimal pour le rendu de monnaie

Corrigé : Exercices 1 à 3

1 Rendu de monnaie

Définition :

Algorithme glouton : Stratégie qui fait le meilleur choix local à chaque étape.

Rendu de monnaie : Donné un montant, rendre la monnaie avec le minimum de pièces/billets.

Méthode du rendu de monnaie glouton :

Trier les pièces/billets par valeur décroissante
À chaque étape, prendre la pièce/billet de plus grande valeur possible
Répéter jusqu'à ce que le montant soit complètement rendu
Ne jamais revenir en arrière sur les choix faits

Montant

67€

Pièces

[50, 20, 10, 5, 2, 1]

Rendu

[50, 10, 5, 2]

50€

20€

10€

5€

2€

1€

50€

20€

10€

5€

2€

1€

Étape 1 : Initialisation

Montant à rendre : 67€

Pièces disponibles : [50, 20, 10, 5, 2, 1] (triées par ordre décroissant)

Étape 2 : Premier choix glouton

Prendre la plus grande pièce ≤ 67 : 50€

Reste à rendre : 67 - 50 = 17€

Pièces rendues : [50]

Étape 3 : Second choix glouton

Prendre la plus grande pièce ≤ 17 : 10€

Reste à rendre : 17 - 10 = 7€

Pièces rendues : [50, 10]

Étape 4 : Troisième choix glouton

Prendre la plus grande pièce ≤ 7 : 5€

Reste à rendre : 7 - 5 = 2€

Pièces rendues : [50, 10, 5]

Étape 5 : Quatrième choix glouton

Prendre la plus grande pièce ≤ 2 : 2€

Reste à rendre : 2 - 2 = 0€

Pièces rendues : [50, 10, 5, 2]

Étape	Pièce choisie	Valeur	Reste à rendre
1	50€	50	17€
2	10€	10	7€
3	5€	5	2€
4	2€	2	0€

                // Pseudo-code
                fonction rendu_monnaie_glouton(montant, pieces):
                  resultat = []
                  pour chaque piece dans trier(pieces, ordre_decroissant):
                    tant que montant >= piece:
                      ajouter piece à resultat
                      montant = montant - piece
                  retourner resultat
                  
                // Pour 67€ et [50, 20, 10, 5, 2, 1]
                // Résultat : [50, 10, 5, 2]
              

Rendu = [50€, 10€, 5€, 2€] (4 pièces)

Réponse finale :

Pour 67€, le rendu optimal glouton est 50€ + 10€ + 5€ + 2€ = 67€ avec 4 pièces.

Règles appliquées :

• Glouton : Choisir la plus grande pièce/billet possible à chaque étape

• Système monétaire : Fonctionne bien avec les systèmes standards (comme l'euro)

• Optimalité locale : Chaque choix semble optimal au moment de la décision

2 Sac à dos fractionnaire

Définition :

Sac à dos fractionnaire : Version du problème où on peut prendre des fractions d'objets.

Stratégie gloutonne : Prendre les objets avec le meilleur rapport valeur/masse.

Capacité

W = 15 kg

Objets

(v/m): (6/1), (10/2), (12/3)

Solution

Total = 24

Étape 1 : Calcul des rapports valeur/masse

Objet A: valeur=6, masse=1 → rapport=6/1=6

Objet B: valeur=10, masse=2 → rapport=10/2=5

Objet C: valeur=12, masse=3 → rapport=12/3=4

Étape 2 : Tri par rapport décroissant

Ordre de sélection: A(rapport=6), B(rapport=5), C(rapport=4)

Étape 3 : Remplissage glouton

Sélectionner objet A: masse=1, valeur=6, reste=14kg

Sélectionner objet B: masse=2, valeur=10, reste=12kg

Sélectionner objet C: masse=3, valeur=12, reste=9kg

Étape 4 : Calcul de la valeur totale

Valeur totale = 6 + 10 + 12 = 28

Masse totale = 1 + 2 + 3 = 6kg (inférieur à la capacité de 15kg)

Objet	Valeur	Masse	Rapport	Sélectionné
A	6	1	6.0	✓
B	10	2	5.0	✓
C	12	3	4.0	✓

                // Pseudo-code
                fonction sac_a_dos_fractionnaire(objets, capacite):
                  // Trier par rapport valeur/masse décroissant
                  objets_tries = trier(objets, cle=lambda o: o.valeur/o.masse, decroissant=True)
                  
                  valeur_totale = 0
                  masse_utilisee = 0
                  
                  pour objet dans objets_tries:
                    si masse_utilisee + objet.masse <= capacite:
                      // Prendre l'objet entièrement
                      valeur_totale += objet.valeur
                      masse_utilisee += objet.masse
                    sinon:
                      // Prendre une fraction de l'objet
                      fraction = (capacite - masse_utilisee) / objet.masse
                      valeur_totale += objet.valeur * fraction
                      masse_utilisee = capacite
                      break
                      
                  retourner valeur_totale
              

Valeur maximale = 28

Réponse finale :

La valeur maximale obtenue est 28 avec les objets A, B et C.

Règles appliquées :

• Rapport valeur/masse : Critère de choix optimal pour le sac à dos fractionnaire

• Tri préalable : Essentiel pour la stratégie gloutonne

• Optimalité : La solution gloutonne est optimale pour cette version du problème

3 Problème d'intervalle

Définition :

Problème d'intervalle : Sélectionner le maximum d'activités sans chevauchement.

Stratégie gloutonne : Sélectionner l'activité qui se termine le plus tôt.

Activités

(début, fin): (1,4), (3,5), (0,6), (5,7), (8,9), (5,9)

Stratégie

Fin la plus tôt

Sélection

(1,4), (5,7), (8,9)

Étape 1 : Analyse des activités

Activités: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]

Objectif: Sélectionner le maximum d'activités sans conflit

Étape 2 : Tri par heure de fin croissante

(1,4), (3,5), (5,7), (8,9), (0,6), (5,9)

Trié: (1,4), (3,5), (5,7), (8,9), (0,6), (5,9)

Étape 3 : Sélection gloutonne

Sélectionner (1,4) - fin à 4

Prochaine activité compatible: (5,7) - commence à 5 ≥ 4

Sélectionner (5,7) - fin à 7

Prochaine activité compatible: (8,9) - commence à 8 ≥ 7

Sélectionner (8,9) - fin à 9

Étape 4 : Vérification de la solution

Activités sélectionnées: (1,4), (5,7), (8,9)

Aucun chevauchement: 4≤5, 7≤8 - Solution optimale!

Activité	Début	Fin	Sélectionnée	Compatibilité
A1	1	4	✓	Début=1
A2	3	5	✗	3<4 (conflict)
A3	0	6	✗	0<4 (conflict)
A4	5	7	✓	5≥4
A5	8	9	✓	8≥7
A6	5	9	✗	5<7 (conflict)

                // Pseudo-code
                fonction selection_activites(activites):
                  // Trier par heure de fin croissante
                  triees = trier(activites, cle=lambda a: a.fin)
                  
                  selectionnees = [triees[0]]  // Première activité
                  derniere_fin = triees[0].fin
                  
                  pour activite dans triees[1:]:
                    si activite.debut >= derniere_fin:
                      selectionnees.ajouter(activite)
                      derniere_fin = activite.fin
                      
                  retourner selectionnees
                  
                // Pour [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]
                // Résultat: [(1,4), (5,7), (8,9)]
              

Activités sélectionnées = (1,4), (5,7), (8,9)

Réponse finale :

Les activités optimales sont (1,4), (5,7), (8,9) - total de 3 activités.

Règles appliquées :

• Heure de fin : Critère de sélection optimal pour ce problème

• Tri préalable : Nécessaire pour la stratégie gloutonne

• Optimalité : La solution gloutonne est optimale pour ce problème

Corrigé : Exercices 4 à 5

4 Analyse de complexité

Définition :

Complexité algorithmique : Mesure de la performance en fonction de la taille des données.

Algorithmes gloutons : Généralement O(n log n) à cause du tri, O(n) sans tri.

Algo

Glouton

Comp

O(n log n)

Tri

O(n log n)

Étape 1 : Analyse du rendu de monnaie

Tri des pièces: O(n log n) où n = nombre de types de pièces

Itération sur les pièces: O(n) dans le pire cas

Complexité totale: O(n log n)

Étape 2 : Analyse du sac à dos fractionnaire

Tri des objets: O(n log n) où n = nombre d'objets

Itération sur les objets: O(n)

Complexité totale: O(n log n)

Étape 3 : Analyse du problème d'intervalle

Tri des activités: O(n log n) où n = nombre d'activités

Itération sur les activités: O(n)

Complexité totale: O(n log n)

Étape 4 : Comparaison avec d'autres algorithmes

Algorithmes dynamiques: souvent O(n²) ou O(n³)

Algorithmes gloutons: plus rapides mais pas toujours optimaux

Problème	Glouton	Dynamique	Optimalité
Rendu monnaie	O(n log n)	O(n × montant)	✓ pour systèmes canoniques
Sac à dos frac.	O(n log n)	O(n log n)	✓
Intervalle	O(n log n)	O(n²)	✓
Sac à dos 0/1	O(n log n)	O(n × W)	✗ (glouton)

\(\text{Complexité}_{\text{glouton}} = O(n \log n) + O(\text{itérations})\)

Dépend du tri et du nombre d'itérations

Complexité typique = O(n log n)

Réponse finale :

La complexité des algorithmes gloutons est généralement O(n log n) à cause du tri.

Règles appliquées :

• Complexité : Dépend du tri et des itérations postérieures

• Avantage : Plus rapides que les algorithmes dynamiques

• Inconvénient : Ne garantissent pas toujours l'optimalité

5 Glouton vs Optimal

Définition :

Comparaison d'algorithmes : Analyse de la qualité des solutions produites.

Systèmes monétaires : Certains systèmes rendent l'algorithme glouton optimal.

Système

[1, 3, 4] euros

Montant

6 euros

Glouton

4+1+1=3 pièces

Optimal

3+3=2 pièces

Étape 1 : Exemple de système non canonique

Système de pièces: [1, 3, 4] euros

Montant à rendre: 6 euros

Étape 2 : Solution gloutonne

Prendre la plus grande pièce ≤ 6: 4€ → reste 2€

Prendre la plus grande pièce ≤ 2: 1€ → reste 1€

Prendre la plus grande pièce ≤ 1: 1€ → reste 0€

Solution gloutonne: 4 + 1 + 1 = 6 (3 pièces)

Étape 3 : Solution optimale

Meilleure combinaison: 3 + 3 = 6 (2 pièces)

L'algorithme glouton n'est pas optimal!

Étape 4 : Conditions d'optimalité

Pour que l'algorithme glouton soit optimal:

• Le système monétaire doit être canonique (comme l'euro)

• Chaque pièce doit être multiple de la suivante (dans une certaine mesure)

Système	Montant	Glouton	Optimal	Optimalité
[1, 3, 4]	6	4+1+1 (3)	3+3 (2)	✗
[1, 2, 5]	6	5+1 (2)	5+1 (2)	✓
[1, 5, 10]	8	5+1+1+1 (4)	5+1+1+1 (4)	✓
[1, 5, 12, 15]	20	15+5 (2)	15+5 (2)	✓

                // Comparaison glouton vs optimal pour rendu de monnaie
                fonction est_optimal_glouton(pieces):
                  // Vérifier si le système est canonique
                  pour chaque montant dans range(1, 2*max(pieces)):
                    solution_glouton = rendu_monnaie_glouton(montant, pieces)
                    solution_optimale = rendu_monnaie_dynamique(montant, pieces)
                    
                    si len(solution_glouton) != len(solution_optimale):
                      retourner False
                  retourner True
                  
                // Exemple:
                systeme_non_canonique = [1, 3, 4]
                systeme_canonique = [1, 2, 5]
                print(est_optimal_glouton(systeme_non_canonique))  // False
                print(est_optimal_glouton(systeme_canonique))      // True
              

Glouton ≠ Optimal dans certains cas

Réponse finale :

Les algorithmes gloutons ne garantissent pas toujours la solution optimale globale.

Règles appliquées :

• Limitation : Les algorithmes gloutons ne sont pas toujours optimaux

• Conditions : Dépendent du problème et des propriétés structurelles

• Vérification : Tester avec des contre-exemples pour prouver non-optimalité

Cours bien détaillé

\(\text{Choix}_{\text{local}} = \arg\max_{x \in X} f(x)\)

Fonction de choix local

🎯

Définition : Algorithme glouton = stratégie qui fait le meilleur choix local à chaque étape.

📏

Principe : Ne jamais revenir en arrière sur les choix faits.

📋

Applications : Rendu de monnaie, sac à dos fractionnaire, arbres couvrants.

⚡

Avantage : Simplicité d'implémentation et rapidité.

💡

Conseil : Utilisez des algorithmes gloutons pour des problèmes avec propriété de sous-structure optimale

🔍

Attention : Ne garantissent pas toujours la solution optimale globale

⚡

Astuce : Trier les données peut améliorer l'efficacité des algorithmes gloutons

📋

Méthode : Identifier le critère de choix optimal local

✅

Vérification : Testez avec des contre-exemples pour prouver la non-optimalité

🔄

Alternative : Utilisez la programmation dynamique pour garantir l'optimalité

Conditions d'application des algorithmes gloutons :

Propriété de choix glouton : Une solution globalement optimale peut être obtenue en faisant un choix localement optimal
Sous-structure optimale : Une solution optimale contient des sous-solutions optimales
Irreversibilité : Les choix faits ne sont jamais révisés
Efficacité : Le choix optimal local est facile à déterminer

Règles importantes :

Les algorithmes gloutons sont simples mais ne garantissent pas toujours l'optimalité
Ils sont efficaces en temps (généralement O(n log n))
Le tri préalable est souvent nécessaire pour la stratégie gloutonne
La preuve de correction est essentielle pour valider un algorithme glouton

Avantages

Simple

Rapide

Inconvénients

Pas optimal

Parfois

Complexité

O(n log n)

Généralement

\(\text{Solution}_{\text{globale}} = \prod_{i=1}^{n} \text{Choix}_{\text{local}}(i)\)

Construction de la solution globale

Points clés à retenir :

• Les algorithmes gloutons font des choix optimaux locaux sans révision future
• Ils sont efficaces mais ne garantissent pas toujours la solution optimale globale
• Le tri est souvent une étape cruciale dans la stratégie gloutonne
• La preuve de correction est nécessaire pour valider l'approche gloutonne
• Ils sont utiles pour des problèmes avec propriétés de choix glouton et sous-structure optimale

Algorithmes dits gloutonsExercices corrigés

Algorithmes dits gloutons
Exercices corrigés