La programmation dynamique: pyramide de nombre

Dans le cadre de l'implantation d’un nouveau forage d’alimentation en eau potable, les géophysiciens ont utilisé une méthode d'imagerie depuis la surface qui consiste à déterminer les propriétés des sous-sols par la mesure de leur conductivité électrique.

Concrètement, cette technique permet de caractériser les différentes couches de matériaux afin de dresser une coupe du sol en 2D sans avoir à creuser:

Exemple d'acquisition de mesures de résistivité
Figure 1: Coupe d'un sol par mesure de conductivité électrique

Les géophysiciens ont effectué un certain nombre de mesures pour essayer de trouver un chemin optimal pour la foreuse. Ils ont établis un système de notation qui prends en compte des propriétés géologiques (teneur en eau, densité, porosité, etc.) pour évaluer une synthèse de la forabilité d'un matériau. Ce système est le suivant:

1 2 3 4 5 6 7 8 9
difficilement forable forabilité optimale

À ce but, les géophysiciens ont fourni des pyramide de nombre contenant des valeurs de 1 à 9. Le poids d’un chemin étant la somme des valeurs parcourues par ce chemin. L’objectif est de trouver le chemin de poids maximal pour faciliter le forage. Ils transmettent les mesures sous la forme de pyramide de nombre (liste de listes) où le sol est représenté à la base de la pyramide, et l'objectif de forage est représenté au sommet (aux indices 0,0).

La foreuse peut se déplacer à chaque fois en diagonale d’une case vers le bas, et d'une case sur la gauche ou sur la droite.

Les élèves de NSI du lycée Jean-Paul Sartre mettent à disposition la fonction poids_meilleur_chemin_rec(pyramide: list) ainsi que 2 fonctions auxilaires sous_pyramide_droite(pyramide: list) et sous_pyramide_gauche(pyramide: list).
Récuperer ces fonctions dans le fichier pyramide-force-brute.py

Récuperer les mesures des géophysiciens dans le fichier mesure.py

  1. Exécuter la fonction poids_meilleur_chemin_rec sur la pyramide de nombre mesure1 et mesure2. Quel est le problème?

Approche bottom-up

On peut chercher à mémoïser les étapes intermédiaires pour gagner en efficacité. Une stratégie peut être de reconstruire une pyramide de même taille que la pyramide de mesures des géophysiciens, et d'enregistrer le poids maximal du chemin à partir d'une case à la place de cette case. On fait ainsi remonter l'information du poids du meilleur chemin du bas vers le haut. Il suffit alors de lire la valeur du sommet de la pyramide pour connaître le poids de ce chemin.

Les pyramides de mémoïsation successives sont les suivantes:

Pyramide de nombre

3
7
6
1
2
9
8
5
4
2
Pyramide de mémoïsation
0
0
0
0
0
0
8
5
4
2
0
0
0
9
7
13
8
5
4
2
0
16
19
9
7
13
8
5
4
2
22
16
19
9
7
13
8
5
4
2

  1. Écrire la fonction pmc_bottom_up(pyramide: list) (pour poids meilleur chemin) de façon à implémenter l'approche bottom-up mémoïsant les calculs dans une pyramide (voir: Aide ↓) pour éviter de répéter des calculs.

Aide

On pourra au choix:

>>> mesure1 = [[3], [7,6], [1,2,9], [8,5,4,2]]
>>> pmc_bottom_up(mesure1)
22

  1. Soit nn le nombre de cases dans une pyramide de nombre. Quelle est la complexité en temps de l'algorithme bottom-up? Quelle est la complexité en espace de votre implémentation?

On peut tester l'avantage de cette implémentation de la programmation dynamique sur les mesures mesure2 des géophysiciens.

Approche top-down

Chaque case de la pyramide (sauf le sommet) possède un ou deux parents (parent = case du dessus permettant d'y parvenir).

L'algorithme top-down consiste à parcourir itérativement la pyramide ligne par ligne, et tout les sommets de chaque ligne pour ajouter le plus grand des parents (ou le seul parent) au sommet courant et d'enregistrer à la case courante le poids du chemin qui permet de l'atteindre. On fait ainsi descendre l'information du poids du meilleur chemin du haut vers le bas.

Finalement il faut identifier le maximum de la dernière ligne de la pyramide pour trouver le poids de ce chemin.

3
7
6
1
2
9
8
5
4
2
3
10
9
1
2
9
8
5
4
2
3
10
9
11
12
18
8
5
4
2
3
10
9
11
12
18
19
17
22
20

Lors du parcours de tout les sommets d'une ligne, on distinguera 3 cas:

  1. Écrire la fonction pmc_top_down(pyramide: list) qui parcourt la chaque sommet de la pyramide itérativement en la modifiant pour obtenir une "pyramide des meilleurs chemins" et renvoie le poids du meilleur chemin de cette pyramide.

>>> mesure1 = [[3], [7,6], [1,2,9], [8,5,4,2]]
>>> pmc_top_down(mesure1)
22

Bonus

Les géophysiciens souhaitent s'assurer de la robustesse des fonctions pmc (questions 2 et 4). Ils proposent d'effectuer une batterie de tests sur un grand nombre de pyramide du même format que les mesures qu'ils ont fourni dans le fichier mesure.py.

Le module random de python permet de générer des valeurs aléatoires.

>>> import random
>>> random.randint(1,9)
4

  1. Écrire une fonction generer_donnees_test(n: int) qui renvoie une pyramide de nombre remplie de valeurs aléatoires pour mieux tester les fonctions pmc.

>>> generer_donnees_test(5)
[[3], [2, 7], [5, 1, 4], [4, 7, 9, 5], [3, 6, 8, 2, 1]]

  1. Modifier la fonction poids_meilleur_chemin_rec(pyramide: list) fournie dans le fichier pyramide-force-brute.py en y rajoutant de la mémoïsation. On pourra avoir besoin de rajouter des paramètres ligne et colonne pour permettre de retrouver l'emplacement courant (le sommet d'une sous-pyramide) par rapport à la pyramide initiale.

fonction poids_meilleur_chemin_rec(pyramide, ligne, colonne)
    poids ← sommet de la sous-pyramide (pyramide[ligne][colonne])
    si la sous-pyramide n'a qu'1 élément, alors memo[ligne][colonne] ← poids
    si memo[ligne][colonne] est vide:
        gauche ← poids_meilleur_chemin_rec sur la sous-pyramide gauche (modifier ligne, colonne)
        droite ← poids_meilleur_chemin_rec sur la sous-pyramide droite (modifier ligne, colonne)
        poids ← poids + max entre gauche et droite
        memo[ligne][colonne] ← poids
    fin si
    renvoyer memo[ligne][colonne]
fin fonction