La programmation dynamique

Le calcul récursif naïf de $F(5)$ nécessite de calculer $F(4)$ et $F(3)$ ; mais $F(4)$ recalcule à son tour $F(3)$ et $F(2)$, etc. Ainsi $F(3)$ est calculé deux fois, $F(2)$ trois fois, et le nombre total d'appels croît de manière exponentielle. Les sous-problèmes se chevauchent massivement : c'est le signe qu'une mémorisation sera très bénéfique.

La programmation dynamique est adaptée à un problème si et seulement si celui-ci présente à la fois :

• des sous-problèmes recouvrants (justifiant la mémorisation) ;
• une sous-structure optimale (justifiant la décomposition récursive).

Si les sous-problèmes sont indépendants (non recouvrants), la méthode diviser-pour-régner suffit. Si la sous-structure optimale est absente, aucune récurrence simple ne peut être établie.

Les deux approches ont la même complexité temporelle asymptotique, mais diffèrent par :

• Lisibilité : la mémoïsation reste proche de la définition récursive, donc souvent plus naturelle à écrire.
• Pile d'appels : l'approche ascendante évite la récursivité et donc tout risque de débordement de pile pour de grandes entrées.
• Sous-problèmes calculés : la mémoïsation ne calcule que les sous-problèmes réellement nécessaires, tandis que l'approche ascendante les calcule tous.
• Optimisation mémoire : l'approche ascendante permet parfois de ne conserver que les dernières lignes du tableau.

La version naïve recalcule un nombre exponentiel de fois les mêmes valeurs.

def fibo_naif(n):
    if n <= 1:
        return n
    return fibo_naif(n - 1) + fibo_naif(n - 2)

La version mémoïsée (top-down) stocke chaque résultat dans un dictionnaire :

def fibo_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibo_memo(n - 1, memo) + fibo_memo(n - 2, memo)
    return memo[n]

La version ascendante (bottom-up) remplit un tableau de bas en haut :

def fibo_bottom_up(n):
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

On peut même optimiser la mémoire en ne gardant que les deux dernières valeurs, réduisant l'espace de $O(n)$ à $O(1)$ :

def fibo_optimise(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Les trois dernières versions ont une complexité temporelle $O(n)$, contre une complexité exponentielle pour la version naïve.

On dispose d'un système de pièces (par exemple [1, 2, 5, 10]) et l'on veut rendre une somme $S$ avec le nombre minimal de pièces. Soit $C(s)$ ce nombre minimal pour la somme $s$. La relation de récurrence est :

$$C(s)=1+\underset{p\in \text{pieces},p\le s}{\min }C(s-p),C(0)=0.$$

La solution ascendante remplit un tableau de $0$ à $S$ :

def rendu_monnaie(pieces, somme):
    INFINI = float('inf')
    table = [0] + [INFINI] * somme
    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s and table[s - p] + 1 < table[s]:
                table[s] = table[s - p] + 1
    return table[somme] if table[somme] != INFINI else -1

La complexité est $O(S\times k)$ où $k$ est le nombre de types de pièces. Contrairement à l'algorithme glouton, cette méthode trouve toujours la solution optimale, même pour des systèmes de pièces « non canoniques ».

Pour connaître les pièces effectivement utilisées (et pas seulement leur nombre), on mémorise la dernière pièce ajoutée pour chaque somme :

def rendu_monnaie_detail(pieces, somme):
    INFINI = float('inf')
    table = [0] + [INFINI] * somme
    choix = [None] * (somme + 1)
    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s and table[s - p] + 1 < table[s]:
                table[s] = table[s - p] + 1
                choix[s] = p
    if table[somme] == INFINI:
        return None
    resultat = []
    s = somme
    while s > 0:
        resultat.append(choix[s])
        s -= choix[s]
    return resultat

Étant données deux chaînes $X$ et $Y$, on cherche la longueur de la plus longue sous-séquence commune aux deux. Soit $L(i,j)$ la longueur de la PLSC des préfixes $X[\mathrm{0..}i]$ et $Y[\mathrm{0..}j]$. La récurrence est :

$$L(i,j)=\{\begin{array}{ll}0& \text{si }i=0\text{ ou }j=0,\\ L(i-1,j-1)+1& \text{si }X[i-1]=Y[j-1],\\ \max (L(i-1,j),L(i,j-1))& \text{sinon.}\end{array}$$

def plsc(X, Y):
    n, m = len(X), len(Y)
    table = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if X[i - 1] == Y[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    return table[n][m]

La complexité temporelle et spatiale est $O(n\times m)$.

On dispose de $n$ objets, chacun de poids $w_i$ et de valeur $v_i$, et d'un sac de capacité $C$. On veut maximiser la valeur totale emportée sans dépasser la capacité, chaque objet étant pris ou laissé (0/1). Soit $K(i,c)$ la valeur maximale en considérant les $i$ premiers objets avec une capacité $c$ :

$$K(i,c)=\{\begin{array}{ll}K(i-1,c)& \text{si }{w}_i>c,\\ \max (K(i-1,c),v_i+K(i-1,c-w_i))& \text{sinon.}\end{array}$$

def sac_a_dos(poids, valeurs, capacite):
    n = len(poids)
    table = [[0] * (capacite + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(capacite + 1):
            if poids[i - 1] > c:
                table[i][c] = table[i - 1][c]
            else:
                table[i][c] = max(
                    table[i - 1][c],
                    valeurs[i - 1] + table[i - 1][c - poids[i - 1]]
                )
    return table[n][capacite]

La complexité est $O(n\times C)$ : on parle de complexité pseudo-polynomiale car elle dépend de la valeur numérique $C$ et non seulement de la taille des données.

La méthode diviser-pour-régner découpe également le problème en sous-problèmes, mais ces sous-problèmes sont indépendants (ils ne se chevauchent pas), comme dans le tri fusion. Il n'y a donc rien à mémoriser. La programmation dynamique s'applique précisément lorsque les sous-problèmes se recouvrent, rendant la mémorisation indispensable pour l'efficacité.

Un algorithme glouton fait à chaque étape le choix qui semble localement optimal, sans jamais revenir en arrière ; il est rapide mais ne garantit pas toujours l'optimum global. La programmation dynamique explore l'ensemble des combinaisons pertinentes des sous-problèmes et garantit l'optimum, au prix d'un coût en temps et en mémoire plus élevé. Le rendu de monnaie illustre bien cette différence : l'algorithme glouton échoue sur certains systèmes de pièces là où la programmation dynamique reste correcte.