Processing math: 100%

Récursivité : planning hippique

Le propriétaire d'un cheval se penche sur le calendrier des courses hippiques de la saison à venir :

  • chaque jour il y a une course hippique à laquelle il peut participer;
  • chacune des courses hippiques offre un prix pour le vainqueur;
  • après avoir participé à une course, le cheval doit se reposer et ne peut participer à une nouvelle course que quatre jours plus tard.

Le propriétaire cherche à choisir les courses auxquelles il participera en maximisant le montant total des prix qu'il pourra récolter s'il gagne.

On suppose que le calendrier des courses est implémenté par un tableau indexé cal pour lequel la valeur d'indice i est le prix offert pour la course du ième jour de la saison (en commençant à zéro).

Exemple :

cal = [2, 1, 10, 6, 8, 20, 22, 10, 4, 20, 2, 4, 14, 2, 6] est de taille 13.

Le propriétaire peut choisir comme planning [0, 4, 8, 12] auquel cas le montant total des prix est 2 + 8 + 4 + 14 = 28. Ce planning n'est clairement pas optimal.

Le propriétaire peut choisir comme planning [0, 5, 9, 14] auquel cas le montant total des prix est 2 + 20 + 20 + 6 = 48. Ce planning est meilleur que le précédent, c'est même le meilleur de tous les plannings : il est optimal.

Le propriétaire ne peut pas choisir comme planning [2, 6, 9, 12] car il n'y a pas quatre jours d'écarts entre les jours d'indice 6 et 9 ni entre les jours d'indices 9 et 12.

Question 1 :

  • Proposer - en français - un algorithme glouton permettant, à partir d'un calendrier des courses, de proposer un planning.

  • Appliquer cet algorithme sur l'exemple ci-dessus.

  • Sur cet exemple, est-ce que cet algorithme fournit un planning optimal ?

  • Si n est la taille du calendrier, quelle est la complexité de cet algorithme : O(n) ? O(n2) ?

Solution

  • Jusqu'à ce qu'il ne reste plus de course disponible :

    • Parmi les courses encore disponibles, choisir celle offrant le prix le plus élevé,
    • Enlever des courses disponibles la course choisie ainsi que les trois courses situées avant et après la course choisie.

  • On choisit cal[6]=22 puis cal[12]=14 puis cal[2]=10 ce qui conduit à un prix total de 46.

  • Si on choisit cal[5]=20, cal[9]=20, cal[14]=6 et cal[0]=2 on aboutit au planning optimal [0, 5, 9, 14] soit un montant total de 48.

  • La complexité de cet algorithme est en O(n2) en version naïve : en effet à chaque étape la recherche de la course avec le prix le plus élevé est en O(n2) en moyenne et on effectue O(n7) telles recherches, soit du O(n214)=O(n2).

Question 2 :

On note planning(cal, n) un planning optimal que choisit le propriétaire lorsqu'on considère uniquement les jours d'indices 0 à n du calendrier cal et on note total_prix(cal, n) le montant total des prix correspondant.

On considère le calendrier cal = [15, 15, 25, 6, 2, 15, 6, 15, 6, X] d'indice maximal 9 et dont le dernier prix cal[9] n'est pas encore fixé.

  • On admet que total_prix(cal, 5) = 30. Quelle est la valeur de planning(cal, 5) ?

  • On admet que total_prix(cal, 8) = 40. Quelle est la valeur de planning(cal, 8) ?

  • Si X est très grand, l'indice 9 fera partie du planning optimal. Déterminer :

    • à partir de quelle valeur de X ce sera le cas ;
    • si c'est le cas, quel sera le planning optimal.

  • Et si ce n'est pas le cas ?

Solution

  • planning(cal, 5) = [0, 5] ou planning(cal, 5) = [1, 5] conviennent (prix total 30).

  • planning(cal, 8) = [2, 7] convient (prix total 40).

  • Si X est plus grand que 11, on rajoute le jour d'indice 9 à planning(cal, 5) pour obtenir [0, 5, 9] ce qui donne total_prix(cal, 9) = 30 + X > 40.

  • Sinon il suffit de garder planning(cal, 8).

Question 3.1 :

On considère le calendrier cal = [......, 15, 2, 5, 25, 18] d'indice maximal 14 et dont les premiers éléments ont été masqués. On sait en revanche que :

  • planning(cal, 10) = [1, 5, 10] et total_prix(cal, 10) = 52,
  • planning(cal, 13) = [1, 5, 9, 13] et total_prix(cal, 13) = 69.

Combien valent planning(cal, 14) et total_prix(cal, 14)?

Solution

Puisque 52 + 18 > 69 on a intérêt à choisir la course du jour d'indice 14 ce qui donne planning(cal, 14) = planning(cal, 10) + [14] = [1, 5, 10, 14] et total_prix(cal, 14) = 70.


Question 3.2 :

On considère le calendrier cal = [......, 15, 2, 5, 25, 9] d'indice maximal 14 et dont les premiers éléments ont été masqués. On sait en revanche que :

  • planning(cal, 10) = [1, 5, 10] et total_prix(cal, 10) = 52,
  • planning(cal, 13) = [1, 5, 9, 13] et total_prix(cal, 13) = 69.

Combien valent planning(cal, 14) et total_prix(cal, 14)?

Entrée[ ]:
Solution

Puisque 52 + 9 < 69 on n'a pas intérêt à choisir la course du jour d'indice 14 mais à rester sur le meilleur planning obtenu sur les courses d'indices 0 à 13, ce qui donne planning(cal, 14) = planning(cal, 13) = [1, 5, 9, 13] et total_prix(cal, 14) = total_prix(cal, 13) = 69.


Question 4 :

Si n>=4, déterminer une relation de récursivité (cas général) permettant de calculer total_prix(cal, n) à partir de total_prix(cal, n-4), total_prix(cal, n-1) et cal[n].

Solution

On regarde le prix total sur le planning des n - 4 premiers jours augmenté du prix du jour d'indice n, c'est à dire total_prix(cal, n - 4) + cal[n]

  • Si le résultat obtenu est supérieur au prix total sur le planning des n - 1 premiers jours, ce résultat obtenu correspond à total_prix(cal, n).

  • Sinon c'est le prix total sur le planning des n - 1 premiers jours qui correspond à prix_total(cal, n)

Au final cela conduit à la relation de récursivité suivante :

total_prix(cal, n) = max ( total_prix(cal, n-4) + cal[n] , total_prix(cal, n-1) )


Question 5 :

Si n<4 (cas de base) déterminer comment calculer total_prix(cal, n) à partir de cal[i] pour i entre 0 et n.

Solution

On choisit tout simplement le meilleur des n premiers jours, c'est à dire que l'on a :

total_prix(cal, n) = max ( [ cal[i] for i in range(n+1) ] )


Question 6 :

Implémenter ci-dessous la fonction total_prix(cal, n) en utilisant un algorithme récursif. On pourra utiliser le jeu de tests fourni plus bas pour tester sa fonction.

Entrée[ ]:
Entrée[ ]:
Solution 
def total_prix(calendrier, jour):
    if jour < 4:
        prix_total_max = max(calendrier[i] for i in range(jour + 1))
        return prix_total_max
    else:
        prix_total_max = max(total_prix(calendrier, jour - 1), 
                             total_prix(calendrier, jour - 4) + calendrier[jour])
        return prix_total_max

Question 7 :

  • Implémenter une fonction cal_aletoire(N) générant des calendriers aléatoires de taille N passée en argument (en utilisant randint(a, b) du module random et des tableaux définis en compréhension).

  • En utilisant ces calendriers aléatoires, tester la fonction total_prix sur des calendriers de taille 35, puis 40, puis 45, puis 50 etc.

  • À partir de quelle taille de calendrier l'algorithme met-il plus de quelques secondes à s'exécuter ?

Attention : Sous basthon, avant de faire ces tests il convient d'effectuer une sauvegarde de votre travail au cas où vous planteriez le noyau Python.

Entrée[ ]:
Solution 
from random import randint

def calendrier_aleatoire(N):
    return [randint(1, 25) for _ in range(N)]

c = calendrier_aleatoire(40)
total_prix(c, 39)                #remarquer le décalage de 1 entre 50 et 49 (taille 50 : indices de 0 à 49)

On remarque qu'à partir d'une taille de calendrier environ égale à 50, l'algorithme commence à prendre plusieurs secondes à s'exécuter.

Question 8 :

Dessiner soigneusement sur une feuille l'arbre des appels récursifs à total_prix(cal, n) lorsque l'appel principal est total_prix(cal, 9). Combien d'appels sont effectués en tout (appel principal compris) ?


En utilisant cet arbre récursif comme support de réflexion et de comptage, combien d'appels récursifs sont effectués lors de l'appel principal à total_prix(cal, 10) ? et lors de l'appel principal à total_prix(cal, 11) ? et pour total_prix(cal, 12) ? et pour total_prix(cal, 13) ?

En quoi ces résultats sont-ils reliés à la question 7 ?

Solution 

                    9
                   / \
                  /   \
                 /     \
                /       \
               8         5
              / \       / \
             /   \     /   \
            7     4   4     1
           /|    /|   |\
          / |   / |   | \
         6  3  3  0   3  0
        /|
       / |
      5  2
     /|
    / |
   4  1
  /|
 / |
3  0

En tout, 19 appels sont effectués lors de l'appel principal total_prix(cal, 9).

Lors de l'appel principal total_prix(cal, 10), on effectue 1 appel principal, 1 appel à total_prix(cal, 9) (comportant 19 appels) et 1 appel à total_prix(6) (comportant 7 appels - voir ci-dessous) soit 1+19+7 = 27 appels.

Pour total_prix(11) on effectuera 1 + 27 + 9 = 37 appels.

Pour total_prix(12) on en effectuera 1 + 37 + 13 = 51.

Et enfin pour total_prix(13) on en effectuera 1 + 51 + 19 = 71.

Le nombre d'appels récursifs effectués lors de l'appel principal total_prix(cal, n) ne semble pas linéaire : il augmente de plus en plus vite et semble quadratique voire exponentiel. Cela explique sans doute que l'algorithme met du temps à s'exécuter même pour des valeurs de n petites.


Question 9 :

  • Compléter/modifier le code de la fonction suivante pour qu'elle renvoie le nombre d'appels récursifs effectués lors de l'appel principal à total_prix(cal, n) avec n>=4.

  • Combien d'appels sont effectués pour n = 100 ?

  • Est-ce que cela est en accord avec les deux questions précédentes ?

Entrée[ ]:
Solution 

def nombre_appels(n):
    assert n>=4
    nb_appels = [1, 1, 1, 1]
    for appel in range(4, n+1):
        nb_appels.append(1 + nb_appels[appel-1] + nb_appels[appel-4]) # à modifier
    return nb_appels[n]

Pour n = 100 on a 108 654 474 368 651 appels qui sont effectués. Ce nombre est très grand (de l'ordre de 10 puissance 14) ce qui est en accord avec les deux questions précédentes.


Question 10 :

On admet que la taille de l'arbre des appels récursifs de planning(cal, n) augmente lorsque n augmente.

  • Justifier que lorsque n augmente de 4, la taille de l'arbre des appels récursifs de planning(cal, n) est au moins multipliée par deux.

  • Qu'en déduit-on : que la complexité de l'algorithme récursif est au moins quadratique ou au moins exponentielle ?

Solution

L'arbre des appels récursifs de planning(cal, n) est constitué de sa racine et de deux arbres d'appels récursifs : celui de planning(cal, n-4) et celui de planning(cal, n-1).

Puisque l'arbre des appels récursifs de planning(cal, n-1) est plus grand que celui de planning(cal, n-4), on en déduit que la taille de celui de planning(cal, n) est au moins égale à deux fois la taille de ceui de planning(cal, n-4).

Lorsqu'une quantité est multipliée par un même nombre à intervalles réguliers, on est dans le cadre d'une croissance exponentielle (confère cours d'enseignement scientifique : démographie). Ici on est donc dans une croissance au moins exponentielle.


Questions bonus

Question Bonus A :

Reprendre les deux questions précédentes n° 4 et 5 pour le planning optimal planning(cal, n) au lieu de total_prix(cal, n). La relation de récursivité utilisera notamment total_prix.

Solution 

Cas de base (n<4):          
planning(cal, n) = [j] où `j` est choisi tel que cal[j] est le plus grand prix offert entre les courses de 0 à n.
                   S'il y a deux courses offrant le même prix maximal, on choisit celle qui a lieu 
                   le plus tôt pour avoir le plus de jours de repos ensuite.
    
    
Cas général (n>=4):
planning(cal, n) = planning(cal, n-4) + [n] si total_prix(cal, n-4) +  cal[n] >  total_prix(cal, n-1)
                 = planning(cal, n-1)       sinon

Question Bonus B ( ⋆⋆⋆ ):

Implémenter ci-dessous la fonction planning(cal, n) en utilisant un algorithme récursif.
Compte-tenu de la relation de récursivité associée au planning optimal, elle renverra à la fois le total optimal et le planning optimal.

Entrée[ ]:
Entrée[ ]:
Solution 

def planning(calendrier, jour):
    if jour < 4:
        total_prix_max = 0
        for i in range(jour + 1):
            if calendrier[i] > total_prix_max:
                total_prix_max = calendrier[i]
                planning_max = [i]
        return total_prix_max, planning_max
    else:
        total_prix_j_moins_1, planning_j_moins_1 = planning(calendrier, jour - 1)
        total_prix_j_moins_4, planning_j_moins_4 = planning(calendrier, jour - 4)
        
        if total_prix_j_moins_1 > total_prix_j_moins_4 + calendrier[jour]:
            total_prix_max = total_prix_j_moins_1
            planning_max = planning_j_moins_1
            
        else:
            total_prix_max = total_prix_j_moins_4 + calendrier[jour]
            planning_max = planning_j_moins_4
            planning_max.append(jour)
            
        return total_prix_max, planning_max

Chargement de Basthon...