TP 7 : Algorithmes gloutons

Voici plusieurs méthodes algorithmiques très utilisés en informatique :

• Algorithmes gloutons
• Programmation dynamique
• Diviser pour régner
• ...

Dans ce TP, on s'intéresse aux algorithmes gloutons, qui s'utilisent souvent sur des problèmes d'optimisation (où on cherche à maximiser quelque chose avec des contraintes).

Un algorithme est glouton lorsqu'il effectue, à chaque étape, le choix qui semble le meilleur à ce moment-là et qui ne revient jamais sur sa décision.

La notion d'algorithme glouton est donc assez vague : nous allons l'illustrer avec quelques exemples.

Petits exercices de rappel¶

Cette partie est seulement pour les élèves en difficulté. Les autres peuvent la passer.

Exercice

Écrire une fonction pour calculer la somme des éléments d'une liste.

Solution

In [1]:

def somme(L):
    s = 0
    for i in L:
        s += i
    return s

def somme(L): s = 0 for i in L: s += i return s

Exercice

Écrire une fonction pour déterminer si une liste est triée dans l'ordre croissant.

Solution

In [2]:

def croissant(L):
    for i in range(len(L)-1):
        if L[i] > L[i+1]:
            return False
    return True

def croissant(L): for i in range(len(L)-1): if L[i] > L[i+1]: return False return True

Rendu de monnaie¶

On suppose avoir des pièces de valeur $p_1$, ..., $p_n$ et on veut rendre la monnaie sur $c$ euros, avec le nombre minimum de pièces. Chaque pièce est disponible en quantité infinie.
Par exemple, si on a des pièces de valeur 1, 2, 4, alors on a plusieurs possibilités pour rendre $c = 6$€ : $4 + 2$, $4 + 1 + 1$, $2 + 2 + 2$... La meilleure solution est $4 + 2$, puisqu'elle utilise le nombre minimum de pièces.
On s'intéresse à l'algorithme glouton qui consiste à rendre utiliser la plus grande pièce à chaque fois.
Par exemple, pour rendre $9$€ avec des pièces de $1$, $2$ et $4$ :

1. On rend une pièce de $4$€, il reste $5$€ à rendre.
2. On rend une pièce de $4$€, il reste $1$€.
3. On ne peut pas rendre $4$€ (qui est supérieur à $1$).
4. On ne peut pas rendre $2$€ (qui est supérieur à $1$).
5. On rend $1$€, il reste $0$€ et on a terminé (en utilisant $3$ pièces).

Exercice

Écrire une fonction rendre_monnaie(c, pieces) qui rend une liste des pièces obtenues avec l'algorithme glouton pour rendre la valeur $c$ avec des pièces dans la liste pieces.
Par exemple, rendre_monnaie(6, [1, 2, 4]) doit renvoyer [4, 2] et rendre_monnaie(5, [1, 3, 7]) doit renvoyer [3, 1, 1].
On pourra s'inspirer du code suivant :

def rendre_monnaie(c, pieces):
    pieces.sort(key=lambda x: -x) # tri par ordre décroissant
    rendu = [] # liste des pièces utilisées par l'algo. glouton
    for ...: # parcours de la liste pieces
        ... # à compléter
    return rendu

Solution

In [26]:

def rendre_monnaie(c, pieces):
    pieces.sort(key=lambda x: -x)
    rendu = []
    for p in pieces:
        while p <= c:
            rendu.append(p)
            c -= p
    return rendu

rendre_monnaie(5, [1, 3, 7])

def rendre_monnaie(c, pieces): pieces.sort(key=lambda x: -x) rendu = [] for p in pieces: while p <= c: rendu.append(p) c -= p return rendu rendre_monnaie(5, [1, 3, 7])

Out[26]:

[3, 1, 1]

Exercice

Trouver un exemple simple dans lequel l'algorithme glouton n'est pas optimal.
Il faut donc trouver des valeurs de pièces $p_1$, ..., $p_n$ et de $c$ tel que le nombre de pièces utilisées par l'algorithme glouton n'est pas le minimum possible.

Solution

On considère des pièces $1, 3, 4$ et $c = 6$. Alors l'algorithme glouton va rendre $4 + 1 + 1$ alors que l'optimum est $4 + 2$.

Remarque : Un système de monnaie est dit canonique si cet algorithme glouton est optimal. La quasi-totalité des monnaies utilisées dans le monde sont canoniques.

Allocation de salles pour des cours¶

Dans ce problème, on doit construire un emploi du temps. Il faut assigner une salle à chaque cours de façon à ne pas avoir 2 cours qui se déroulent dans la même salle au même moment.

En Python, chaque cours sera un couple $(d, f)$ avec $d$ l'heure de début et $f$ de fin et une salle sera un entier. On rappelle que si c est un couple, on accède à son premier élément avec c[0] et aux deuxième avec c[1].

Exercice

Écrire une fonction intersecte pour déterminer si deux cours se chevauchent.
Par exemple, intersecte((1, 3), (2, 4)) doit renvoyer True mais intersecte((1, 2), (3, 5)) doit renvoyer False.

Solution

In [8]:

def intersecte(c1, c2):
    return (c1[0] <= c2[0] and c1[1] >= c2[0]) or (c2[0] <= c1[0] and c2[1] >= c1[0])

assert intersecte((1, 3), (2, 4)) and not intersecte((1, 2), (3, 5))

def intersecte(c1, c2): return (c1[0] <= c2[0] and c1[1] >= c2[0]) or (c2[0] <= c1[0] and c2[1] >= c1[0]) assert intersecte((1, 3), (2, 4)) and not intersecte((1, 2), (3, 5))

Voici un exemple de cours (où il y a un cours de $9$h à $11$h, un cours de $12$h à $15$h...) :

Voici un exemple d'assignement :

Chaque couleur correspond à une salle : il y a donc $6$ salles en tout.

Exercice

Trouver une solution avec $4$ classes seulement (c'est l'optimum).

On s'intéresse à un algorithme glouton qui consiste à :

1. Trier les cours par ordre de début croissant
2. Pour chaque cours $c$ : utiliser pour $c$ une salle déjà existante si possible, et utiliser une nouvelle salle sinon.

Ainsi, sur l'exemple ci-dessus, on considère les cours dans l'ordre $2, 0, 4, 7, 5, 9, 6, 8, 3$ (si $2$ cours commencent en même temps, on les prends dans un ordre quelconque). On commence donc d'abord par le cours $2$, qu'on assigne à la salle $0$, puis on considère le cours $0$ qu'on assigne à la salle $1$ (car le cours $0$ intersecte le cours $1$ donc on ne peut pas les mettre dans la même salle)...

Remarque : On pourrait montrer que cet algorithme glouton renvoie l'optimum.

Exercice

Écrire une fonction intersecte_list telle que, si c est un cours et L est une liste de cours, intersecte_list(c, L) renvoie True si c chevauche un des cours de L.
Par exemple, intersecte_list((1, 3), [(2, 5), (4, 6)]) renvoie True mais intersecte_list((1, 3), [(4, 6), (5, 7)]) renvoie False.

Solution

In [9]:

def intersecte_list(c, L):
    for cours in L:
        if intersecte(c, cours):
            return True
    return False

assert intersecte_list((1, 3), [(2, 5), (4, 6)]) and not intersecte_list((1, 3), [(4, 6), (5, 7)])

def intersecte_list(c, L): for cours in L: if intersecte(c, cours): return True return False assert intersecte_list((1, 3), [(2, 5), (4, 6)]) and not intersecte_list((1, 3), [(4, 6), (5, 7)])

Pour stocker les assignations de salle à chaque cours, on utilisera une liste salles telle que, si i est un numéro de salle, salles[i] est une liste contenant les cours qui se déroulent dans la salle i.
Par exemple, dans l'exemple de la figure ci-dessus, si 0 correspond à la salle jaune, salles[0] est égale à [(9, 11), (12, 15)].

Exercice

Écrire une fonction choisir_salle telle que, si c est un cours, choisir_salle(c, salles) renvoie une salle disponible pour c, ou -1 si aucune salle n'est disponible.
Par exemple, choisir_salle((7, 10), [[(9, 11)], [(12, 15)]]) doit renvoyer 1 mais choisir_salle((7, 10), [[(8, 10)], [(9, 12)]]) doit renvoyer -1.

Solution

In [10]:

def choisir_salle(c, salles):
    for s in range(len(salles)):
        if not intersecte_list(c, salles[s]):
            return s
    return -1

assert choisir_salle((7, 10), [[(9, 11)], [(12, 15)]]) == 1
assert choisir_salle((7, 10), [[(8, 10)], [(9, 12)]]) == -1

def choisir_salle(c, salles): for s in range(len(salles)): if not intersecte_list(c, salles[s]): return s return -1 assert choisir_salle((7, 10), [[(9, 11)], [(12, 15)]]) == 1 assert choisir_salle((7, 10), [[(8, 10)], [(9, 12)]]) == -1

Exercice

Écrire une fonction allocation_salles(cours) qui renvoie une liste des salles utilisées par les cours de la liste cours en appliquant l'algorithme glouton.
On pourra compléter le code suivant :

In [11]:

def allocation_salles(cours):
    cours.sort(key=lambda c: c[0]) # trie les cours par ordre de début croissant
    salles = []
    for c in cours: # parcours de la liste cours
        for s in range(len(salles)): # teste si on peut mettre le cours c en salle s
            if ... # si on peut mettre le cours c en salle s
                salles[s].append(c) # on ajoute le cours c à la liste des cours de la salle s
                break # on sort de la boucle for
    
    return salles

def allocation_salles(cours): cours.sort(key=lambda c: c[0]) # trie les cours par ordre de début croissant salles = [] for c in cours: # parcours de la liste cours for s in range(len(salles)): # teste si on peut mettre le cours c en salle s if ... # si on peut mettre le cours c en salle s salles[s].append(c) # on ajoute le cours c à la liste des cours de la salle s break # on sort de la boucle for return salles

  File "<ipython-input-11-e933b66f0ca1>", line 6
    if ... # si on peut mettre le cours c en salle s
           ^
SyntaxError: invalid syntax

Solution

In [12]:

def allocation_salles(cours):
    cours.sort(key=lambda c: c[0]) # trie les cours par ordre de début croissant
    salles = []
    for c in cours: # parcours de la liste cours
        s = choisir_salle(c, salles)
        if s == -1:
            salles.append([c])
        else:
            salles[s].append(c)
    return salles

allocation_salles([(8, 11), (9, 10), (12, 14), (11, 15)])

def allocation_salles(cours): cours.sort(key=lambda c: c[0]) # trie les cours par ordre de début croissant salles = [] for c in cours: # parcours de la liste cours s = choisir_salle(c, salles) if s == -1: salles.append([c]) else: salles[s].append(c) return salles allocation_salles([(8, 11), (9, 10), (12, 14), (11, 15)])

Out[12]:

[[(8, 11), (12, 14)], [(9, 10), (11, 15)]]

Sélection d'activités (Interval scheduling)¶

Dans ce problème, on considère un ensemble d'intervalles (des activités) et on veut en sélectionner le plus possible sans avoir aucune intersection entre les intervalles.
Par exemple, si on utilise les mêmes intervalles que pour l'exercice précédent, on peut choisir au plus $4$ intervalles de temps qui ne se chevauchent pas ($7, 5, 1, 3$ par exemple) :

On admet que l'algorithme glouton suivant est optimal :

1. Trier les intervalles par ordre de fin croissante (sur l'exemple ci-dessus, on considère les intervalles dans l'ordre $7, 0, 5, 2, 4, 1, 9, 6, 3, 8$)
2. On considère chaque itervalle dans cet ordre et on le sélectionne s'il n'intersecte pas les autres intervalles déjà choisis.

Remarque : À nouveau, on peut montrer que cet algorithme glouton est optimal.

Exercice

Écrire cet algorithme glouton en Python.