Aller au contenu

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
🐍 Script Python
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

🐍 Script Python
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 :

🐍 Console Python
>>> somme_max(T, 2, 3)
16

Dans le cas d'un tableau de n lignes et m colonnes, l'appel sera :

🐍 Console Python
>>> somme_max(T, n - 1, m - 1)
16

On peut aussi faire une fonction qui suppose que T est non vide et bien formé.

🐍 Script Python
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
🐍 Script Python
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)

🐍 Script Python
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
🐍 Script Python
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
🐍 Script Python
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.