Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 06 - Algorithmes gloutons

Dans ce dernier chapitre, nous allons de nouveau nous intéresser à la résolution de problèmes d’optimisation, mais via cette fois une approche dite gloutonne. Cette méthode sera plus simple à implémenter que la programmation dynamique, mais en contrepartie elle ne produira pas toujours une solution optimale.

Nous allons commencer par en présenter le principe général, puis nous étudierons de façon complète un problème classique, celui de la planification d'activités.

Principe général

Après avoir exposé le fonctionnement global des algorithmes gloutons, nous étudierons ce qui les différentie de la programmation dynamique en revenant entre autres sur le problème du rendu de monnaie.

La méthode gloutonne

Rappelons (cf. cinquième chapitre de ce cours) que dans un problème d'optimisation chaque solution possède une valeur, et que l'on cherche à déterminer parmi toutes les solutions celle dont la valeur est optimale.

La technique la plus basique pour résoudre ce type de problème consiste à énumérer de façon exhaustive toutes les solutions possibles, puis à choisir la meilleure. Cette approche par force brute s'implémente la plupart du temps avec des algorithmes récursifs naïfs de complexité exponentielle.

Nous avons vu lors du précédent chapitre que l'on pouvait procéder de façon plus efficace en utilisant la programmation dynamique. Celle-ci peut être codée itérativement ou récursivement avec une complexité pseudo-polynomiale.

Une autre alternative sera l'utilisation d'une méthode dite gloutonne. Pour construire une solution optimale avec cette technique, on va effectuer une succession de choix, chacun d'eux étant celui semblant être le meilleur sur le moment. Après chaque prise de décision, on résout alors le sous-problème qui en découle, en profitant du fait qu’une solution optimale contient la solution optimale des sous-problèmes. Particularité importante, on ne revient jamais sur un choix déjà effectué.

Cette approche est naturellement récursive dans sa conception, il y a en effet toujours l'idée de se ramener à des sous-problèmes de plus petites tailles. Cependant, on l'implémentera en général itérativement pour ne pas risquer de débordements de la pile de récursion.

Une technique déjà utilisée sans le dire

Cette technique ne doit pas être étrangère au lecteur ayant suivi le cours de théorie des graphes 2GRA. Nous l'avons déjà en effet utilisée plusieurs fois mais sans la mettre en avant.

Par exemple dans l'algorithme de Prim, on rajoute à chaque étape l'arrête de plus petite valuation entre un sommet de l'arbre en construction et un sommet qui n'y figure pas encore. Il s'agit donc bien d'un choix glouton au sens que l'on vient de définir.

Dans celui de Kruskal, on choisit successivement les arrêtes de plus petites valuations à condition que celles-ci ne créent pas de cycle simple. Là encore l'approche est gloutonne.

On peut également citer l'algorithme de Welsh-Powell où l'on considère les sommets par ordre décroissant de leurs degrés.

Et puis bien sûr le célèbre algorithme de Dijkstra, où à chaque itération l'on sélectionne le sommet non encore traité dont la distance à l'origine est minimale. Et donc le meilleur sur le moment.

Ces algorithmes sont donc gloutons, ils sont bien constitués d'une succession de choix sur lesquels on ne revient jamais par la suite.

[Note]

A noter que l’algorithme de Bellman-Ford n’est pas glouton, on revient plusieurs fois sur chacun des sommets.

[Note]

On voit bien sur ces premiers exemples qu’une des contraintes implicites des méthode gloutonnes sera le tri des élements selon un certain critère.

Le choix du critère sera fondamental dans la mesure où il pourra conduire ou non à une solution optimale. Nous reviendrons vite sur cette question.

Comparaison avec la programmation dynamique

Nous allons ici nous focaliser sur les différences entre programmation dynamique et méthode gloutonne, en les explicitant d'abord sur le problème du rendu de monnaie, puis en les présentant de façon générale.

Retour sur le problème du rendu de monnaie

Reprenons les hypothèses telles que nous les avons exposées dans le cinquième chapitre de ce cours :

  • Le système de pièces de monnaie peut être modélisé par un n-uplet d'entiers naturels S = ( c 1 , c 2 , . . . , c n ) , où c i représente la valeur de la pièce i.

  • On suppose que c 1 = 1 et que c 1 < c 2 < . . . < c n .

  • Une somme à rendre est un entier naturel X.

  • Une répartition de pièces est un n-uplet d'entiers naturels ( x 1 , x 2 , . . . , x n ) , où x 1 représente le nombre de pièces c 1 , x 2 le nombre de pièces c 2 , etc. Le nombre total de pièces d'une telle répartition est donc i = 1 n x i .

La question est alors la suivante : pour tout entier naturel X, on cherche un n-uplet d'entiers naturels ( x 1 , x 2 , . . . , x n ) qui minimise i = 1 n x i sous la contrainte i = 1 n x i c i =X.

Nous avions alors établi cette formule de récurrence

C [ X ] = { 0 si X = 0 1 + m i n 1 i n c i X C [ X c i ] si X > 0

Une exploitation à la lettre de cette formule conduit tout d'abord à un algorithme récursif naïf, de type diviser pour régner, où l'on étudie toutes les solutions avant de prendre la meilleure :

def recursiveChange(S,X):
    if X==0:
        return 0
    else:
        mini = X+1
        for i in range(len(S)):
            if S[i]<=X:
                nb = 1 + recursiveChange(S,X-S[i])
                if nb<mini:
                    mini = nb
        return mini

On peut montrer que la complexité de cet algorithme est en O ( n X ) , ce qui est cohérent avec l'allure de l'arbre des appels récursifs comme on peut le constater sur l'exemple suivant.

Example 1.1. Arbre des appels récursifs pour l'algorithme diviser pour régner

Considérons le système européen S= ( 1 , 2 , 5 , 10 , 20 , 50 , 100 , 200 , 500 ) et une somme X=6 :


Il est alors facile de modifier l'algorithme précédent en adoptant une technique de programmation dynamique, i.e. en mémorisant les résultats des sous-problèmes au lieu de les recalculer systématiquement. Avec une approche Top Down, cela donne :

def DPTDChangeRec(S,X,track):
    if X==0:
        return 0
    elif track[X]>0:
        return track[X]
    else:
        mini = X+1
        for i in range(len(S)):
            if S[i]<=X:
                nb=1+DPTDChangeRec(S,X-S[i],track)
                if nb<mini:
                    mini = nb
                    track[X] = mini
        return mini

Il faut bien sûr également une fonction pour déclarer notre mémoire cache, c'est-à-dire la liste track, et réaliser le premier appel de la fonction récursive :

def DPTDChange(S,X):
    track = [0]*(X+1)
    return DPTDChangeRec(S,X,track)

Nous avons ainsi amélioré la complexité puisqu'elle est maintenant en Θ ( n X ) , ce que là aussi l'arbre des appels récursifs confirme.

Example 1.2. Arbre des appels récursifs pour l'algorithme Top Down

Reprenons le système européen S= ( 1 , 2 , 5 , 10 , 20 , 50 , 100 , 200 , 500 ) et la somme X=6 :


Voyons maintenant comment résoudre ce problème de façon gloutonne. Par définition de cette méthode, à chaque étape l'on va effectuer le meilleur choix à cet instant précis. On commence ainsi par rendre la plus grande pièce possible, i.e. la plus grande pièce inférieure à la somme à rendre. En effet, il s'agit clairement de la décision la plus profitable sur le moment.

On déduit alors cette pièce de la somme à rendre, ce qui nous conduit à un sous-problème de plus petite taille. On recommence ainsi jusqu'à obtenir une somme nulle.

Voici l'implémentation de cette approche :

def greedyRecChange(S,X):
    if X==0:
        return 0
    else:
        i = 0
        while (i<len(S)) and (S[i]<=X):
            i+=1
        return 1 + greedyRecChange(S,X-S[i-1])
[Note]

Dans la mesure où les pièces du système de monnaie sont par hypothèse classées par ordre croissant de valeur, pour déterminer la plus grande pièce inférieure à la somme à rendre, il suffit de parcourir la liste et de s'arrêter dès que l'on a une pièce plus grande que cette somme.

Cet algorithme est clairement plus simple que les précédents, puisqu'à chaque étape l'on n'étudie pas tous les cas possibles, on se contente juste de choisir la pièce la plus grande que l'on peut encore rendre.

Encore une fois, construire l'arbre des appels récursifs va confirmer cet état de fait.

Example 1.3. Arbre des appels récursifs pour l'algorithme glouton

Reprenons le système européen S= ( 1 , 2 , 5 , 10 , 20 , 50 , 100 , 200 , 500 ) et la somme X=6 :


Cette simplification n'est malheureusement pas sans effets néfastes, puisqu'elle s'accompagne d'une perte de l'optimalité dans certains cas. Nous allons le vérifier en exhibant un contre-exemple.

Example 1.4. Non optimalité de l'algorithme glouton

Pour certains systèmes de monnaie, l'approche gloutonne peut retourner un résultat optimal :

S=(1,2,5)
print(DPTDChange(S,6))
print(greedyRecChange(S,6))
2
2

Pour d'autres systèmes cela ne sera par contre pas le cas :

S=(1,3,4)
print(DPTDChange(S,6))
print(greedyRecChange(S,6))
2
3

Le code précédent est récursif, il n'est cependant nullement difficile de le convertir en code itératif :

def greedyIterChange(S,X):
    nb = 0
    while X>0:
        nb+=1
        i = 0
        while (i<len(S)) and (S[i]<=X):
            i+=1
        X-=S[i-1]
    return nb

Considérations générales

Les techniques de programmation dynamique et de choix glouton reposent donc toutes deux sur l’utilisation de sous-problèmes induits par le problème initial.

Il y a cependant une grosse différence entre elles. En programmation dynamique on calcule les solutions de tous les sous-problèmes et on les combine de façon optimale. Tandis qu'avec une méthode gloutonne on choisit à tout moment ce qui semble être la meilleure solution et on résout le sous-problème qui en découle.

La comparaison des arbres des appels récursifs montre bien cette différence. En programmation dynamique on explore toutes les branches une et une seule fois, alors que dans une méthode gloutonne on explore une seule branche.

[Note]

A noter que dans une recherche exhaustive la situation est encore plus singulière, puisque l'on explore toutes les branches, certaines un grand nombre de fois.

[Note]

Un algorithme glouton peut toujours être converti en un algorithme de programmation dynamique. Même si c'est parfois assez délicat.

L'inverse est faux.

Chacune de ces deux techniques possède ses avantages et inconvénients.

En particulier, un algorithme glouton sera clairement de complexité moindre qu'un algorithme de programmation dynamique. Il sera également plus simple à implémenter.

[Note]

Bien comprendre que complexité algorithmique et complexité d'implémentation sont deux choses complètement différentes et à priori non corrélées.

Même si dans la comparaison méthode gloutonne versus programmation dynamique, dans les deux cas l'avantage tourne en faveur de la gloutonnerie.

Cette simplicité n'est malheureusement pas sans contrepartie. La programmation dynamique fournissait toujours une solution optimale à nos problèmes, ce qui n'est pas le cas de l'approche gloutonne.

Vérification de l’optimalité

La méthode gloutonne ne retourne donc pas toujours un résultat optimal, comme nous avons pu le voir avec le problème du rendu de monnaie.

D'ailleurs, dans le cas où la solution obtenue n’est pas optimale, on parle plutôt d’heuristique gloutonne, et dans le cas où elle l'est d'algorithme glouton.

La non optimalité d'une heuristique gloutonne est relativement simple à prouver, il suffit d'exhiber un contre-exemple, i.e. trouver un cas particulier où la solution gloutonne n’est pas la meilleure.

Par contre, lorsque l'on pressent qu'une méthode gloutonne est optimale, le démontrer est en général très difficile. Il existe cependant une approche générique que l'on pourra essayer d'employer.

On peut commencer par essayer de montrer qu'il existe une solution optimale contenant le premier élément choisi par la méthode gloutonne. Cela se fait souvent en échangeant un élement d’une solution optimale avec ce premier élément.

Une fois cela fait, on montre qu’une solution optimale du sous-problème qui en résulte, combinée avec ce premier choix glouton, est une solution optimale au problème d’origine. Cela se fait souvent en utilisant une preuve par l’absurde.

En réitérant cet argument, on montre enfin qu’il existe une solution optimale contenant la solution gloutonne. Q.E.D.

[Note]

Que le lecteur ne s'inquiète pas, ces éléments généraux de démonstration vont prendre tout leur sens après l'étude de l'exemple proposé dans la seconde partie.

Le problème du choix d’activités

Le problème très concret du choix d'activités va nous permettre de bien cerner tous les aspects de l'approche gloutonne, et en particulier le fait que l'on peut envisager différentes heuristiques dans une situation donnée.

Position du problème

On considère un ensemble d’activités, chacune possédant une date de début et une date de fin. Pour des raisons logistiques, on ne peut pas programmer des activités se déroulant en même temps.

La question est la suivante : quel est le nombre maximal d’activités que l’on va pouvoir planifier ?

Formalisons tout d'abord ce problème avec quelques notations mathématiques :

  • L'ensemble des n activités peut être modélisé par un n-uplet de couples S= ( ( b 1 , e 1 ) , ( b 2 , e 2 ) , . . . , ( b n , e n ) ) , où b i représente la date de début de l'activité i et e i sa date de fin.

  • On suppose que i, 1 i n , b i < e i et que l'activité i se déroule pendant l'intervalle [ b i ; e i [ .

  • Deux activités i et j sont dites compatibles si b i e j ou alors b j e i . On peut dans ce cas les programmer toutes les deux.

Notre question peut alors être reformulée comme suit : on cherche un sous-ensemble d’activités compatibles dont le cardinal est le plus grand possible.

[Note]

La première hypothèse est naturelle, elle signifie juste que la date de début d'une activité doit être antérieure à sa date de fin.

Le fait que l'intervalle de temps pendant lequel se déroule une activité est semi-fermé à gauche et semi-ouvert à droite implique que si la date de début d'une activité est égale à la date de fin d'une autre, alors ces deux activités sont compatibles.

Présentons de suite un petit exemple dans le but de bien fixer les idées.

Example 1.5. Un cas simple d'activités à planifier

Considérons l'ensemble d'activités

S = ( ( 1 , 4 ) , ( 0 , 6 ) , ( 3 , 5 ) , ( 12 , 13 ) , ( 8 , 11 ) , ( 8 , 12 ) , ( 2 , 13 ) , ( 6 , 10 ) , ( 5 , 9 ) , ( 3 , 8 ) , ( 5 , 7 ) , ( 13 , 16 ) , ( 15 , 17 ) , ( 16 , 19 ) )

On va résoudre à la main le problème du choix d'activités pour ces données en commençant par les représenter :

Il est alors relativement facile de voir qu'on le nombre maximal d'activités que l'on peut planifier est 6, et que celles-ci sont :


L'huile de coude se montrant vite insuffisante en face de situations plus délicates que celle de l'exemple précédent, il est donc temps d'aborder la question de façon plus rationnelle.

Des heuristiques gloutonnes

On va dans cette sous-partie imaginer différentes approches gloutonnes pour tenter de résoudre ce problème. On se posera bien sûr la question de leur optimalité.

Comme nous l'avons noté dans la première partie, il nous faudra trier les données, donc ici les activités, selon un critère spécifique. C'est le choix de ce critère qui différentiera une approche d'une autre.

Nous représenterons en Python l'ensemble S des activités par une liste de couples. En effet, nous serons amenés à effectuer des tris et même d'autres opérations sur S, il nous faut donc une structure de données muable.

Nous désignerons par C la solution de notre problème, c'est-à-dire la liste des activités choisies.

Tri par durée

Une première méthode consiste à prendre les activités par ordre croissant de leur durée. On peut en effet raisonnablement penser que planifier d'abord les activités les plus courtes laissera plus de temps pour les autres.

Cela donne cette résolution :

  1. Trier les activités par ordre croissant de leur durée.

  2. Initialiser la liste C des activités choisies avec l’ensemble vide.

  3. Parcourir dans l’ordre la liste S des activités, et rajouter l’activité courante à C si elle n’est pas incompatible avec celles déjà présentes dans C.

Cette approche est bien gloutonne, à chaque étape l'on considère que le meilleur choix à effectuer est de prendre l'activité la plus courte compatible avec toutes celles déjà planifiées.

L'implémentation en Python de cette idée est alors :

def shorterBeforeChoice(S):
    S.sort(key=lambda x:(x[1]-x[0]))
    C = []
    for x in S:
        compatibility = True
        for y in C:
            if not ((y[0]>=x[1]) or (x[0]>=y[1])):
                compatibility = False
        if compatibility:
            C.append(x)
    return C

Le tri des activités selon leur durée a été effectué en utilisant sort, procédure native du langage Python permettant de trier des listes. Pour spécifier le critère de tri, on a passé une fonction lambda au paramètre key. Il s'agit d'une fonction anonyme, i.e. une fonction sans nom, que l'on ne souhaite pas réutiliser et que l'on définit donc à la volée quand le besoin s'en fait sentir. Ici, à une activité x cette fonction associe x [ 1 ] - x [ 0 ] , qui est bien sa durée puisque x [ 1 ] est la date de fin de x et x [ 0 ] sa date de début.

[Note]

On aurait bien sûr pu aussi implémenter nous même un algorithme de tri, et nous y aurions d'ailleurs été obligé dans un langage plus bas niveau. Mais ce n'est pas un problème.

On parcourt ensuite les activités x de cette liste triée. Pour tester si x peut être rajoutée à C, on considère une par une les activités y déjà choisies, c'est-à-dire celles de C, et l'on teste la compatibilité entre x et y en revenant à la définition même de celle-ci (voir sous-partie 2.1).

Example 1.6. Utilisation de la fonction précédente

activities = [(1,4),(0,6),(3,5),(12,13),(8,11),(8,12),(2,13),\
              (6,10),(5,9),(3,8),(5,7),(13,16),(15,17),(16,19)]

print(shorterBeforeChoice(activities))
[(12, 13), (3, 5), (5, 7), (15, 17), (8, 11)]

Cette idée tout à fait sensée n'est malheureusement pas optimale. Pour le démontrer il suffit de proposer un contre-exemple, ce que nous laissons le lecteur faire à titre d'exercice.

Exercice corrigé

1.1.

Trouver un contre-exemple prouvant que le résultat retourné par l’heuristique précédente n’est pas toujours optimal. On pourra répondre par un schéma du même type que celui de la fin de la sous-partie 2.1.

Dans le cas de figure suivant, l’heuristique précédente retournerait les deux activités en rouge, à la place des trois en bleu :

Tri par date de début

Une autre approche est de considérer les activités par ordre croissant de leur date de début. L'idée sous-jacente étant de perdre le moins de temps possible en commençant au plus vite une nouvelle activité.

Voici les étapes de la résolution :

  1. Trier les activités par ordre croissant de leur date de début.

  2. Initialiser la liste C des activités choisies avec l’ensemble vide.

  3. Parcourir dans l’ordre la liste S des activités, et rajouter l’activité courante à C si elle n’est pas incompatible avec celles déjà présentes dans C.

[Note]

Les étapes 2 et 3 sont bien sûr les mêmes que celles de la sous-partie 2.2.1.

Ici, le choix glouton consiste à prendre à chaque étape l'activité commençant le plus tôt, à condition qu'elle soit compatible avec celles déjà planifiées.

En Python, cela donne cette implémentation :

def firstBeginChoice(S):
    S.sort(key = lambda x:x[0])
    C = [S[0]]
    j=0
    for i in range(j+1,len(S)):
        if S[i][0]>=S[j][1]:
            C.append(S[i])
            j=i
    return C

La fonction lambda passée en paramètre de key associe bien à une activité x sa date de début x [ 0 ] , ce que l'on voulait.

Le rajout de l'activité d'indice i se fait en testant juste si sa date de début est supérieure ou égale à la date de fin de la dernière activité ajoutée à C, indexée ici par l'indice j. En effet, puisque l'on a dans un premier temps trié les activités par ordre croissant de leur date de début, en aucun cas l'activité j ne peut commencer avant l'activité i.

Example 1.7. Utilisation de la fonction précédente

activities = [(1,4),(0,6),(3,5),(12,13),(8,11),(8,12),(2,13),\
              (6,10),(5,9),(3,8),(5,7),(13,16),(15,17),(16,19)]

print(firstBeginChoice(activities))
[(0, 6), (6, 10), (12, 13), (13, 16), (16, 19)]

Là non plus il n'y a pas optimalité, et nous allons de nouveau mettre le lecteur à contribution pour le prouver.

Exercice corrigé

1.1.

Trouver un contre-exemple prouvant que le résultat retourné par l’heuristique précédente n’est pas toujours optimal. On pourra répondre par un schéma du même type que celui de la fin de la sous-partie 2.1.

Dans le cas de figure suivant, l’heuristique précédente retournerait l’activité en rouge, à la place des trois en bleu :

Tri par nombre d'incompatibilités

Une troisième possibilité revient à prendre les activités par ordre croissant de leurs incompatibilités. Procéder ainsi permet de privilégier les activités qui "gènent" le moins, et donc avoir moins de contraintes pour planifier les autres.

Là encore on aura trois étapes dans la résolution :

  1. Trier les activités par ordre croissant de leur nombre d’activités incompatibles.

  2. Initialiser la liste C des activités choisies avec l’ensemble vide.

  3. Parcourir dans l’ordre la liste S des activités, et rajouter l’activité courante à C si elle n’est pas incompatible avec celles déjà présentes dans C.

Ici le critère de tri (et donc le choix glouton) est moins simple que dans les deux sous-parties précédentes. Il va déjà nous falloir une procédure afin d'évaluer le nombre d'activités incompatibles de chaque activité. Ce qui est fait dans le code suivant, où l'on transforme les couples en triplets avec rajout de ce nombre d’activités incompatibles :

def addIncomp(S):
    for i in range(len(S)):
        total = 0
        for j in range(len(S)):
            if (i!=j) and not ((S[j][0]>=S[i][1]) or (S[i][0]>=S[j][1])):
                total+=1
        S[i] = (S[i][0],S[i][1],total)

Le fonctionnement de cette procédure est très simple, on considère les activités une par une et l'on évalue leur nombre d'activités incompatibles grâce à la définition de la sous-partie 2.1.

On peut alors implémenter notre approche gloutonne :

def lessIncompChoice(S):
    addIncomp(S)
    S.sort(key = lambda x : x[2])
    C = []
    for x in S:
        compatibility = True
        for y in C:
            if not ((y[0]>=x[1]) or (x[0]>=y[1])):
                compatibility = False
        if compatibility:
            C.append(x)
    return C

Ce code est quasiment le même que celui de la sous-partie 2.2.1, seul le critère de tri passé au paramètre key changeant. La fonction lambda utilisée associe bien à une activité x son nombre d'activités incompatibles x [ 2 ] , ce que l'on voulait.

Example 1.8. Utilisation de la fonction précédente

activities = [(1,4),(0,6),(3,5),(12,13),(8,11),(8,12),(2,13),\
              (6,10),(5,9),(3,8),(5,7),(13,16),(15,17),(16,19)]

print(lessIncompChoice(activities))
[(12, 13, 1), (13, 16, 1), (16, 19, 1), (1, 4, 4), (8, 11, 4), (5, 7, 5)]

[Note]

Pour respecter le format initial des données, on pourrait bien sûr retransformer les triplets en couple avant l'instruction de retour.

Nous invitons maintenant le lecteur à se demander pourquoi cette méthode n'est pas plus optimale que les deux précédentes.

Exercice corrigé

1.1.

Trouver un contre-exemple prouvant que le résultat retourné par l’heuristique précédente n’est pas toujours optimal. On pourra répondre par un schéma du même type que celui de la fin de la sous-partie 2.1.

Dans le cas de figure suivant, l’heuristique précédente retournerait l’activité en rouge et les deux en violet au lieu des deux en bleu et deux en violet :

Un algorithme glouton

Les tentatives précédentes avaient certes du sens, mais elles avaient surtout comme gros défaut commun de ne pas être optimales.

Il est donc temps de présenter un algorithme qui le soit.

La bonne idée : tri par date de fin

Pour cela nous allons envisager les activités par ordre croissant de leur date de fin. On va ainsi chercher à laisser le plus de temps disponible après la planification d'une activité.

Ceci étant dit, nous allons retrouver nos trois traditionnelles étapes :

  1. Trier les activités par ordre croissant de leur date de fin.

  2. Initialiser la liste C des activités choisies avec l’ensemble vide.

  3. Parcourir dans l’ordre la liste S des activités, et rajouter l’activité courante à C si elle n’est pas incompatible avec celles déjà présentes dans C.

Voici l'implémentation en Python de cette idée :

def firstEndChoice(S):
    S.sort(key = lambda x:x[1])
    C = [S[0]]
    j=0
    for i in range(j+1,len(S)):
        if S[i][0]>=S[j][1]:
            C.append(S[i])
            j=i
    return C

De façon similaire au code de la sous-partie 2.2.2, avant de rajouter l'activité d'indice i il suffit de vérifier que sa date de début est supérieure ou égale à la date de fin de la dernière activité ajoutée à C, indexée ici par l'indice j. Pour la simple raison que les activites étant triées par ordre croissant de leur date de fin, il est impossible pour l'activité j de commencer avant l'activité i.

Example 1.9. Utilisation de l'algorithme précédent

activities = [(1,4),(0,6),(3,5),(12,13),(8,11),(8,12),(2,13),\
              (6,10),(5,9),(3,8),(5,7),(13,16),(15,17),(16,19)]

print(firstEndChoice(activities))
[(1, 4), (5, 7), (8, 11), (12, 13), (13, 16), (16, 19)]

[Note]

On obtiendrait un résultat équivalent en classant les activités par ordre décroissant de leur date de début. Mais cette façon de voir la chose est clairement moins intuitive.

Démonstration de l'optimalité

Soient ( ( b 1 , e 1 ) , ( b 2 , e 2 ) , . . . , ( b n , e n ) ) les activités classées par ordre croissant de leur date de fin.

On va commencer par montrer qu’il existe une solution optimale contenant ( b 1 , e 1 ) , c'est-à-dire contenant le premier élément de la solution retournée par l'algorithme glouton.

Considérons donc X une solution optimale.

Si X contient ( b 1 , e 1 ) on a ce que l'on voulait et donc rien à faire.

Sinon, on est dans une situation du style :

On a représenté en rouge l'activité ( b 1 , e 1 ) , qui au vu du tri effectué se termine nécessairement avant la première activité de la solution optimale X.

On peut alors échanger le premier élément de X avec ( b 1 , e 1 ) sans nuire à l’optimalité. En effet cet échange ne modifie bien sûr pas le nombre d'éléments de X, et dans la mesure où ( b 1 , e 1 ) se termine avant la première activité de ( b 1 , e 1 ) , cette substitution ne créera pas d'incompatibilités.

On montre ensuite que si X est une solution optimale contenant ( b 1 , e 1 ) , alors X ' =X\ ( b 1 , e 1 ) est une solution optimale pour le problème du choix d’activités commençant à la date e 1 . Pour faire cela procédons par l'absurde, i.e. supposons que X ' ne soit pas optimale pour ce sous-problème et considérons X '' une solution qui l'est.

On va alors vérifier que X ''' = X '' ( b 1 , e 1 ) est une solution du problème initial contenant plus d'éléments que X.

Il est clair déjà que X ''' est une solution du problème initial car par construction X '' ne contient que des activités commençant après la date e 1 .

On a d'une part card ( X ' ) = card ( X ) - 1 car X ' contient clairement un élément de moins que X, et d'autre part card ( X ''' ) = card ( X '' ) + 1 car X ''' contient clairement un élément de plus que X '' .

L'hypothèse de notre raisonnement par l'absurde implique que card ( X '' ) > card ( X ' ) , ce qui peut se réécrire d'après la première des deux égalités ci-dessus comme card ( X '' ) > card ( X ) - 1 .

En ajoutant 1 à chacun des termes de cette inégalité et en utilisant la seconde égalité il vient card ( X ''' ) > card ( X ) . Ainsi X ''' serait une solution au problème initial comportant plus d'éléments que X, ce qui est absurde car X est une solution optimale de ce problème.

On a donc montré les deux points suivants :

  1. Il existe une solution optimale contenant ( b 1 , e 1 ) .

  2. Si X est une solution optimale contenant ( b 1 , e 1 ) , alors X ' =X\ ( b 1 , e 1 ) est une solution optimale pour le problème du choix d’activités commençant à la date e 1 .

On peut alors réitérer cet argument et montrer de proche en proche, i.e. par récurrence, que l’on peut transformer toute solution optimale en la solution gloutonne. Q.E.D.

[Note]

L'auteur laisse un tout petit peu de poussière sous le tapis, mais franchement pas beaucoup.

Considérations de complexité

La complexité du parcours de la liste S des activités est clairement un Θ ( n ) , n étant la longueur de cette liste, c'est-à-dire le nombre total d'actvités.

Il ne faut cependant pas conclure hâtivement à une complexité linéaire, puisque le tri préalable de S a lui pour complexité un Θ ( n log ( n ) ) .

La complexité de notre algorithme glouton est donc un Θ ( n log ( n ) ) .

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels