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 ...