Algorithmes gloutons

#Algorithmes gloutonsCopier le lien

#PrincipeCopier le lien

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éristiquesCopier le lien

• 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 monnaieCopier le lien

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 DijkstraCopier le lien

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 interactiveCopier le lien

Voici une animation qui illustre le fonctionnement de l'algorithme de Dijkstra :

#Implémentation en PythonCopier le lien

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 bienCopier le lien

1. Arbre couvrant minimal (Kruskal, Prim)
2. Planification d'intervalles
3. Problème du sac à dos fractionnel
4. Codage de Huffman
5. Sélection d'activités

#LimitationsCopier le lien

Les algorithmes gloutons ne garantissent pas toujours une solution optimale. Par exemple, pour le sac à dos 0/1, un tri par ratio valeur/poids peut rater l’optimum. Cherchez un argument d’échange/matroïde ou une borne d’approximation.

#Exercice : Planification d'intervallesCopier le lien

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.

#InstructionsCopier le lien

1. Triez les intervalles par date de fin croissante
2. Sélectionnez le premier intervalle
3. Pour chaque intervalle suivant, s'il ne chevauche pas le dernier intervalle sélectionné, sélectionnez-le

#Exemple de codeCopier le lien

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éCopier le lien

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é.