Méthodes de la programmation dynamique : Mémoisation et tabulation

Mémoisation et tabulation sont deux approches couramment utilisées pour optimiser les solutions de programmation dynamique. Elles permettent de résoudre les problèmes plus efficacement en stockant les résultats intermédiaires pour éviter les calculs répétitifs.

La mémoisation est une technique d'optimisation consistant à stocker les résultats de calculs intermédiaires pour éviter de les recalculer plusieurs fois. Elle est souvent utilisée dans les approches descendantes (top-down) de la programmation dynamique.

La mémoisation fait généralement appel à des structures de données telles que des dictionnaires, des tableaux ou des matrices pour stocker les résultats intermédiaires.

Exemple

Le problème de la suite de Fibonacci. Lors de l'utilisation de la récursion simple, le même calcul est effectué plusieurs fois pour des valeurs répétées. En utilisant la mémoisation, on peut stocker les résultats de la suite de Fibonacci déjà calculés dans un dictionnaire ou un tableau, de sorte que les appels récursifs suivants puissent utiliser ces valeurs sans avoir à les recalculer.

def fibonacci(n, cache):
    if n < 2: 
        return 1
    if n not in cache:
        cache[n] = fibonacci(n-1) + fibonacci(n-2)
        
    return cache[n]

La fonction fibonacci(n, cache) prend deux arguments en entrée : n, l'indice du nombre de Fibonacci à calculer, et cache, un dictionnaire utilisé pour stocker les résultats intermédiaires et éviter les calculs redondants.

La première condition (if n < 2) vérifie si l'indice n est inférieur à 2. Dans ce cas, la fonction renvoie 1, car les deux premiers nombres de la suite de Fibonacci (F(0) et F(1)) sont égaux à 1.

La deuxième condition (if n not in cache) vérifie si la valeur de Fibonacci pour l'indice n a déjà été calculée et stockée dans le dictionnaire cache. Si ce n'est pas le cas, la fonction calcule la valeur de Fibonacci pour l'indice n en appelant récursivement la fonction fibonacci pour les indices n-1 et n-2. La somme des deux résultats est stockée dans le dictionnaire cache à la clé n.

Enfin, la fonction renvoie la valeur de Fibonacci pour l'indice n en accédant à la valeur correspondante dans le dictionnaire cache.

La tabulation est une autre technique d'optimisation consistant à construire une table (généralement un tableau ou une matrice) pour stocker les résultats intermédiaires des sous-problèmes. Elle est souvent utilisée dans les approches ascendantes (bottom-up) de la programmation dynamique.

La tabulation résout les sous-problèmes de manière itérative, en commençant par les plus petits et en construisant la solution au problème global.

Exemple

Le problème du sac à dos. On construit une matrice pour stocker les valeurs maximales obtenues pour chaque capacité du sac à dos et chaque objet disponible. En parcourant la matrice, on détermine la valeur maximale qui peut être obtenue pour une capacité donnée du sac à dos en tenant compte des objets disponibles.

Nous parlerons en détail de ce problème plus tard.

Les deux approches ont leurs avantages et leurs inconvénients. La mémoisation est généralement plus simple à mettre en œuvre et peut parfois être plus rapide pour les problèmes dont la structure ne permet pas de résoudre facilement tous les sous-problèmes. La tabulation, en revanche, peut être plus efficace en termes de complexité spatiale et temporelle pour les problèmes dont tous les sous-problèmes doivent être résolus pour obtenir la solution globale.

Un exemple où la mémoisation peut être plus efficace que la tabulation est le problème de recherche du nombre minimum de sauts pour atteindre la fin d'un tableau.

Description du problème

Étant donné un tableau d'entiers non négatifs, chaque entier représentant la longueur maximale d'un saut à partir de cet indice, déterminer le nombre minimum de sauts nécessaires pour atteindre la fin du tableau à partir de l'indice 0.

Mémoisation (approche descendante) :

Dans cette approche, on commence par l'indice 0 et on explore récursivement toutes les possibilités de sauts en utilisant les valeurs du tableau. On stocke les résultats des calculs intermédiaires dans un dictionnaire ou un tableau pour éviter les calculs redondants. Cette méthode permet d'éviter de résoudre les sous-problèmes inutiles.

Dans certains cas, certaines combinaisons de sauts ne sont pas explorées, car elles ne sont pas nécessaires pour trouver la solution optimale. Cela peut entraîner un gain de temps significatif, car on ne calcule que les sous-problèmes pertinents.

def minSauts(tab, index, memo):
    if index == len(tab) - 1:
        return 0

    if index >= len(tab):
        return float('inf')

    if index in memo:
        return memo[index]

    nb_max = tab[index]
    nb_min = float('inf')

    for i in range(1, nb_max + 1):
        sauts = minSauts(tab, index + i, memo)
        nb_min = min(nb_min, sauts + 1)

    memo[index] = nb_min
    return nb_min


tab = [2, 3, 1, 1, 2, 4, 2, 9, 1, 1, 1, 3, 5]
print(minSauts(tab, 0, {}))

La fonction minSauts(tab, index, memo) est une fonction récursive auxiliaire qui prend en entrée la tableau tab, l'indice courant index et un dictionnaire memo pour stocker les résultats intermédiaires. Cette fonction est responsable de calculer et renvoyer le nombre minimum de sauts pour atteindre la fin du tableau à partir de l'indice courant.

La fonction minSauts commence par vérifier si l'indice courant a atteint la fin du tableau. Si c'est le cas, elle renvoie 0, car aucun saut supplémentaire n'est nécessaire.

Si l'indice courant dépasse la fin du tableau, la fonction renvoie une valeur infinie, représentée par float('inf'), car cette situation ne constitue pas une solution valide.

Si l'indice courant est présent dans le dictionnaire memo, cela signifie que le résultat pour cet indice a déjà été calculé précédemment. Dans ce cas, la fonction renvoie simplement la valeur stockée dans memo.

Si l'indice courant n'a pas été traité précédemment, la fonction calcule le nombre minimum de sauts pour atteindre la fin du tableau à partir de cet indice. Pour cela

Tabulation (approche ascendante) :

Dans cette approche, on construit un tableau pour stocker les solutions des sous-problèmes en partant des indices les plus petits. On résout tous les sous-problèmes en parcourant le tableau, puis on combine ces solutions pour obtenir la solution optimale.

Dans le cas du problème de recherche du nombre minimum de sauts, la tabulation résout tous les sous-problèmes, même ceux qui ne sont pas nécessaires pour obtenir la solution optimale. Cela peut entraîner une perte de temps pour les problèmes où tous les sous-problèmes ne sont pas pertinents pour la solution globale.

def minSautsTabu(tab):
    n = len(tab)
    sauts = [float('inf')] * n
    sauts[0] = 0

    for i in range(1, n):
        for j in range(i):
            if j + tab[j] >= i:
                sauts[i] = min(sauts[i], sauts[j] + 1)

    print(sauts)
    return sauts[-1]

tab = [2, 3, 1, 1, 2, 4, 2, 9, 1, 1, 1, 3, 5]
print(minSautsTabu(tab))

La fonction minSautsTabu(tab) est la fonction principale qui prend en entrée le tableau tab et renvoie le nombre minimum de sauts nécessaires pour atteindre la fin du tableau.

La variable n stocke la longueur du tableau tab. Un tableau sauts est initialisé avec des valeurs infinies (float('inf')) pour chaque position. La valeur de sauts[0] est définie sur 0, car aucun saut n'est nécessaire pour atteindre l'indice 0.

Le programme utilise deux boucles imbriquées pour parcourir le tableau et remplir le tableau sauts avec les solutions aux sous-problèmes. La boucle externe (for i in range(1, n)) parcourt les indices du tableau à partir de 1 jusqu'à n - 1.

La boucle interne (for j in range(i)) parcourt les indices précédents de 0 jusqu'à i - 1. Si la somme de l'indice j et de la valeur tab[j] (la longueur maximale du saut à partir de cet indice) est supérieure ou égale à i, cela signifie qu'on peut atteindre l'indice i à partir de l'indice j en un saut.

Si l'indice i peut être atteint à partir de l'indice j, on met à jour la valeur de sauts[i] avec le minimum entre sa valeur actuelle et la somme de sauts[j] + 1. Le + 1 représente le saut de l'indice j à l'indice i.

Les deux boucles imbriquées permettent de remplir progressivement le tableau sauts avec les solutions des sous-problèmes. À la fin de la boucle externe, le tableau sauts contient le nombre minimum de sauts pour atteindre chaque indice du tableau tab.

La valeur de sauts[-1] (la dernière valeur du tableau sauts) représente le nombre minimum de sauts nécessaires pour atteindre la fin du tableau tab. Cette valeur est renvoyée par la fonction minSautsTabu(tab).