Algorithme Glouton

Un algorithme glouton est une méthode de résolution de problèmes qui repose sur une approche myope : il choisit à chaque étape l’option qui semble la meilleure localement, sans se soucier des conséquences futures. Cette stratégie est simple, intuitive, et peut être étonnamment efficace dans certains cas. Cependant, elle ne garantit pas toujours une solution optimale.

Prenons un exemple classique pour illustrer ce concept : le problème de la monnaie. Supposons que l’on doive rendre une certaine somme avec le moins de pièces possible. En France, les pièces disponibles sont de 1, 2, 5, 10, 20 et 50 centimes, ainsi que 1 et 2 euros.

L’idée gloutonne est la suivante : à chaque étape, on choisit la pièce de plus grande valeur possible sans dépasser le montant restant à rendre. On répète ce processus jusqu’à ce que la somme soit atteinte.

def rendre_monnaie(somme, pieces_disponibles):
    pieces_triees = tri_decroissant(pieces_disponibles[:])  # copie de la liste originale
    rendu = []  # liste pour stocker les pièces à rendre

    # Pour chaque pièce, on en ajoute autant que possible sans dépasser la somme
    for piece in pieces_triees:
        while somme >= piece:
            somme -= piece  # on soustrait la valeur de la pièce de la somme restante
            rendu.append(piece)  # on ajoute la pièce au rendu
    return rendu  # on retourne la liste des pièces utilisées

Pour trier les valeurs on peu utiliser la fonction :

def tri_decroissant(liste):
    for i in range(len(liste)):
        max_index = i
        # On cherche l'indice de la plus grande valeur dans le reste de la liste
        for j in range(i + 1, len(liste)):
            if liste[j] > liste[max_index]:
                max_index = j
        # On échange l'élément courant avec le maximum trouvé
        liste[i], liste[max_index] = liste[max_index], liste[i]
    return liste

Exemple :

objets = [(10, 60), (20, 100), (30, 120)]
print(sac_a_dos_fractionnaire(50, objets))
# Résultat attendu : 240.0

Ce résultat est correct ici, car le système de pièces est canonique, c’est-à-dire que la solution gloutonne est toujours optimale. Mais ce n’est pas toujours le cas. Si on utilisait des pièces de valeurs non standards (par exemple 1, 3 et 4), la solution gloutonne pourrait ne pas donner le meilleur résultat.

Un autre exemple typique où la stratégie gloutonne est appliquée avec succès est le problème du sac à dos fractionnaire. On cherche à remplir un sac d’une capacité donnée avec des objets ayant chacun un poids et une valeur, de façon à maximiser la valeur totale. Contrairement au problème du sac à dos classique, ici on peut prendre une fraction d’un objet. L’approche gloutonne consiste à choisir les objets selon le meilleur ratio valeur/poids en priorité.

# Fonction pour trier les objets selon leur ratio valeur/poids en ordre décroissant
def tri_decroissant_par_ratio(objets):
    for i in range(len(objets)):
        max_index = i
        for j in range(i + 1, len(objets)):
            # Calcul du ratio valeur/poids pour comparer
            ratio_j = objets[j][1] / objets[j][0]
            ratio_max = objets[max_index][1] / objets[max_index][0]
            if ratio_j > ratio_max:
                max_index = j
        # Échange des objets pour placer celui avec le meilleur ratio en premier
        objets[i], objets[max_index] = objets[max_index], objets[i]
    return objets

# Fonction principale pour résoudre le problème du sac à dos fractionnaire
def sac_a_dos_fractionnaire(capacite, objets):
    # On trie les objets selon leur rentabilité (valeur/poids)
    objets_tries = tri_decroissant_par_ratio(objets[:])  # copie pour ne pas modifier la liste d'origine
    valeur_totale = 0  # valeur totale que l’on va accumuler

    for poids, valeur in objets_tries:
        if capacite >= poids:
            # Si on peut prendre l'objet en entier
            capacite -= poids
            valeur_totale += valeur
        else:
            # Sinon, on prend une fraction de l'objet pour remplir le sac
            fraction = capacite / poids
            valeur_totale += valeur * fraction
            break  # le sac est plein, on peut arrêter
    return valeur_totale

Chaque objet est représenté par un tuple (poids, valeur). L’algorithme trie les objets selon le meilleur rendement, puis ajoute autant que possible au sac. Dès que le sac est presque plein, il ajoute une fraction de l’objet suivant.

Ce type de problème montre bien l’efficacité d’une approche gloutonne quand les conditions sont favorables. En revanche, dans le cas du sac à dos entier (où les objets sont indivisibles), cette méthode ne garantit pas l’optimalité.

Il est essentiel, avant d’appliquer un algorithme glouton, de vérifier si le problème satisfait la propriété d’optimalité gloutonne, c’est-à-dire que des choix locaux mènent bien à une solution globale optimale. Si cette propriété n’est pas respectée, des algorithmes plus complexes comme la programmation dynamique peuvent être nécessaires.

L'algorithme de Glouton

All work licensed under CC BY-NC-SA 4.0