Introduction

Nous allons nous intéresser au raisonnement et à la résolution des deux exercices de niveau 4 des épreuves régionales de cette année, vous pouvez les trouver ici : https://prologin.org/train/2020/semifinal

La première partie sera assez intuitive, suivie du code que l’on aura pu écrire à partir de cette intuition, que l'on devra optimiser pour qu'il soit utilisable, et surtout qu'il passe les tests de performance ;)

Cette correction n'a pas pour but d'être très exhaustive, ni parfaite, elle donne des idées qui pourront aider ceux qui ne connaissent pas la notion de programmation dynamique. Si vous avez des remarques, sur cette correction, n'hésitez pas à nous le dire en répondant au thread.

Bonne lecture !

De l'intuition ...

L’idée de base de ces deux exercices est de résoudre un problème de choix : on a un certain nombre de décisions à faire. Les décisions que l’on va prendre, au fur et à mesure du problème, vont impacter les décisions futures que nous pourrons faire, on peut donc dire que ces décisions sont dépendantes les unes des autres.

On commence à se faire une petite idée de ce à quoi le problème ressemble.

Pour simplifier l’explication et la correction, on va se concentrer sur le problème space_bus. La meilleure des façons d’apprendre… c’est d’essayer !

Si vous avez déjà une idée de comment résoudre le problème, allez-y : https://prologin.org/train/2020/semifinal/space_bus

Revenez lire la correction une fois que vous avez implémenté votre idée !

Si vous n’avez aucune idée de comment on peut résoudre ce problème, lisez quand même le sujet, plusieurs fois, et essayez de le reformuler. Rappelez-vous, c’est normal de ne pas y arriver dès le début ! Mais bien comprendre le problème vous permettra de mieux le résoudre et d’avoir une intuition de comment le résoudre ! Soyons un peu lettré : “Ce que l’on conçoit bien s’énonce clairement, et les mots pour le dire arrivent aisément.” - N. Boileau

Prenez quelques instants pour lire le sujet de l'exercice, et y réfléchir.

L’idée donc, comme je l’ai rapidement dit plus haut, c’est de faire des choix ! Ici, à chaque étape du trajet, Joseph a le choix de prendre ou non de nouveaux passagers. Nous n'avons qu'une seule contrainte, prendre les passagers d'un certain arrêt prend du temps, et l'on ne doit pas dépasser le temps maximal dont Joseph dispose !

... vers la résolution !

On a pu donc reformuler notre problème en : "Soit on prend des passagers, soit on ne les prend pas. De plus, si on a décidé de prendre les passagers, on doit faire attention à ne pas dépasser le temps maximal." ; cette idée est à effectuer récursivement pour chaque arrêt.

On peut modéliser cette résolution avec un arbre, avec un papier et un crayon, on peut représenter chaque étape du problème avec un arbre binaire : chaque nœud correspond à un état, l'arrêt de bus auquel nous sommes actuellement, et le nombre de temps qu'il nous reste, en fonction des décisions que l'on a pris avant. Et le passage vers l'un deux nœuds fils correspondent à la décision de prendre, ou non, les passagers de l'arrêt suivant.

On pourrait écrire du un premier algorithme naïf récursif qui résout ce problème, en testant tous les cas possibles (on commence déjà à sentir notre PC chauffer) : 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def space_bus(n, p, t, m):
    def rec(index, reste):
        # on vérifie si on a dépassé la taille maximale
        if index >= n:
            return 0

        # on saute l'élément actuel, vu qu'on ne le prend pas
        on_prend_pas = rec(index + 1, reste)

        # si on a encore suffisament de temps, on le prend
        if t[index] <= reste:
            # on ajouter le nombre de personnes, et on retire
            # du reste le temps que cela nous a pris
            on_prend = p[index] + rec(index + 1, reste - t[index])
        else:
            # sinon c'est qu'on ne **peut** pas le prendre
            on_prend = 0

        # on retourne le maximum des deux appels qu'on vient
        # de faire
        return max(on_prend, on_prend_pas)

Cette solution naïve permet de résoudre le problème donné.

Récapitulons rapidement :

On a un tableau des éléments qu'on veut parcourir, ici les arrêts de bus.

Vu qu'on veut parcourir récursivement (par soucis de simplicité) ce tableau, il nous faut un cas d'arrêt : l'index actuel du tableau doit être dans les bornes du tableau, donc plus petit que n. Vu que l'on veut un nombre maximal, on retourne 0 quand on est sorti du tableau, car 0 sera toujours plus petit que le nombre de personnes à un arrêt.

Ensuite, on fait nos décisions : soit on prend les passagers, soit on ne les prend pas. Ici on a choisit de d'abord ne pas prendre les passagers, et après de les prendre, mais l'inverse est tout à fait possible.

Je vous laisse imaginer l'arbre de récursion, plutôt basique pour ce problème, que ce programme génère.

On se rend rapidement compte que les deux paramètres de fonction rec(index, reste) vont potentiellement être répétés : on va avoir beaucoup d'appels que l'on aura déjà effectué !

Et c'est là toute la force de la programmation dynamique.

Une approche dynamique

Même si notre programme résout le problème, et en testant chez nous plusieurs configurations et plusieurs entrées (il est aussi possible de le tester sur le site de Prologin, mais c'est une meilleure habitude de tester en local !), on remarque que, pour des entrées relativement petites, on a aucun problème, mais dès qu'on augmente la taille de l'entrée, le programme prend bien plus de temps, trop de temps !

L'idée derrière la programmation dynamique, et je ne rentrerai pas forcément trop dans les détails, est de mémoriser les valeurs de retour de notre fonction récursive.

Ce procédé porte un petit nom : la mémoïsation. Il permet de ne pas avoir a recalculer des valeurs intermédiaires dont on a pas besoin in fine. Ce sont en effet ces valeurs intermédiaires qui prennent le plus de temps à calculer, lorsque l'entrée est très grande.

Comment fait-on pour "mémoïser" les valeurs intermédiaires me dis tu ?

Et bien c'est très simple... il suffit d'utiliser une liste :)

Ou plutôt ici, une liste de liste, une liste à deux dimensions.

En effet, on veut retenir les valeurs intermédiaires qui sont fonctions de index et de reste. On a donc un tableau à deux entrées, une représentant les index, et une autre représentant les restes.

Le but de se souvenir de ces valeurs étant de ne plus les recalculer à chaque fois, il faut donc ajouter un nouveau cas d'arrêt !

Je vous laisser essayer d'appliquer ce principe au programme que nous venons d'écrire ensemble, et je vous montre après comment je l'ai fait moi...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def space_bus(n, p, t, m):

    # on initialise une liste avec les contraintes données
    # dans le sujet
    temps_max = m + 1
    nb_stations_max = 500
    liste = [[-1 for _ in range(temps_max)] for _ in range(nb_stations_max)]

    def rec(index, reste):
        # on vérifie si on a dépassé la taille maximale
        if index >= n:
            return 0
        # si la valeur dans liste[index][reste] n'est pas
        # celle par défaut (-1), alors c'est qu'on l'a déjà
        # calculée ! On la retourne donc directement
        # sans réfléchir :)
        if liste[index][reste] != -1:
            return liste[index][reste]

        # on saute l'élément actuel, vu qu'on ne le prend pas
        on_prend_pas = rec(index + 1, reste)

        # si on a encore suffisament de temps, on le prend
        if t[index] <= reste:
            # on ajouter le nombre de personnes, et on retire
            # du reste le temps que cela nous a pris
            on_prend = p[index] + rec(index + 1, reste - t[index])
        else:
            # sinon c'est qu'on ne **peut** pas le prendre
            on_prend = 0

        # on garde en mémoire le maximum des deux appels
        # qu'on vient de faire, sans le retourner (mémoïsation)
        liste[index][reste] = max(on_prend, on_prend_pas)
        return liste[index][reste]

Et voilà ! La magie de programmation dynamique est intervenue, notre programme est maintenant bien plus rapide !

Récapitulons une fois de plus ce que nous avons fait :

  • On a défini notre problème, de sorte à pouvoir le résoudre récursivement, en se rendant compte que ce problème était un problème de décisions, et que ces décisions impactaient les décisions d'après,
  • On a écrit un algorithme récursif naïf qui résout le problème pour des petites entrées,
  • On s'est rendu compte que dès que les entrées sont trop grandes, le temps pris par notre programme est trop grand,
  • En utilisant le principe de mémoïsation, et en utilisant une liste pour se souvenir des valeurs intermédiaires de retour de notre fonction récursive, on a réduit considérablement le temps que prend notre programme pour s'exécuter.

La programmation dynamique n'a rien de magique en réalité ! Je vous laisse tester en local, en augmentant la taille de l'entrée puis en comparant la première version que nous avons écrite et la version dynamique, vous vous rendrez compte du temps gagné.

Sous Linux, vous pouvez utiliser la commande time python3 space_bus.py < test.txt, où test.txt est un fichier de test respectant le modèle des exemples donnés.

En conclusion

Merci beaucoup d'avoir pris le temps de lire ce petit article explicatif ! En espérant qu'il vous aura plu, et qu'il vous aura permis d'avoir un premier aperçu de la programmation dynamique.

L'algorithme proposé n'est pas forcément le plus optimal, et la liste qui nous permet de stocker les valeurs intermédiaires est trop grande ! Je vous laisse réfléchir à comment réduire la taille de cette liste, tout en ne perdant pas d'information : vous pouvez par exemple regarder chaque indice que l'on appelle, pour vous rendre compte de quelle partie de la liste est utilisée à quel moment !

Comme toujours, n'hésitez pas répondre à ce thread si vous avez des questions, ou si vous voulez avoir plus d'exercices corrigés comme ça (si oui, lesquels ?), ou nous donner votre avis ! :)

À bientôt !