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.

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.

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

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

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

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)

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)

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])

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])