Algorithmes gloutons
#Algorithmes gloutons
Les algorithmes gloutons (ou "greedy algorithms" en anglais) sont une classe d'algorithmes qui prennent des décisions locales optimales à chaque étape dans l'espoir d'atteindre une solution globale optimale. Bien que cette approche ne garantisse pas toujours l'optimalité, elle est souvent efficace et donne de bons résultats dans de nombreux cas.
#Principe
Un algorithme glouton suit une heuristique simple : à chaque étape, il fait le choix qui semble le meilleur sur le moment, sans reconsidérer les décisions passées. Cette approche "myope" peut être très efficace pour certains problèmes.
#Caractéristiques
- Choix glouton : À chaque étape, l'algorithme fait un choix qui semble optimal localement
- Sous-structure optimale : Une solution optimale au problème contient des solutions optimales aux sous-problèmes
- Pas de retour en arrière : Une fois qu'un choix est fait, il n'est jamais révisé
#Exemple classique : Rendu de monnaie
Un problème classique résolu par un algorithme glouton est le rendu de monnaie : trouver le nombre minimal de pièces pour rendre une certaine somme.
1def rendre_monnaie_glouton(montant, pieces):2 """3 Rendre la monnaie avec un algorithme glouton4 pieces doit être trié par ordre décroissant5 """6 resultat = []7 for piece in pieces:8 while montant >= piece:9 resultat.append(piece)10 montant -= piece11 return resultat12 13# Exemple14pieces = [100, 50, 20, 10, 5, 2, 1] # en centimes#Algorithme de Dijkstra
L'algorithme de Dijkstra est un algorithme glouton utilisé pour trouver les chemins les plus courts dans un graphe pondéré avec des poids positifs.
#Animation interactive
Voici une animation qui illustre le fonctionnement de l'algorithme de Dijkstra :
#Implémentation en Python
1import heapq2 3def dijkstra(graphe, depart):4 """5 Algorithme de Dijkstra pour trouver les chemins les plus courts6 depuis un nœud de départ vers tous les autres nœuds7 """8 # Initialisation des distances9 distances = {noeud: float('infinity') for noeud in graphe}10 distances[depart] = 011 12 # File de priorité pour les nœuds à visiter13 file_priorite = [(0, depart)]14 chemins = {noeud: [] for noeud in graphe}#Problèmes où les algorithmes gloutons fonctionnent bien
- Arbre couvrant minimal (Kruskal, Prim)
- Planification d'intervalles
- Problème du sac à dos fractionnel
- Codage de Huffman
- Sélection d'activités
#Limitations
Les algorithmes gloutons ne garantissent pas toujours une solution optimale. Par exemple, pour le problème du sac à dos 0/1, un algorithme glouton basé sur le ratio valeur/poids ne donne pas toujours la solution optimale.
#Exercice : Planification d'intervalles
Implémentez un algorithme glouton pour résoudre le problème de planification d'intervalles : sélectionner le maximum d'intervalles qui ne se chevauchent pas.
#Instructions
- Triez les intervalles par date de fin croissante
- Sélectionnez le premier intervalle
- Pour chaque intervalle suivant, s'il ne chevauche pas le dernier intervalle sélectionné, sélectionnez-le
#Exemple de code
1def planification_intervalles(intervalles):2 """3 Planification d'intervalles avec un algorithme glouton4 intervalles : liste de tuples (début, fin)5 """6 # Trier par date de fin croissante7 intervalles_tries = sorted(intervalles, key=lambda x: x[1])8 9 selection = []10 derniere_fin = 011 12 for debut, fin in intervalles_tries:13 # Si l'intervalle ne chevauche pas le dernier sélectionné14 if debut >= derniere_fin:#Complexité
La complexité des algorithmes gloutons dépend du problème spécifique, mais ils sont généralement efficaces :
- Rendu de monnaie : O(n) où n est le nombre de pièces
- Dijkstra : O((V + E) log V) où V est le nombre de sommets et E le nombre d'arêtes
- Planification d'intervalles : O(n log n) pour le tri
Les algorithmes gloutons sont précieux pour leur simplicité et leur efficacité, en particulier lorsqu'ils fournissent des solutions optimales ou proches de l'optimalité.