Parcours de cout maximum dans une grille.⚓︎
D'après 2021, Sujet 0, Ex. 2
On considère un tableau de nombres de n
lignes et m
colonnes.
Les lignes sont numérotées de 0
à n - 1
et les colonnes sont numérotées de 0
à m - 1
. La case en haut à gauche est repérée par (0, 0)
et la case en bas à droite par (n - 1, m - 1)
.
On appelle chemin une succession de cases allant de la case (0, 0)
à la case (n - 1, m - 1)
, en n'autorisant que des déplacements case par case : soit vers la droite, soit vers le bas.
On appelle somme d'un chemin la somme des entiers situés sur ce chemin.
Par exemple, pour le tableau T
suivant :
4 | 1 | 1 | 3 |
2 | 0 | 2 | 1 |
3 | 1 | 5 | 1 |
- Un chemin est
(0, 0)
,(0, 1)
,(0, 2)
,(1, 2)
,(2, 2)
,(2, 3)
; - La somme du chemin précédent est 14 ;
(0, 0)
,(0, 2)
,(2, 2)
,(2, 3)
n'est pas un chemin.
L'objectif de cet exercice est de déterminer la somme maximale pour tous les chemins possibles allant de la case (0, 0)
à la case (n - 1, m - 1)
.
1. On considère tous les chemins allant de la case (0, 0)
à la case (2, 3)
du tableau T
donné en exemple.
1.a. Un tel chemin comprend nécessairement 3 déplacements vers la droite. Combien de déplacements vers le bas comprend-il ?
Réponse
2 déplacements :
- 1 pour passer de la ligne 0 à la ligne 1,
- un autre pour passer de la ligne 1 à la ligne 2.
1.b. La longueur d'un chemin est égale au nombre de cases de ce chemin. Justifier que tous les chemins allant de (0, 0)
à (2, 3)
ont une longueur égale à 6.
Réponse
Un tel chemin comporte 3 déplacements vers la droite d'après l'énoncé et 2 déplacements vers le bas (question précédente), donc 3 + 2 = 5 déplacements.
Un chemin qui comporte \(k\) déplacements a une longueur de \(k + 1\) cases puisqu'il faut compter la première case.
Nous avons donc une longueur de \(5 + 1 = 6\).
2. En listant tous les chemins possibles allant de (0, 0)
à (2, 3)
du tableau T
, déterminer un chemin qui permet d'obtenir la somme maximale et la valeur de cette somme.
Aide : il est possible de placer tous les chemins sur un arbre de possibilités dont la racine serait la case (0, 0)
.
Réponse
flowchart TD
A00["(0, 0)\n s=4"] --> A01["(0, 1)\n s=5"]
A00 --> A10["(1, 0)\n s=6"]
A01 --> A0102["(0, 2)\n s=6"]
A01 --> A0111["(1, 1)\n s=5"]
A10 --> A1011["(1, 1)\n s=6"]
A10 --> A1020["(2, 0)\n s=9"]
A0102 --> A010203["(0, 3)\n s=9"]
A0102 --> A010212["(1, 2)\n s=8"]
A0111 --> A011112["(1, 2)\n s=7"]
A0111 --> A011121["(2, 1)\n s=6"]
A1011 --> A101112["(1, 2)\n s=8"]
A1011 --> A101121["(2, 1)\n s=7"]
A1020 --> A102021["(2, 1)\n s=10"]
A010203 --> A01020313["(1, 3)\n s=10"]
A010212 --> A01021213["(1, 3)\n s=9"]
A010212 --> A01021222["(2, 2)\n s=13"]
A011112 --> A01111213["(1, 3)\n s=8"]
A011112 --> A01111222["(2, 2)\n s=12"]
A011121 --> A01112122["(2, 2)\n s=11"]
A101112 --> A10111213["(1, 3)\n s=9"]
A101112 --> A10111222["(2, 2)\n s=13"]
A101121 --> A10112122["(2, 1)\n s=12"]
A102021 --> A10202122["(2, 2)\n s=15"]
A01020313["(1, 3)\n s=10"] --> fin0["(2, 3)\n s=11"]
A01021213["(1, 3)\n s=9"] --> fin1["(2, 3)\n s=10"]
A01021222["(2, 2)\n s=13"] --> fin2["(2, 3)\n s=14"]
A01111213["(1, 3)\n s=8"] --> fin3["(2, 3)\n s=9"]
A01111222["(2, 2)\n s=12"] --> fin4["(2, 3)\n s=13"]
A01112122["(2, 2)\n s=11"] --> fin5["(2, 3)\n s=12"]
A10111213["(1, 3)\n s=9"] --> fin6["(2, 3)\n s=10"]
A10111222["(2, 2)\n s=13"] --> fin7["(2, 3)\n s=14"]
A10112122["(2, 1)\n s=12"] --> fin8["(2, 3)\n s=13"]
A10202122["(2, 2)\n s=15"] --> fin9["(2, 3)\n <strong>s=16</strong>"]
((0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3))
donne 11((0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3))
donne 10((0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3))
donne 14((0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3))
donne 9((0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3))
donne 13((0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3))
donne 12((0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (2, 3))
donne 10((0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 3))
donne 14((0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3))
donne 13((0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3))
donne 16
Le dernier chemin est celui qui permet d'obtenir la somme maximale.
3. On veut créer le tableau T_p
où chaque élément T_p[i][j]
est la somme maximale pour tous les chemins possibles allant de (0, 0)
à (i, j)
.
3.a. Compléter et recopier sur votre copie le tableau T_p
, donné ci-dessous, associé au tableau T
.
4 | 5 | 6 | ... |
6 | ... | 8 | 10 |
9 | 10 | ... | 16 |
Réponse
4 | 5 | 6 | 9 |
6 | 6 | 8 | 10 |
9 | 10 | 15 | 16 |
3.b. Justifier que si 0 < j < m
, alors : T_p[0][j] = T[0][j] + T_p[0][j - 1]
.
Réponse
Supposons un chemin (0, 0), ..., (0, j - 1)
, qui va de (0, 0)
à la case située juste à gauche de (0, j)
: son cout maximal est T_p[0][j - 1]
.
On ne peut prolonger ce chemin vers la case (0, j)
qu'en lui ajoutant cette case : le chemin (0, 0), ..., (0, j - 1), (0, j)
sera donc le chemin de cout maximal de (0, 0)
à (0, j)
et son cout sera T[0][j] + T_p[0][j - 1]
4. Justifier que si 0 < i < n
et 0 < j < m
, alors :
T_p[i][j] = T[i][j] + max(T_p[i - 1][j], T_p[i][j - 1])
.
Réponse
Soit un chemin de cout maximal de (0, 0)
à (i, j)
. L'avant-dernière case de ce chemin est soit (i-1, j)
, soit (i, j - 1)
.
Si le cout T_p[i - 1][j]
du chemin de cout maximal de (0, 0)
à (i - 1, j)
est supérieur au cout T_p[i][j - 1]
du chemin de cout maximal de (0, 0)
à (i, j - 1)
, l'avant-dernière case est (i - 1, j)
, sinon, c'est (i, j - 1)
.
Le cout T_p[i][j]
du chemin de cout maximal de (0, 0)
à (i, j)
est donc le plus grand des deux, additionné au cout T[i][j]
de la case (i, j)
.
5. On veut créer la fonction récursive somme_max
ayant pour paramètres un tableau T
, un entier i
et un entier j
. Cette fonction renvoie la somme maximale pour tous les chemins possibles allant de la case (0, 0)
à la case (i, j)
.
5.a. Quel est le cas de base, à savoir le cas qui est traité directement sans faire appel à la fonction somme_max
? Que renvoie-t-on dans ce cas ?
Réponse
Le cas de base est celui où i
et j
sont égaux à 0
et il faut renvoyer, dans ce cas, T[0][0]
.
5.b. À l'aide de la question précédente, écrire en Python la fonction récursive somme_max
.
Réponse
def somme_max(T, i, j):
"""Renvoie le cout d'un chemin de cout maximal
entre la case (0, 0) et la case (i, j) du tableau T
"""
if (i == 0) and (j == 0):
return T[0][0]
elif i == 0:
return T[i][j] + somme_max(T, i , j - 1)
elif j == 0:
return T[i][j] + somme_max(T, i - 1, j )
else:
return T[i][j] + max(
somme_max(T, i , j - 1),
somme_max(T, i - 1, j )
)
Une alternative plus simple est
def somme_max(T, i, j):
"""Renvoie le cout d'un chemin de cout maximal
entre la case (0, 0) et la case (i, j) du tableau T
"""
if (i < 0) or (j < 0):
return 0
else:
return T[i][j] + max(
somme_max(T, i , j - 1),
somme_max(T, i - 1, j )
)
Elle est correcte dès que T
ne comporte que des nombres positifs.
5.c. Quel appel de fonction doit-on faire pour résoudre le problème initial ?
Réponse
Dans le cas d'un tableau de 3 lignes et 4 colonnes, l'appel sera :
>>> somme_max(T, 2, 3)
16
Dans le cas d'un tableau de n
lignes et m
colonnes, l'appel sera :
>>> somme_max(T, n - 1, m - 1)
16
On peut aussi faire une fonction qui suppose que T
est non vide et bien formé.
def reponse_somme_max(T):
n = len(T)
m = len(T[0])
return somme_max(T, n - 1, m - 1)
6. Écrire en python la fonction tab_sommes_max
qui a comme paramètre un tableau T
et qui renvoie le tableau T_p
décrit à la question 3 (T_p[i][j]
est la somme maximale pour tous les chemins possibles dans T
entre (0, 0)
et (i, j)
).
Il est garanti que chaque ligne du tableau T
comporte un même nombre d'éléments, tous entiers positifs.
- Aide
- pour pouvoir utiliser directement la formule de la question 4, vous pourriez « encadrer » le tableau
T_p
d'une ligne de zéros en haut et d'une colonne de zéros à gauche. - Conseil
- On n'utilisera pas la fonction
somme_max
, mais plutôt la formule de la question 4.
Réponse
def tab_sommes_max(T):
n, m = len(T), len(T[0])
# On ajoute une ligne et une colonne de zéros à T_p
T_p = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n):
for j in range(m):
# Si i ou j est nul alors [0 - 1] envoie
# sur la dernière ligne ou sur la dernière colonne de T_p
# que l'on a construit nulle.
T_p[i][j] = max(T_p[i - 1][j], T_p[i][j - 1]) + T[i][j]
# Facultatif
## On enlève la dernière colonne de zéro
for i in range(n):
T_p[i].pop()
## On enlève la dernière ligne de zéro
T_p.pop()
# Résultat
return T_p
Cette solution est efficace, il n'y a qu'une opération à cout constant par case du tableau.
Variante non efficace
Avec une solution du genre (plusieurs écritures du même algorithme)
def tab_sommes_max(T):
n, m = len(T), len(T[0])
# version avec double boucle explicite
T_p = []
for i in range(n):
ligne = []
for j in range(m):
ligne.append(somme_max(T, i, j))
T_p.append(ligne)
return T_p
Avec des listes en compréhension
def tab_sommes_max(T):
n, m = len(T), len(T[0])
# version avec une boucle explicite et une en compréhension
T_p = []
for i in range(n):
T_p.append([somme_max(T, i, j) for j in range(m)])
return T_p
def tab_sommes_max(T):
# version avec liste en compréhension, double
n, m = len(T), len(T[0])
return [[somme_max(T, i, j) for j in range(m)] for i in range(n)]
Cette solution est très lente ; pour chaque case, de très nombreux calculs redondants sont effectués.