Les algorithmes gloutons sont des algorithmes souvent simples, qui donnent une solution pas forcément exacte à un problème. C'est un peu "la solution évidente qui en fait ne fonctionne pas" dans la plupart des cas.

Pour certaines applications, on va se satisfaire d'un tel algorithme. On va présenter deux exemples d'algorithmes gloutons.

Ressources : Eduscol, clogique.fr.

I. Problème du rendu de monnaie

a) Présentation

Idée : toujours rendre la plus grande pièce possible d'abord. C'est un algorithme "glouton", car il essaye de prendre "le plus possible" à chaque moment, sans anticiper la suite ni revenir en arrière.

On cherche à écrire une fonction Python qui prend en argument :

• une liste d'entiers [v1, ..., vn] ;
• un entier S.

Et qui renvoie la liste d'entiers [x1, ..., xn] obtenue par la méthode gloutonne.

pieces = [1, 2, 5, 10, 20, 50, 100, 500]
S = 34

def glouton(pieces, S):
    pass

def glouton(pieces, S):
    """
    Renvoie une liste de la quantité de chaque pièce utilisée pour rendre S
    avec la méthode gloutonne
    """
    X = [0 for _ in pieces]
    i = len(pieces) - 1 #indice de la dernière pièce utilisée
    while S > 0:
        while pieces[i] > S:
            i -= 1
        S -= pieces[i]
        X[i] += 1
    return X

def glouton(pieces, S):
    """
    Renvoie une liste de la quantité de chaque pièce utilisée pour rendre S
    avec la méthode gloutonne
    """
    X = [0 for _ in pieces]
    i = len(pieces) - 1 #indice de la dernière pièce utilisée
    while S > 0:
        while pieces[i] > S:
            i -= 1
        S -= pieces[i]
        X[i] += 1
    return X

print(glouton([1, 2, 5, 10, 20, 50, 100, 500], 34))
print(glouton([1, 3, 4], 6))

b) Non optimalité

Sur notre exemple des €, il se trouve que l'algorithme glouton donne toujours la solution optimale. On dit que c'est un système monétaire canonique. Mais ce n'est pas toujours le cas !

L'exemple a peut-être l'air un petit peu "construit", mais des systèmes non canoniques ont bien été en circulation dans l'histoire.

On ne connaît pas de condition nécessaire et suffisante simple pour qu'un système soit canonique.

II. Construction d'emploi du temps

Vous allez dans une convention, un séminaire, etc., où un certain nombre d'événements et de conférences se produisent. Vous souhaitez assister à un maximum de conférences.

Par exemple, ici, on peut assister à 2 conférences maximum. Comment choisir à quelles conférences assister ?

On peut imaginer plusieurs algorithmes gloutons différents dans ce cas ! Dans tous les cas, il s'agira de trier les conférences selon un certain critère, et de prendre la "meilleure" conférence selon ce critère de manière répétitive.

a) Première solution : dans l'ordre de début

Contre-exemple : une très longue conférence dès le début, puis plein de petites qui lui sont superposées :

b) Deuxième solution : les plus courtes d'abord

A priori, si une conférence est courte, elle doit être plus facile à caser dans un emploi du temps. Mais ce n'est pas optimal non plus !

Ici, C2 est la plus courte, mais elle empêche de choisir C1 et C3.

c) Troisième solution : celles qui interfèrent avec le moins d'autres conférences

A priori, si une conférence a peu de conflits, elle est plus intéressante.

Ici, C1 a le moins de conflits (2, contre 3 ou 4 pour les autres). Mais elle empêche de choisir C2 et C3, ce qui nous mène à un choix avec 3 conférences (alors qu'on peut en faire 4 !).

d) Quatrième solution : dans l'ordre de fin

Sur l'exemple précédent, on prend C4 (qui finit en premier), puis C2, C3 et C5 : on trouve bien 4 conférences.

Essayez de trouver un contre-exemple. Compliqué, non ?

Eh bien en fait, c'est optimal ! Pourquoi ?

Exercices

def emploi_du_temps(conferences):
    triees = sorted(conferences, key=lambda c: c[1])   # tri par heure de fin
    choisies = []
    fin_derniere = float("-inf")
    for (debut, fin) in triees:
        if debut >= fin_derniere:   # compatible avec la dernière conférence choisie
            choisies.append((debut, fin))
            fin_derniere = fin
    return choisies

emploi_du_temps([(0, 2), (2.5, 5.5), (5, 10), (9.5, 12.5), (13, 15)])