Algorithme glouton

Un algorithme glouton (connu en anglais sous le nom de greedy algorithm), aussi appelé méthode gloutonne, est une stratégie algorithmique qui, à chaque étape, effectue le meilleur ou le choix optimal (c.-à-d. le plus favorable) dans l'état actuel, en espérant aboutir à un résultat globalement meilleur ou optimal.

Algorithme gloutonComme on le dit souvent, il ne se préoccupe que des bénéfices immédiats et ne considère pas l'optimum global ; le choix effectué n'est qu'une solution localement optimale dans un certain sens.

Imaginez que vous avez une pile de pièces de différentes valeurs (par exemple, 1 yuan, 5 jiao, 1 jiao), et vous devez constituer 1.8 yuan en utilisant le moins de pièces possible.

Une idée très naturelle est :Toujours prendre d'abord la pièce de plus grande valeur,。

Prenez d'abord une pièce de 1 yuan, il reste 0.8 yuan ; puis prenez une pièce de 5 jiao, il reste 0.3 yuan ; enfin, prenez trois pièces de 1 jiao.

Tout au long du processus, à chaque étape nous avons faitLe choix qui semble actuellement le meilleurC'est l'idée centrale de l'algorithme glouton.

Algorithme gloutonIl est comme une personne à courte vue mais décisive :

  • Choix à chaque étapeDans l'état actuel, faire le choix qui semble optimal.
  • Ne considère pas la vision globale: sans considérer l'impact de ce choix sur l'avenir
  • Résultat attenduEspérer que le choix localement optimal puisse conduire à une solution globalement optimale.

Cas concrets :

  • Rendre la monnaie: toujours utiliser d'abord la pièce de plus grande valeur
  • Escalade: toujours se déplacer dans la direction la plus raide
  • Achats: toujours acheter le produit actuellement le plus favorable
  • Sélection d'itinéraire: toujours choisir le chemin actuellement le plus court

Caractéristiques de l'algorithme glouton

  • Propriété du choix gloutonLa solution optimale à chaque étape peut être déduite des solutions optimales locales des étapes précédentes. Les choix ultérieurs n'affecteront pas les choix antérieurs.
  • Sous-structure optimaleLa solution optimale d'un problème contient les solutions optimales de ses sous-problèmes. C'est également une propriété de la programmation dynamique, mais un algorithme glouton choisit de manière gloutonne la solution optimale d'un sous-problème à chaque étape.
Fonctionnalités Description Avantages Inconvénients
Optimum local Choisir la solution optimale actuelle à chaque étape Simple et intuitif Peut ne pas être globalement optimal
Irréversible Impossible de regretter après avoir choisi Prise de décision rapide Tendance à rester bloqué dans des optimums locaux
Efficacité A généralement une faible complexité temporelle Très pratique Applicabilité limitée
Implémentation simple Logique claire et facile à comprendre Facile à coder Nécessite de prouver la correction

Différences avec la programmation dynamique

C'est un point que les débutants trouvent souvent déroutant. Comparons-les avec un tableau :

Fonctionnalités Algorithme glouton Programmation dynamique
Base de décision Faire le choix optimal actuel à chaque étape,Aucun retour en arrière。 Le choix de chaque étape dépend de la solution des sous-problèmes, enregistre les résultats intermédiaires et peut comparer plusieurs choix.
Garantie de solution optimale Il peut ne pas produire la solution optimale globale ; le problème lui-même doit posséder la propriété de choix glouton. Permet généralement d'obtenir la solution optimale globale.
Efficacité Efficace, généralement avec une complexité temporelle plus faible. Relativement faible, car des sous-problèmes qui se chevauchent doivent être résolus.
Scénarios applicables Le problème possède la propriété de choix glouton et une sous-structure optimale, comme le codage de Huffman et les arbres couvrants minimaux. Le problème possède une sous-structure optimale et des sous-problèmes se chevauchant, comme le problème du sac à dos et les plus courts chemins.

En termes simples,la programmation dynamique consiste à « réfléchir avant d'agir » et sacrifie les intérêts immédiats pour des avantages à long terme ; les algorithmes gloutons consistent à « manger, boire et se réjouir aujourd'hui » et ne recherchent que des avantages immédiats.


Cadre de base de l'algorithme glouton

Les algorithmes gloutons n'ont pas de gabarit de code fixe, mais leur idée peut se résumer aux étapes suivantes :

  1. Construire un modèle mathématique: abstraire le problème du monde réel en un problème mathématique.
  2. Définir une stratégie gloutonneDéterminer le critère de choix de la « solution optimale » à chaque étape. C'est le cœur et la difficulté de l'algorithme.
  3. Prouver la stratégie gloutonneProuver que la stratégie gloutonne définie peut conduire à une solution globalement optimale (facultatif mais important ; pour les problèmes algorithmiques, vous devez généralement en comprendre la correction).
  4. Résolution itérativeSelon la stratégie, à partir de l'état initial, effectuez des choix gloutons étape par étape jusqu'à obtenir une solution au problème.

Un cadre général de pseudocode est le suivant :

Exemple

def greedy_algorithm(problem):
    # 1. Initialisation : peut inclure le tri, la création d'un conteneur de résultat, etc.
    solution = []
    # 2. Parcourir toutes les options ; généralement, il faut d'abord trier selon une certaine règle
    for item in sorted(problem.items, key=Règle de la stratégie gloutonne):
        # 3. Choix glouton : si le choix actuel satisfait la condition, l'adopter
        if is_feasible(solution, item):
            solution.append(item)
    # 4. Retourner la solution finale construite
    return solution

Problèmes classiques et exemples de code

Découvrons l'application des algorithmes gloutons à travers quelques problèmes classiques. Pour chaque problème, nous allons : 1) analyser le problème et la stratégie gloutonne ; 2) fournir le code complet ; 3) fournir une explication ligne par ligne.

Exemple 1 : problème du rendu de monnaie

Description du problème: Supposons que le système de pièces soit [100, 50, 20, 10, 5, 1] (unité : centimes), et que nous devions rendre la monnaieamountcentimes, trouver le nombre minimum de pièces nécessaires.

Stratégie gloutonne:Chaque fois, choisir la plus grande pièce dont la valeur faciale ne dépasse pas le montant restant.Pour le système monétaire RMB, cette stratégie est efficace.

Implémentation du code:

Exemple

def coin_change_greedy(coins, amount):
    """
Utiliser l'algorithme glouton pour résoudre le problème du rendu de monnaie (pour un système de pièces spécifique)
:param coins: list[int], liste des valeurs faciales des pièces, doit être triée par ordre décroissant
:param amount: int, montant total pour lequel rendre la monnaie
:return: list[int], liste des dénominations de pièces utilisées
    """

    coins.sort(reverse=True)  # S'assurer que les pièces sont triées par dénomination, de la plus élevée à la plus faible
    result = []  # Utilisé pour stocker les pièces pour rendre la monnaie
    remaining = amount  # Montant restant pour lequel il faut rendre la monnaie

    for coin in coins:
        # Lorsque la dénomination de la pièce actuelle est inférieure ou égale au montant restant, l'utiliser autant que possible
        while remaining >= coin:
            result.append(coin)
            remaining -= coin  # Déduire la dénomination de la pièce actuelle du montant restant

    # Vérifier si la monnaie est rendue exactement
    if remaining == 0:
        return result
    else:
        # Pour les cas où l'appoint exact ne peut pas être fait (bien que cela ne se produira pas dans ce système de pièces)
        return None

# Données de test
test_coins = [100, 50, 20, 10, 5, 1]
test_amount = 186  # 1 yuan 8 jiao 6 fen

change = coin_change_greedy(test_coins, test_amount)
print(f"Monnaie pour {test_amount} fen, pièces nécessaires : {change}")
print(f"Nombre de pièces : {len(change)}")
# Sortie : monnaie pour 186 fen, pièces nécessaires : [100, 50, 20, 10, 5, 1]
# Nombre de pièces : 6

Explication du code:

  • Ligne 8 :coins.sort(reverse=True)Il s'agit de la préparation clé pour la stratégie gloutonne, garantissant que l'on considère toujours les dénominations les plus élevées en premier.
  • Lignes 12-15 :whileLa boucle garantit que tant que la dénomination actuelle peut encore être utilisée, nous continuons à l'utiliser ; cela met en œuvre le choix glouton « autant que possible ».
  • Lignes 18-22 : Vérifier le résultat final pour s'assurer que le montant correspond exactement.

Remarque importante: Algorithme glouton pour résoudre le problème du rendu de monnaieNe produit pas toujours la solution optimalePar exemple, si le système de pièces est [25, 20, 10, 5, 1] et que vous devez rendre 40 cents, la méthode gloutonne choisirait 25+10+5 (trois pièces), mais la solution optimale est 20+20 (deux pièces).Ce n'est que dans des systèmes monétaires spécifiques (comme le RMB) que la stratégie gloutonne est efficace.

Exemple 2 : Problème d'ordonnancement d'intervalles

Description du problèmeÉtant donné de nombreuses réunions (chacune avec une heure de début et une heure de fin), comment les organiser pour maximiser le nombre de réunions que vous pouvez tenir dans une salle de réunion ?

Stratégie gloutonne:Choisir à chaque fois la réunion qui se termine le plus tôtCela laisse plus de temps pour les réunions suivantes.

Implémentation du code:

Exemple

def interval_scheduling(intervals):
    """
Résolution du problème des intervalles non chevauchants maximaux (ordonnancement d'intervalles)
:param intervals: liste de [start, end], liste d'intervalles
:return: liste de [start, end], liste d'intervalles sélectionnés
    """

    # 1. Trier par heure de fin par ordre croissant
    intervals_sorted = sorted(intervals, key=lambda x: x[1])
   
    selected = []  # Stocker les intervalles sélectionnés
    last_end_time = -float('inf')  # Initialiser l'heure de fin de l'intervalle sélectionné précédent
   
    for interval in intervals_sorted:
        start, end = interval
        # 2. Sélection gloutonne : si l'heure de début de l'intervalle courant n'est pas antérieure à l'heure de fin de l'intervalle sélectionné précédent, le sélectionner
        if start >= last_end_time:
            selected.append(interval)
            last_end_time = end  # Mettre à jour la dernière heure de fin
   
    return selected

# Données de test : chaque sous-liste représente une réunion [heure de début, heure de fin]
test_intervals = [
    [1, 3], [2, 4], [3, 5], [4, 6], [5, 7],
    [1, 2], [2, 3], [1, 4]
]

result = interval_scheduling(test_intervals)
print(Nombre maximum de réunions pouvant être planifiées (après tri par heure de fin) :)
for meeting in result:
    print(fRéunion [{meeting[0]}, {meeting[1]}])
print(fTotal {len(result)} réunions)
# Une sortie possible (car l'ordre après tri peut différer, mais le nombre est optimal) :
# Réunion [1, 2]
# Réunion [2, 3]
# Réunion [3, 5] ou [4, 6], etc.
# Total 4 réunions

Explication du code:

  • Ligne 10 :sorted(intervals, key=lambda x: x[1])C'est le cœur de l'implémentation de la stratégie gloutonne : trier par heure de fin.
  • Lignes 16-19 :if start >= last_end_timeIl s'agit d'une vérification de faisabilité, garantissant que la réunion actuelle ne chevauche pas les réunions sélectionnées.
  • La complexité temporelle de cet algorithme est O(n log n), principalement due au tri.

Exemple 3 : Codage de Huffman - Concept et implémentation simplifiée

Le codage de Huffman est un algorithme glouton pour la compression de données sans perte. Son idée centrale est :Attribuer des codes plus courts aux caractères de fréquence plus élevée et des codes plus longs aux caractères de fréquence plus faible.。

Stratégie gloutonneFusionner de manière répétée les deux nœuds ayant les plus petites fréquences pour construire un arbre binaire.

Comme une implémentation complète est assez longue, nous montrons ici son processus central de fusion gloutonne :

Exemple

import heapq

class Node:
    """Classe de nœud d'arbre de Huffman"""
    def __init__(self, char, freq):
        self.char = char  # Caractère (nœuds feuilles uniquement)
        self.freq = freq  # Fréquence
        self.left = None
        self.right = None
   
    # Pour permettre la comparaison dans le tas, définir des méthodes de comparaison
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(char_freq):
    """
Construire l'arbre de Huffman
:param char_freq: dict, caractères et leurs fréquences, par ex. {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
:return: Node, le nœud racine de l'arbre de Huffman
    """

    # 1. Initialisation : créer un nœud feuille pour chaque caractère et le placer dans un tas min (file de priorité)
    heap = [Node(char, freq) for char, freq in char_freq.items()]
    heapq.heapify(heap)  # Convertir la liste en un tas min
   
    # 2. Fusion gloutonne : lorsqu'il y a plus d'un nœud dans le tas
    while len(heap) > 1:
        # Extraire les deux nœuds ayant les plus petites fréquences
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
       
        # Créer un nouveau nœud interne dont la fréquence est la somme des fréquences des enfants
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
       
        # Réinsérer le nouveau nœud dans le tas
        heapq.heappush(heap, merged)
   
    # Le dernier nœud restant dans le tas est la racine de l'arbre de Huffman
    return heap[0] if heap else None

# Données de test
test_freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
root = build_huffman_tree(test_freq)
print("Construction de l'arbre de Huffman terminée ! Fréquence racine =", root.freq if root else 0)
# Sortie : Construction de l'arbre de Huffman terminée ! Fréquence racine = 100

Visualisation de l'algorithmeLa figure suivante montre les premières étapes de fusion lors de la construction de l'arbre de Huffman à l'aide des données de test ci-dessus :

Explication illustréeL'algorithme sélectionne toujours les deux nœuds ayant les plus petites fréquences parmi tous les nœuds disponibles (au départ les nœuds feuilles, puis également les nœuds internes) et les fusionne en un nouveau nœud interne. Ce processus est répété jusqu'à ce qu'un arbre binaire complet soit formé. Les nœuds feuilles de cet arbre correspondent aux caractères d'origine, et le chemin de la racine à une feuille (branche gauche = 0, branche droite = 1) constitue le code de Huffman de ce caractère.


Preuve de justesse de l'algorithme glouton

Comment déterminer si un problème peut être résolu avec un algorithme glouton ? En général, il faut prouver les deux points suivants :

  1. Propriété du choix gloutonOn peut prouver par récurrence mathématique ou par l'absurde que le choix optimal à la première étape est contenu dans une solution optimale globale.
  2. Sous-structure optimaleProuver qu'après avoir effectué le premier choix glouton, le problème d'origine se réduit à un problème de plus petite taille.Sous-problèmes de même type。

avecProblème d'ordonnancement d'intervallesIdée de preuve en utilisant ... comme exemple :

  • Choix gloutonSoit l'intervalle ayant l'heure de fin la plus précoce parmi tous les intervallesi. Il existe une solution optimale contenant l'intervalle ...i。
    • Preuve: Supposons qu'une solution optimale ne le contienne pas.i. Soit le premier intervalle de cette solution optimale ...j. Carise termine le plus tôt, donc remplaçons ... par ...iremplacementjil n'entre pas en conflit avec les autres intervalles, et la taille de la solution reste inchangée, donc elle contientiLa solution résultante est également optimale.
  • Sous-structure optimale: Lors de la sélection des intervallesiEnsuite, le problème restant est, parmi tous les intervalles qui ... avec ...itrouver la solution optimale parmi des intervalles non chevauchants. Cela constitue un sous-problème du problème d'origine.

Exercices pratiques

Maintenant, essayez de résoudre les problèmes suivants en utilisant l'algorithme glouton pour renforcer votre compréhension.

Exercice 1 : Jump Game

Problème: Étant donné un tableau d'entiers non négatifsnumsVous êtes initialement au premier indice du tableau. Chaque élément du tableau représente la longueur maximale que vous pouvez sauter depuis cette position. Déterminez si vous pouvez atteindre le dernier indice.Exemple:nums = [2,3,1,1,4], retourneTrue(Sautez 1 pas de l'indice 0 à l'indice 1, puis sautez 3 pas jusqu'au dernier indice).Indice de stratégie gloutonneAu lieu de simuler la distance à sauter à chaque étape, maintenez unePosition la plus lointaine accessible。

Exercice 2 : Attribuer des cookies

ProblèmeIl y a un groupe d'enfants et un tas de cookies ; chaque enfant a une valeur d'appétitg[i], chaque cookie a une tailles[j]Un enfant est satisfait seulement si la taille du cookie >= l'appétit de l'enfant. Trouvez le nombre maximal d'enfants pouvant être satisfaits.Exemple:g = [1,2,3], s = [1,1], sortie1。 Indice de stratégie gloutonne: Pour satisfaire plus d'enfants,Utilisez le plus petit cookie pour satisfaire l'enfant ayant le plus petit appétit.(ou réfléchissez dans l'autre sens).

Exercice 3 : Meilleur moment pour acheter et vendre des actions II

Problème: Étant donné un tableauprices, oùprices[i]est le ... d'une action donnée au ...iLe prix pour chaque jour. Vous pouvez effectuer autant de transactions que vous le souhaitez (c'est-à-dire acheter et vendre une action), mais vous ne pouvez pas participer à plusieurs transactions en même temps (vous devez vendre l'action précédente avant d'en acheter une nouvelle). Calculez le profit maximal que vous pouvez obtenir.Exemple:prices = [7,1,5,3,6,4], sortie7(Acheter à 1 et vendre à 5, profit 4 ; acheter à 3 et vendre à 6, profit 3 ; profit total 7).Indice de stratégie gloutonneLe profit peut être décomposé en différences de prix quotidiennes. Tant quele prix d'aujourd'hui est supérieur à celui d'hier, prenez cette différence comme profit.。

autres extensions