Introduction aux algorithmes gloutons

La résolution d'un problème algorithmique peut parfois se faire à l'aide de techniques générales, ou "paradigmes", qui présentent l'avantage d'être applicables à un grand nombre de situations. Parmi ces méthodes, on peut citer le célèbre principe "diviser pour régner" ou encore la programmation dynamique. Les algorithmes gloutons, souvent utilisés pour résoudre des problèmes d'optimisation, constituent l'une de ces approches générales.

Nous allons d'abord fournir une définition intuitive de cette méthode, accompagnée de deux exemples.

Le principe glouton

Définition

Lors de la résolution d'un problème d'optimisation, la construction d'une solution se fait souvent de manière séquentielle, l'algorithme réalisant à chaque étape un certain nombre de choix. Le principe glouton repose sur l'idée de faire, à chaque étape, le choix qui semble le meilleur à ce moment précis (choix local), sans se soucier des conséquences futures ni revenir sur les choix précédents.

Un algorithme glouton est donc caractérisé par son approche directe et irréversible. En se dirigeant rapidement vers une solution, il peut ne pas garantir d'obtenir une solution optimale. Cependant, il fournit une réponse en un temps réduit, ce qui peut être acceptable, notamment pour des problèmes NP-difficiles où une solution optimale est hors de portée. Dans de tels cas, les algorithmes gloutons sont souvent utilisés comme algorithmes d'approximation.

Pour que cette méthode soit efficace, il est crucial que chaque choix local aboutisse à un problème similaire, mais plus petit. Cette approche partage ainsi des similitudes avec la programmation dynamique. Toutefois, la différence majeure réside dans l'ordre des opérations :

• Avec la méthode gloutonne, on effectue d'abord un choix local, puis on résout un problème plus restreint (progression descendante).

• En programmation dynamique, on commence par résoudre des sous-problèmes élémentaires et on combine ensuite leurs résultats pour résoudre le problème global (progression ascendante).

Exercice 1 : Comment rendre la monnaie

Nous considérons des pièces de monnaie de 1, 2 et 5 centimes. Notons \( N(x) \) le nombre minimum de pièces nécessaires pour obtenir \( x \) centimes.

Question 1.1

Quelle est la valeur de \( N(0) \), \( N(1) \), \( N(2) \), \( N(3) \), \( N(4) \), \( N(5) \) ?

Question 1.2

Donner un algorithme qui calcule \( N(x) \) et déterminer sa complexité en termes d'opérations.

Question 1.3

Appliquer cet algorithme pour calculer \( N(14) \) en considérant maintenant que l'on dispose des pièces de monnaie de 1, 7 et 10 centimes. Que constatez-vous ?

Question 1.4

Adapter cet algotithme avec le système de monnaie en Euro :

Python

# valeurs des pièces
systeme_monnaie = [1, 2, 5, 10, 20, 50, 100, 200]

# liste des pièces à rendre
lst_pieces = []

# somme à rendre
somme_a_rendre = 87

# indice pour parcourir les pièces
i = len(systeme_monnaie) - 1

# boucle de construction de la liste des pièces
while somme_a_rendre > 0:
    valeur = systeme_monnaie[i]
    if somme_a_rendre < valeur:
        i -= 1
    else:
        lst_pieces.append(valeur)
        somme_a_rendre -= valeur

print("Pièces à rendre :", lst_pieces)

Exercice 2 : Les conférenciers

Planification des conférenciers

Des conférenciers sont invités à présenter leurs exposés dans une salle. Cependant, leurs disponibilités ne leur permettent d’intervenir qu’à des horaires bien définis. Le problème consiste à construire un planning d’occupation de la salle incluant le plus grand nombre possible de conférenciers.

Désignons par \( n \), entier naturel non nul, le nombre de conférenciers. Chacun d’eux, identifié par une lettre \( C_i \), où \( i \) est un entier compris entre 0 et \( n - 1 \), est associé à un intervalle temporel \([d_i, f_i[\), où \( d_i \) et \( f_i \) désignent respectivement l’heure de début et l’heure de fin de l’intervention.

Afin de dégager une stratégie de résolution du problème, commençons par analyser cette situation :

Nous allons utiliser une liste des conférences :

tab_intervalles = [[0,7,'C1'],[2,5,'C2'],[6,8,'C3'],[1,2,'C4'],[5,6,'C5'], [0,2,'C6'],[4,7,'C7'],[0,1,'C8'],[3,6,'C9'],[1,3,'C10'], [4,5,'C11'],[6,8,'C12'],[0,2,'C13'],[5,7,'C14'],[1,4,'C15']]

Question 2.1

Ecrire une version adaptée du tri à bulles pour classer ces intervalles heure de fin croissante.

Solution

Python

tab_intervalles = [[0,7,'C1'],[2,5,'C2'],[6,8,'C3'],[1,2,'C4'],[5,6,'C5'], [0,2,'C6'],[4,7,'C7'],[0,1,'C8'],[3,6,'C9'],[1,3,'C10'], [4,5,'C11'],[6,8,'C12'],[0,2,'C13'],[5,7,'C14'],[1,4,'C15']]

def tri(tab_intervalles):
    n =len(tab_intervalles)
    trie = False

    # Le tri à bulles parcoure la liste jusqu'à ce que tous les éléments soient dans le bon ordre
    while trie == False:

        trie = True # au début d'un parcours, on suppose les éléments triés
        for i in range(n - 1): # parcours jusqu'à l'avant dernier
            hfin1 = tab_intervalles[i][1]       # l'heure de fin est le 2eme élément de chaque liste
            hfin2 = tab_intervalles[i + 1][1]

            if hfin1 > hfin2:

                # permutation des 2 éléments
                tab_intervalles[i], tab_intervalles[i + 1] = tab_intervalles[i + 1], tab_intervalles[i]

                trie = False # nous avons rencontrés des éléments non ordonnés

    return tab_intervalles

Question 2.2

Avec

tab_classe = [[0,1,'C8'],[1,2,'C4'],[0,2,'C6'],[0,2,'C13'],[1,3,'C10'], [1,4,'C15'],[2,5,'C2'],[4,5,'C11'],[5,6,'C5'],[3,6,'C9'], [0,7,'C1'],[4,7,'C7'],[5,7,'C14'],[6,8,'C3'],[6,8,'C12']]

Compléter le code suivant pour obtenir le planning optimal.

Python

def planning(tab_classe):

    # tableau du planning
    tab_planning = [tab_classe[0]] # ajout du premier créneau


    nb_intervalles = len(tab_classe)

    j = 0 # j contient le dernier intervalle ajouté à tab_planning

    for i in range(1, nb_intervalles):
        if .... >= tab_classe[j][1]: # Comparaison de l'heure de début du créneau i avec l'heure de fin du créneau j
            ...append(tab_classe[i])
            j = ...

    return tab_planning

Solution

Python

tab_intervalles = [[0,7,'C1'],[2,5,'C2'],[6,8,'C3'],[1,2,'C4'],[5,6,'C5'], [0,2,'C6'],[4,7,'C7'],[0,1,'C8'],[3,6,'C9'],[1,3,'C10'], [4,5,'C11'],[6,8,'C12'],[0,2,'C13'],[5,7,'C14'],[1,4,'C15']]

def planning(tab_classe):

    # tableau du planning
    tab_planning = [tab_classe[0]] # ajout du premier créneau


    nb_intervalles = len(tab_classe)

    j = 0 # j contient le dernier intervalle ajouté à tab_planning

    for i in range(1, nb_intervalles):
        if tab_classe[i][0] >= tab_classe[j][1]: # Comparaison de l'heure de début du créneau i avec l'heure de fin du créneau j
            tab_planning.append(tab_classe[i])
            j = i

    return tab_planning