Algorithmes gloutons

Optimisation

Un problème d’optimisation est un problème algorithmique dans lequel l’objectif est de trouver la « meilleure » solution (selon un critère donné) parmi un ensemble de solutions également valides mais potentiellement moins  bonnes.

Le contexte d’un problème d’optimisation est donc :

• un très grand nombre de solutions (dans le cas contraire, il n’y aurait pas de difficulté à trouver la meilleure),
• une fonction permettant d’évaluer la qualité de chaque solution,
• l’existence d’une solution optimale, ou suffisamment bonne.

Un voyageur souhaite visiter plusieurs villes de France, dans n’importe quel ordre, mais en minimisant la distance parcourue.

De nombreuses techniques informatiques sont susceptibles d’apporter une solution exacte ou approchée à ces problèmes.

Certaines de ces techniques, comme l’énumération exhaustive de toutes les solutions, ont un coût machine qui les rend souvent peu pertinentes au regard de contraintes extérieures imposées (temps de réponse de la solution imposé, moyens machines limités). Quand il existe un très grand nombre de solutions il est tout simplement impossible de les évaluer toutes.

Par exemple : si le voyageur décidait de visiter 20 villes, il y aurait 1,2.10¹⁸ trajets possibles, ce qui représenterait plusieurs jours de calcul !!!

Les techniques de programmation dynamique ou d’optimisation linéaire peuvent apporter une solution mais sont parfois complexes à mettre en œuvre.

Un glouton

Les algorithmes gloutons (greedy algorithms) constituent une alternative beaucoup plus simple à programmer, mais dont le résultat n’est pas toujours optimal (sauf dans certaines situations dites canoniques).

L’approche gloutonne consiste à construire une solution complète par une succession de choix locaux donnant systématiquement la meilleure solution partielle.

Pour résumer, on peut employer un algorithme glouton lorsque :

• une solution complète peut être construite en passant par une succession de solutions partielles,
• chaque solution partielle est établie en faisant un choix local à partir de la solution partielle précédente,
• on dispose d’une fonction permettant d’évaluer la qualité de chaque solution partielle.

Les choix ne sont jamais remis en cause : une fois faits, on ne revient pas dessus. Cela constitue une différence essentielle avec la programmation dynamique qui au lieu de se focaliser sur un seul sous-problème, explore les solutions de tous les sous-problèmes pour les combiner finalement de manière optimale.

Rendu de monnaie

Un achat en espèces se traduit par un échange de pièces et de billets (dans la suite de l’article, les « pièces » désignent indifféremment les véritables pièces et les billets).

Dans le système monétaire français, les « pièces » prennent les valeurs 1€, 2€, 5€, 10€, 20€, 50€ et 100€.

Si la question est de rendre la monnaie avec un minimum de pièces, il s’agit d’un problème d’optimisation !

Comment parvenir à un tel résultat à l’aide d’un algorithme, et sans faire une énumération exhaustive ?

En pratique, sans s’en rendre compte généralement, tout individu met en œuvre un algorithme glouton.

Par exemple, pour rendre 49€, il choisit d’abord la plus grande valeur de monnaie, parmi 1, 2, 5, 10, 20, 50 et 100, contenue dans 49€. En l’occurrence, 2 fois une pièce de 20€. La somme de 9€ restant à rendre, il choisit 1 pièce de 5€, puis 2 pièces de 2€.
Cette stratégie gagnante pour la somme de 49€ l’est-elle pour n’importe quelle somme à rendre ?

On peut montrer que pour le système monétaire français, la stratégie gloutonne donne toujours une solution optimale. Pour cette raison, un tel système de monnaie est qualifié de canonique.

D’autres systèmes ne sont pas canoniques : l’algorithme glouton ne répond pas toujours de manière optimale.

Par exemple, avec le système {1,3,6,12,24,30}, l’algorithme glouton répond en proposant le rendu 49=30+12+6+1, soit 4 pièces alors que la solution optimale est 49=2×24+1, soit 3 pièces.

La réponse à cette difficulté passe par la programmation dynamique.

Un algorithme glouton

Considérons un ensemble de \(n\) pièces de monnaie de valeurs :

\(v_1<v_2<⋅⋅⋅<v_n\), avec \(v_1=1\)

On suppose que ce système est canonique. On peut noter le système de pièces : \(S_n=\{v_1, . . . , v_{n}\}\)

Désignons par \(s\) une somme à rendre avec le minimum de pièces de \(S_n\). L’algorithme glouton sélectionne la plus grande valeur \(v_n\) et la compare à \(s\).

• Si \(s<v_n\), la pièce de valeur \(v_n\) ne peut pas être utilisée. On reprend l’algorithme avec un système de pièces « réduit » \(S_{n−1}=\{v_1, . . . , v_{n−1}\}\).
• Si \(s\geq v_b\), la pièce \(v_n\) peut être utilisée une première fois. Ce qui fait une première pièce à comptabiliser, de valeur \(v_n\), la somme rendre devient alors \(s−v_n\). L’algorithme continue avec le même système de pièces \(S_n\) et cette nouvelle somme à rendre \(s−v_n\).

L’algorithme est ainsi répété jusqu’à obtenir une somme à rendre nulle.

Remarque : Il s’agit effectivement d’un algorithme glouton, la plus grande valeur de pièce étant systématiquement choisie si sa valeur est inférieure à la somme à rendre. Ce choix ne garantit en rien l’optimalité globale de la solution. Le choix fait est considéré comme pertinent et permet d’avancer plus avant dans le calcul. Toutefois si le système monétaire est canonique, la solution est optimale.

Codage en Python

Définissons le système de pièces à l’aide d’un tableau de valeurs des pièces classées par valeurs décroissantes :

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

Pour stocker les pièces à rendre, une liste Python, initialement vide, peut être utilisée :

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

La première pièce à rendre est potentiellement la première pièce du tableau systeme_monnaie (celle de plus forte valeur). Une variable « indice »  i, de type entier, est donc initialisée à 0 :

# indice de la première pièce comparer à la somme à rendre
i = 0

La somme à rendre est initialement stockée dans la variable somme_a_rendre.

Si la pièce d’indice i est utilisable, somme_a_rendre est diminuée de sa valeur.

Chaque fois qu’une pièce de systeme_monnaie n’est plus utilisable, la valeur de i sera augmentée de 1. pour passer à la pièce de valeur directement inférieure.

Le programme s’arrête quand somme_a_rendre atteint la valeur 0. Ce qui mène à l’écriture d’une boucle conditionnelle pour remplir la liste des pièces choisies.

systeme_monnaie = [100, 50, 20, 10, 5, 2, 1]
somme_a_rendre = 49

i = 0
lst_pieces = []
while somme_a_rendre > 0:
    if somme_a_rendre >= systeme_monnaie[i]:
        somme_a_rendre -= systeme_monnaie[i]
        lst_pieces.append(systeme_monnaie[i])
    else:
        i += 1
  
print(lst_pieces)

Un problème d’organisation

Des conférenciers sont invités à présenter leurs exposés dans une salle. Mais leurs disponibilités ne leur permettent d’intervenir qu’à des horaires bien définis. Le problème est de construire un planning d’occupation de la salle avec le plus grand nombre 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 tactique de résolution du problème, commençons par analyser plusieurs situations.

Premières analyses

Situation 1

Quatre conférenciers peuvent intervenir aux intervalles temporels suivants :

\(\begin{array}{c}C_1∶[3,4[ & C_2∶[0,1[ & C_3∶[2,3[ & C_4∶[1,2[\end{array}\)

Une telle situation est simple puisque tous les conférenciers peuvent intervenir sur des créneaux horaires disjoints. Le planning est donc défini par la suite \([C_2, C_4, C_3, C_1]\) de conférenciers. L’algorithme menant à ce résultat choisit les conférenciers par ordre croissant des heures de début ou de fin des conférence après s’être assuré que les intervalles sont disjoints.

Situation 2

On considère à nouveau quatre conférenciers dont les créneaux horaires ne sont plus toujours disjoints.

\(\begin{array}{c}C_1∶[2,4[ & C_2∶[0,1[ & C_3∶[1,3[ & C_4∶[0,2[\end{array}\)

Ces intervalles ne sont pas compatibles : des choix doivent être faits et certains conférenciers peuvent ne pas être retenus pour construire un planning. Plusieurs solutions peuvent être construites.

\([C_2, C_1]\) ou \([C_2, C_3]\) ou \([C_4, C_1]\) ou \([C_3]\)

Seules les trois premières solutions sont retenues puisque la dernière ne maximise pas le nombre de conférenciers choisis.

Mais laquelle de ces solutions retenir ?

Une idée serait de nouveau de classer par ordre croissant les heures de début des intervalles compatibles. En procédant de la sorte, \(C_1\) et \(C_3\) sont compatibles avec \(d_2<d_1\) ; ce qui mène au planning \([C_2, C_1]\). De même, \(C_2\) et \(C_3\) sont compatibles avec \(d_2<d_3\)  ; ce qui mène à \([C_2, C_3]\). Enfin, \(C_4\) et \(C_1\) sont également compatibles, avec \(d_4<d_1\); ce qui mène à \([C_4, C_1]\).

Une autre idée serait de construire les plannings en classant par ordre croissant les heures de fin des intervalles compatibles. En procédant de la sorte, on retrouve les trois propositions de plannings précédentes.

Il semble donc que ces deux idées mènent à des résultats identiques. En outre, elles n’ont pas permis d’éliminer des solutions afin de n’en fournir qu’une seule. C’est à ce niveau que la stratégie gloutonne intervient. Celle-ci va faire un premier choix de conférencier en suivant un critère à préciser. Ce choix ne sera jamais remis en question et la même stratégie sera appliquée pour trouver les conférenciers suivants.

Après avoir classé les intervalles par valeurs croissantes des heures de début, sélectionner l’intervalle de la première plus petite valeur, puis celui de la deuxième plus petite valeur compatible avec la précédente, et ainsi de suite. On observe que :

\(d_2=d_4<d_3<d_1\)

et que :

• \(C_2\) et \(C_4\) ne sont pas compatibles ;
• \(C_3\) et \(C_4\) ne sont pas compatibles ;
• \(C_1\) et \(C_3\) ne sont pas compatibles.

Deux solutions \([C_2, C_3]\) et \([C_4, C_1]\) restent, en raison de l’égalité \(d_2=d_4\) qui ne permet pas de choisir le premier conférencier.

On peut aussi classer les intervalles par valeurs croissantes des heures de fin, puis sélectionner l’intervalle de la première plus petite valeur, puis celui de la deuxième plus petite valeur compatible avec la précédente, et ainsi de suite. On observe à présent que :

\(f_2<f_4<f_3<f_1\) avec les mêmes incompatibilités que précédemment.

Une seule solution est alors possible : \([C_2, C_3]\).

Cette solution était également proposée par la stratégie précédente. Il est alors légitime de se demander si ce dernier résultat relève d’une stratégie générale pertinente ou d’une situation trop particulière. La situation suivante apporte un premier élément de réponse.

Situation 3

Considérons à présent trois conférenciers et appliquons les deux stratégies précédentes.

\(\begin{array}{c}C_1∶[0,3[ & C_2∶[1,2[ & C_3∶[2,3[\end{array}\)

• En classant les heures de début, on a \(d_1<d_2<d_3\). Seuls \(C_2\) et \(C_3\) sont compatibles. Mais puisque \(d_1\) est la plus petite des heures, le planning proposé en suivant cette stratégie se réduit \([C_1]\) alors que \([C_2, C_3]\) est une meilleure solution puisqu’elle maximise le nombre de conférenciers.
• En classant les heures de fin, on a \(f_2<f_1=f_3\). Cette fois-ci, le planning proposé en suivant la seconde stratégie fournit le planning \([C_2, C_3]\)

Un algorithme glouton

Une solution semble émerger des observations précédentes. On peut donc proposer la stratégie suivante :

• Classer les intervalles par heures de fin croissantes,
• Choisir le conférencier associé au premier intervalle,
• Choisir parmi les intervalles suivants celui du conférencier dont l’intervalle est compatible avec celui du premier conférencier,
• Recommencer ainsi avec les intervalles classés suivants jusqu’à ce qu’il n’y en ait plus à traiter.

Illustrons la mise en œuvre de cet algorithme sur la situation suivante :

Commençons par classer les conférenciers par heures de fin croissantes en notant≼la relation d’ordre associée.

\(C_8\leq C_4\leq C_6\leq C_{13}\leq C_{10}\leq C_{15}\leq C_2\leq C_{11}\leq C_5\leq C_9\leq C_1\leq C_7\leq C_{14}\leq C_3\leq C_{12}\)

Puis construisons petit à petit le planning :

• Le premier conférencier est \(C_8\rightarrow [C_8]\).
• Le conférencier suivant dont l’intervalle est compatible avec celui de \(C_8\) est \(C_4\rightarrow[C_8, C_4]\).
• Le conférencier suivant compatible avec \(C_4\) est \(C_2\rightarrow[C_8, C_4, C_2]\).
• Le conférencier suivant compatible avec \(C_2\) est \(C_5\rightarrow[C_8, C_4, C_2, C_5]\).
• Le conférencier suivant compatible avec \(C_5\) est \(C_3\rightarrow[C_8, C_4, C_2, C_5, C_3]\).

Ce qui mène au planning final suivant.

\([C_8, C_4, C_2, C_5, C_3]\)

Remarques :

• Un tel algorithme est effectivement de type glouton. Chaque choix fait sélectionne l’une des meilleures possibilités et ne remet jamais en cause les choix précédents.
• Pour conclure cette proposition d’algorithme, il conviendrait de montrer que la solution obtenue est optimale, c’est-à-dire de cardinal maximum.

Codage en Python

Structure des données

Avant de proposer un code Python qui renvoie un planning sous la forme d’un tableau, il convient de s’interroger sur la manière de stocker les intervalles horaires de chaque conférencier.

Étant donnés \(n\) conférenciers, une première idée consiste à placer à l’indice \(i\in\{0, . . . , n−1\}\) d’un tableau tab_intervalles l’intervalle \([d_{i+1}, f_{i+1}]\) du conférencier \(i+1\) sous la forme d’un tableau.

Reprenant l’exemple de la figure, cela donnerait le tableau suivant.

tab_intervalles = [[0,7],[2,5],[6,8],
                   [1,2],[5,6],[0,2],
                   [4,7],[0,1],[3,6],
                   [1,3],[4,5],[6,8],
                   [0,2],[5,7],[1,4]]

debut = 8      # heure de début des conférences
fin = 17       # heure de fin des conférences
duree_max = 3  # durée maximale des conférences

from random import randint

def activites(nb_intervalles):
   debut = 8
   fin = 17
   duree_max = 3
   tab_intervalles = []
   for _ in range(nb_intervalles):
      duree = randint(1, duree_max)
      deb = randint(debut, fin-duree)
      tab_intervalles.append([deb, deb+duree])
   return tab_intervalles

Si une telle solution semble pertinente, elle présente un inconvénient lié à la phase de tri qui, en réorganisant les créneaux horaires, place à un indice i du tableau trié un conférencier qui n’est plus \(C_i\). Sur le tableau ci-dessus, le tri mène au tableau suivant.

[[0,1],[1,2],[0,2],[0,2],[1,3],[1,4],[2,5],[4,5],[5,6],[3,6],[0,7],[4,7],[5,7],[6,8],[6,8]]

Pour éviter cette difficulté, plusieurs solutions sont envisageables. Nous proposons de d’ajouter un champ aux tableaux des créneaux horaires sous la forme d’une chaîne de caractères qui identifie le conférencier :

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']]

Le tableau trié est alors le suivant :

[[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']]

from random import randint

def activites(nb_intervalles):    
    debut = 8    
    fin = 17    
    duree_max = 3    
    tab_intervalles = []    
    for i in range(nb_intervalles):       
        duree = randint(1, duree_max)       
        deb = randint(debut, fin-duree)       
        tab_intervalles.append([deb, deb+duree, 'C'+str(i+1)])    
    return tab_intervalles

Tri des données

La première étape de l’algorithme consiste à trier les intervalles par valeur croissante des heures de fin.

tab_intervalles = sorted(tab_intervalles, key = lambda a:a[1])

def org_intervalles(tab_intervalles):
   nb_intervalles = len(tab_intervalles)
   
   # tri des intervalles par valeurs croissantes des heures de fin
   tab_intervalles = sorted(tab_intervalles, key = lambda a:a[1])
   
   # tableau du planning
   tab_planning = [tab_intervalles[0]]
   j = 0
   for i in range(1, nb_intervalles):
      if tab_intervalles[i][0] >= tab_intervalles[j][1]:
         tab_planning.append(tab_intervalles[i])
         j = i
   return tab_planning

def affiche_intervalles(tab_intervalles):
    t = ""
    for d, f, l in tab_intervalles:
        t += l + "\t:" + " "*d + "#"*(f-d) + "\n"
    print(t)

sources : https://cache.media.eduscol.education.fr/file/NSI/76/4/RA_Lycee_G_NSI_algo-gloutons_1170764.pdf