Aller au contenu

TP - Parcours de Tableaux 2D☘

Ce TP est partagé en plusieurs parties indépendantes. Dans chacune des parties, il faudra programmer un algorithme de parcours d'un tableau en deux dimensions.

Il est donc conseillé de se munir d'un cahier et d'un crayon afin de tracer des schémas...

Dans le dossier [NSI], commencez par créer le dossier [E03-Prog_Dynamique].

TPE03.51 - Nombre de chemins☘

Téléchargez le fichier « à trous » : TPE03.11.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le répertoire [E03-Prog_Dynamique].

Le problème☘

Dans une grille de dimensions n × m, on part de la cellule (0, 0) et on se rend dans la cellule (n-1, m-1). Les seuls déplacements autorisés sont les déplacements vers la droite et vers le bas.

Par exemple, dans une grille 4 × 6, un chemin de (0, 0) à (3, 5) peut être :

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)
(1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5)
(2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5)
(3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5)

L'objectif est de déterminer le nombre de chemins de (0, 0) à (n-1, m-1).

Un cas particulier☘

Déterminez « à la main » le nombre de chemins possibles dans une grille comportant trois lignes et quatre colonnes.

Résolution du problème☘

On construit une matrice de mémorisation nommée chemins, de dimensions n \times m telle que chemins[i][j] contienne, au final le nombre de chemins permettant d'aller de la case (0, 0) à la case (i, j).
Au départ, les valeurs sont toutes initialisées à 0 :

12
chemins = [ [0  for j in range(m)] for i in range(n) ]

Vous allez commencer par chercher une relation de récurrence qui permette de remplir la matrice chemins, puis vous allez programmer une version itérative « Bottom-Up » puis une version récursive « Top-Down » de résolution de ce problème.

  1. Quelle est la valeur de chemin[0][0] ?
  2. Comment compléter la première ligne et la première colonne de la matrice chemins ?
  3. Pour i \neq 0 et j \neq 0, quelle(s) case(s) doit-on traverser juste avant d'arriver à la case (i, j) ?
  4. En déduire comment calculer la valeur de chemin[i][j].

  5. Complétez la définition itérative de la fonction nb_chemins().

    Code à compléter
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    def nb_chemins(n, m):
    """
    n, m - int, entiers strictement positifs
    Sortie: int - Dernière case d'un tableau de n tableaux ayant chacun m éléments
            La case (i, j) contient le nombre de chemins allant de (0, 0) à (i, j)
            Les seuls déplacements autorisés sont vers la droite et vers le bas
            Version itérative "Bottom-Up"
    >>> nb_chemins(3, 4)
    10
    >>> nb_chemins(30, 40)
    13750991318793417920
    """
    chemins = [ [0  for j in range(m)] for i in range(n) ]
    pass

  6. Que pouvez-vous dire de la complexité spatiale et de la complexité temporelle de votre algorithme ?

  7. Complétez la définition récursive de la fonction nb_routes(), qui est une « sous-fonction » de la fonction nb_chemins_rec().

    Code à compléter
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    def nb_chemins_rec(n, m):
    """
    n, m - int, entiers strictement positifs
    Sortie: int - Dernière case d'un tableau de n tableaux ayant chacun m éléments
            La case (i, j) contient le nombre de chemins allant de (0, 0) à (i, j)
            Les seuls déplacements autorisés sont vers la droite et vers le bas
            Version récursive "Top-Down"
    >>> nb_chemins_rec(3, 4)
    10
    >>> nb_chemins_rec(30, 40)
    13750991318793417920
    """
    chemins = [ [0  for j in range(m)] for i in range(n) ]
    chemins[0][0] = 1

    def nb_routes(i, j):
        pass

    return pass

TPE03.52 - Plus court chemin dans une matrice☘

Téléchargez le deuxième fichier « à trous » : TPE03.12.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le répertoire [E03-Prog_Dynamique].

Les fonctions min() et max() de Python sont autorisées dans ce TP.

Le problème☘

Dans une grille de dimensions n × m, dont chaque case contient un nombre, on part de la cellule (0, 0) et on se rend dans la cellule (n-1, m-1). Les seuls déplacements autorisés sont les déplacements vers la droite et vers le bas. La contrainte étant, cette fois-ci, d'emprunter le chemin pour lequel la somme des nombres rencontrés est la plus petite.

Par exemple, dans le tableau suivant :

0 0 8 3 2 5
2 4 2 7 7 1
8 3 5 1 8 7
6 8 3 4 4 9
4 4 0 1 3 2

Le chemin optimal a pour somme 20 :

0 0 8 3 2 5
2 4 2 7 7 1
8 3 5 1 8 7
6 8 3 4 4 9
4 4 0 1 3 2

Un exemple interactif☘

Une fois que vous aurez cliqué sur le bouton [Nouveau Jeu], vous devrez parcourir un donjon. Dans chaque salle, un monstre demande un « péage » pour pouvoir traverser et vous rendre dans la salle de droite ou bien dans celle du bas.
Attention, choisissez bien car vous ne pourrez pas revenir en arrière...

Nombre total de pièces dépensées :

Un cas particulier « à la main »☘

Déterminez « à la main » le chemin optimal pour parcourir le tableau suivant :

4 2 7 4 2 7
4 8 8 1 4 7
4 1 4 6 8 4
8 1 2 5 2 6
1 1 9 1 3 7

Résolution « gloutonne » du problème☘

Une manière d'envisager la résolution du problème est de se dire :

« Depuis chaque case, je vais vers la voisine dont la valeur est la plus petite. »

  1. Complétez la définition de la fonction parcours_mini_glouton() qui prend en paramètre une matrice tab de nombres et qui renvoie, sous la forme d'un tableau, la liste des coordonnées des cases à parcourir pour aller de tab[0][0] à tab[n-1][m-1] en appliquant l'algorithme ci-dessus.

    Code à compléter
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def parcours_mini_glouton(tab):
    """
    tab - list, Tableau de tableaux contenant des nombres
    Sortie: list - Tableau des couples de coordonnées à parcourir pour
            aller de la première à la dernière case du tableau tab
            en appliquant un principe glouton pour minimiser la somme
            totale des cases parcourues
    >>> tab = [[2, 2, 4, 4, 9, 0], [7, 0, 2, 2, 0, 2], [0, 5, 7, 3, 5, 2], [2, 6, 1, 0, 4, 7], [5, 2, 0, 6, 6, 9]]
    >>> parcours_mini_glouton(tab)
    [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
    """
    pass

  2. Testez cette fonction avec la matrice ci-dessous :

    Matrice de test

    1
    tab = [[0, 0, 8, 3, 2, 5], [2, 4, 2, 7, 7, 1], [8, 3, 5, 1, 8, 7], [6, 8, 3, 4, 4, 9], [4, 4, 0, 1, 3, 2]]

  3. Cette méthode vous semble-t-elle optimale ? Appelez l'enseignant et justifiez.

Résolution « dynamique » du problème☘

  1. Complétez la définition de la fonction genere_tab_2D() qui renvoie un tableau de n tableaux contenant chacun m éléments. Ces éléments sont des entiers aléatoires compris entre les paramètres borne_inf et borne_sup passés en paramètres.

    Code à compléter
    1
2
3
4
5
6
7
8
    def genere_tab_2D(n, m, borne_inf, borne_sup):
    """
    n, m - int, entiers strictement positifs
    borne_inf, borne_sup - int, entiers tels que borne_inf < borne_sup
    Sortie: list - Tableau de n tableaux ayant m éléments
            Chaque élément est un entier aléatoire compris entre borne_inf et borne_sup
    """
    pass

  2. La fonction sommes_parcours() va prendre en paramètre une matrice tab de nombre et va renvoyer une matrice memo de mêmes dimensions. Chaque case (i, j) de la matrice memo devra contenir la plus petite somme pour un chemin allant de tab[0][0] à tab[i][j].

    1. Par quelle valeur initialiser chacune des cases de la matrice memo ?
    2. Quelle est la valeur de memo[0][0] ?
    3. Comment compléter la première ligne et la première colonne de la matrice memo ?
    4. Pour i \neq 0 et j \neq 0, comment calculer la valeur de memo[i][j].

    5. Complétez la définition itérative de la fonction sommes_parcours().

      Code à compléter
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
      def sommes_parcours(tab):
    """
    tab - list, Tableau de tableaux contenant des nombres
    Sortie: list - Tableau de tableaux ayant les mêmes dimensions que tab
            Chaque case (i, j) contient la plus petite somme pour un chemin
            allant de tab[0][0] à tab[i][j]
            Version itérative "Bottom-Up"
    >>> tab = [[2, 2, 4, 4, 9, 0], [7, 0, 2, 2, 0, 2], [0, 5, 7, 3, 5, 2], [2, 6, 1, 0, 4, 7], [5, 2, 0, 6, 6, 9]]
    >>> sommes_parcours(tab)
    [[2, 4, 8, 12, 21, 21], [9, 4, 6, 8, 8, 10], [9, 9, 13, 11, 13, 12], [11, 15, 14, 11, 15, 19], [16, 17, 14, 17, 21, 28]]
    """
    pass

  3. A partir de ce tableau de sommes de parcours, il est possible de « remonter » la piste pour obtenir les coordonnées du parcours à réaliser. Complétez la définition de la fonction parcours_mini().

    Code à compléter
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def parcours_mini(memo):
    """
    memo - list, Tableau de tableaux contenant des sommes de parcours minimisées
    Sortie: list - Tableau des couples de coordonnées à parcourir pour
            aller de la première à la dernière case du tableau tab
            en empruntant la somme minimale
    >>> memo = [[2, 4, 8, 12, 21, 21], [9, 4, 6, 8, 8, 10], [9, 9, 13, 11, 13, 12], [11, 15, 14, 11, 15, 19], [16, 17, 14, 17, 21, 28]]
    >>> parcours_mini(memo)
    [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
    """
    pass

  4. Testez cette fonction avec la matrice ci-dessous :

    Matrice de test

    1
    tab = [[0, 0, 8, 3, 2, 5], [2, 4, 2, 7, 7, 1], [8, 3, 5, 1, 8, 7], [6, 8, 3, 4, 4, 9], [4, 4, 0, 1, 3, 2]]

  5. Ajoutez des tests dans le programme principal à partir de tableaux générés aléatoirement à l'aide de la fonction genere_tab_2D().

  6. Cette méthode vous semble-t-elle optimale ? Appelez l'enseignant et justifiez.

  7. Complétez la définition de la fonction sommes_parcours_rec(), qui fait appel à une sous-fonction récursive sommes(). Cette sous-fonction prend en paramètres deux entiers i et j et renvoie la valeur de la case memo[i][j], où memo est une matrice initialisée dans sommes_parcours_rec() puis renvoyée par cette dernière.

    Code à compléter
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def sommes_parcours_rec(tab):
    """
    tab - list, Tableau de tableaux contenant des nombres
    Sortie: list - Tableau de tableaux ayant les mêmes dimensions que tab
            Chaque case (i, j) contient la plus petite somme pour un chemin
            allant de tab[0][0] à tab[i][j]
            Version récursive "Top-Down"
    >>> tab = [[2, 2, 4, 4, 9, 0], [7, 0, 2, 2, 0, 2], [0, 5, 7, 3, 5, 2], [2, 6, 1, 0, 4, 7], [5, 2, 0, 6, 6, 9]]
    >>> sommes_parcours_rec(tab)
    [[2, 4, 8, 12, 21, 21], [9, 4, 6, 8, 8, 10], [9, 9, 13, 11, 13, 12], [11, 15, 14, 11, 15, 19], [16, 17, 14, 17, 21, 28]]
    """
    pass
    Une piste

    Voici un code à trou un peu plus complet : 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    def sommes_parcours_rec(tab):
    """
    tab - list, Tableau de tableaux contenant des nombres
    Sortie: list - Tableau de tableaux ayant les mêmes dimensions que tab
            Chaque case (i, j) contient la plus petite somme pour un chemin
            allant de tab[0][0] à tab[i][j]
            Version récursive "Top-Down"
    >>> tab = [[2, 2, 4, 4, 9, 0], [7, 0, 2, 2, 0, 2], [0, 5, 7, 3, 5, 2], [2, 6, 1, 0, 4, 7], [5, 2, 0, 6, 6, 9]]
    >>> sommes_parcours_rec(tab)
    [[2, 4, 8, 12, 21, 21], [9, 4, 6, 8, 8, 10], [9, 9, 13, 11, 13, 12], [11, 15, 14, 11, 15, 19], [16, 17, 14, 17, 21, 28]]
    """
    n = ...
    m = ...
    memo = ...
    memo[0][0] = ...

    def sommes(i, j):
        pass

    sommes(..., ...)
    return ...