Programmation dynamique

Compter tous les chemins possibles dans une grille MxN

Le problème est de compter tous les chemins possibles du haut à gauche (case rouge) au bas à droite (case verte) d’une matrice MxN avec les contraintes suivantes :

  • Nous pouvons se déplacer soit à droite soit en bas, et 
  • Nous ne pouvons pas traverser une cellule noire.


Solution Récursive

def CheminsRecursive(Grille, M, N, i, j):
    if (i >= M or j >= N) or Grille[i][j] == (-1):
        return 0
    if i == M-1 and j == N-1:
        return 1

    Grille[i][j] = CheminsRecursive(
        Grille, M, N, i, j+1)+CheminsRecursive(Grille, M, N, i+1, j)
    return Grille[i][j]

Grille = [[0, 0, 0, 0, 0],
    [0, 0, -1, 0, -1],
    [0, 0, 0, 0, 0],
    [0, -1, 0, -1, 0],
    [0, 0, 0, 0, 0]
    ]
M = 5
N = 5
CheminsRecursive(Grille, M, N,0,0)
print(Grille[0][0])

La complexité temporelle de la solution récursive ci-dessus est exponentielle. Il existe de nombreux sous-problèmes qui se chevauchent.

Programmation Dynamique

Identifiez s'il s'agit d'un problème de programmation dynamique

Ce problème a les deux propriétés : Chevauchement de sous-problèmes et Sous-structure optimale donc c’est un problème de programmation dynamique

  • Chevauchement de sous-problèmes : deux appels au sous-problème (1,1)
  • Sous-structure optimale : le nombre de chemin entre cellule (0,0) et (4,4) est égal au maximum entre ((0,0)->(0,1)+(0,1)->(4,4)) et ((0,0)->(1,0)+(1,0)->(4,4))

Identifiez les variables du problème

Il y’a deux variable dans ce problème :

  • Nombre de chemin de voisin droite
  • Nombre de chemin de voisin en bas

Exprimer clairement la relation de récurrence

Pour calculer le nombre de chemins entre la cellule (i,j) et la cellule (k,l) il faut calculer la somme des chemins allant du voisin droite (i,j+1) et le voisin en bas (i+1,j) d’ou la relation de récurrence :

Nbchemins(i, j)= Nbchemins(i+1, j) + Nbchemins(i, j+1)

Tabulation ou Mémoïsation

C’est l’étape la plus simple, consiste à commencer le calcule à partir du destination (4,4) et remonté dans la matrice jusqu'à la cellule source (0,0)

Mémoïsation

def CheminsMemo(Grille, M, N, i, j):
    if (i >= M or j >= N) or Grille[i][j] == (-1):
        return 0
    if i == M-1 and j == N-1:
        return 1

    if Grille[i][j] > 0:
        return Grille[i][j]

    Grille[i][j] = CheminsMemo(
        Grille, M, N, i, j+1)+CheminsMemo(Grille, M, N, i+1, j)
    return Grille[i][j]


Grille = [[0, 0, 0, 0, 0],
    [0, 0, -1, 0, -1],
    [0, 0, 0, 0, 0],
    [0, -1, 0, -1, 0],
    [0, 0, 0, 0, 0]
    ]
M = 5
N = 5
CheminsMemo(Grille, M, N,0,0)
print(Grille[0][0])
Complexité la complexité de cet algorithme est O(M*N) ou M= Nombre de lignes et N=Nombre de colonnes

Tabulation

Etape 1 : consiste à initialiser la matrice et le calcule : mettre 0 dans la case (4,4)

Etape 2 : 

Etape 2 : 

Etape 2 : 

Etape 2 : 

 ... 
 Dernières étape :  calculer le nombre de chemin de la cellule (0,0) et retourner le résultat


def CheminsDynamique(Grille, M, N):
    Grille[M-1][N-1] = 1
    for i in range(M-1, -1, -1):
        for j in range(N-1, -1, -1):

            # la case n'est pas noir
            if Grille[i][j] > (-1):
                # à l'interieur du matrice (sans les nornes)
                if i < M-1 and j < N-1:
                    # si les deux cases voisines sont valides
                    if Grille[i+1][j] > (-1) and Grille[i][j+1] > (-1):
                        Grille[i][j] = Grille[i+1][j]+Grille[i][j+1]
                    elif Grille[i+1][j] > (-1):
                        Grille[i][j] = Grille[i+1][j]
                    else:
                        Grille[i][j] = Grille[i][j+1]

                # bornne en bas
                elif i < M-1:
                    if Grille[i+1][j] > (-1):
                        Grille[i][j] = Grille[i+1][j]

                # bornne droite
                elif j < N-1:
                    if Grille[i][j+1] > (-1):
                        Grille[i][j] = Grille[i][j+1]


Grille = [[0, 0, 0, 0, 0],
          [0, 0, -1, 0, -1],
          [0, 0, 0, 0, 0],
          [0, -1, 0, -1, 0],
          [0, 0, 0, 0, 0]
          ]
M = 5
N = 5
CheminsDynamique(Grille, M, N)
print(Grille[0][0])
Complexité la complexité de cet algorithme est O(M*N) ou M= Nombre de lignes et N=Nombre de colonnes

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :