Les bases de la programmation dynamique

5.1 Définition de la programmation dynamique.

Programmation dynamique (Dynamic Programming, DP) — c'est une méthode d'optimisation utilisée pour résoudre des problèmes complexes en les divisant en sous-problèmes plus simples. La programmation dynamique est utilisée efficacement pour les problèmes qui peuvent être divisés en sous-problèmes qui se chevauchent avec une structure optimale.

Principes de fonctionnement :

1. Sous-structure optimale :

Un problème a une sous-structure optimale si sa solution optimale peut être construite à partir des solutions optimales de ses sous-problèmes. Cela signifie que tu peux résoudre un grand problème en résolvant plusieurs plus petits.

2. Sous-problèmes qui se chevauchent :

Un problème a des sous-problèmes qui se chevauchent si ses sous-problèmes se répètent plusieurs fois dans le processus de résolution. La programmation dynamique résout efficacement ces problèmes en mémorisant les résultats des sous-problèmes déjà résolus (mémorisation).

3. Mémorisation et tabulation :

Mémorisation (de haut en bas) : Approche récursive où les résultats des sous-problèmes sont stockés en mémoire pour éviter les calculs redondants.

Tabulation (de bas en haut) : Approche itérative où les résultats des sous-problèmes sont calculés et stockés dans une table (généralement un tableau) et utilisés pour calculer le résultat final.

Exemples de problèmes résolus par programmation dynamique

5.2 Problème du sac à dos.

Problème :

Il y a un ensemble d'objets, chacun avec un poids et une valeur. Il faut choisir des objets pour un sac à dos avec une capacité limitée afin de maximiser la valeur totale.

Important ! Contrairement à un problème similaire qui se résout bien avec un algorithme glouton, ici les objets ne peuvent pas être divisés.

Solution :

Une table est créée, où les lignes correspondent aux objets et les colonnes à la capacité possible du sac à dos. La valeur dans une cellule représente la valeur maximale pour un certain nombre d'objets et de capacité.

Complexité temporelle : O(n * W), où n est le nombre d'objets et W est la capacité du sac à dos.

Exemple de code en Python :

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 Problème du plus court chemin

Problème :

Trouver les plus courts chemins entre toutes les paires de sommets d'un graphe pondéré.

Solution :

Une table est utilisée, où les lignes et les colonnes correspondent aux sommets du graphe. La valeur dans une cellule représente la distance la plus courte entre deux sommets.

Complexité temporelle : O(V^3), où V est le nombre de sommets

Exemple de code en Python :

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 Comparaison de la programmation dynamique avec d'autres méthodes.

Comparaison avec la méthode de force brute (brute force) :

Complexité temporelle :

• Force brute : a souvent une complexité temporelle exponentielle (par exemple, O(2^n) pour le problème de Fibonacci).
• Programmation dynamique : réduit la complexité temporelle à polynomiale (par exemple, O(n) pour le problème de Fibonacci).

Complexité spatiale :

• Force brute : peut utiliser moins de mémoire, mais les coûts en temps sont élevés.
• Programmation dynamique : peut utiliser plus de mémoire pour stocker les résultats intermédiaires (par exemple, O(n) pour le problème de Fibonacci avec mémorisation), mais gagne en temps.

Comparaison avec la méthode des algorithmes gloutons (greedy algorithms) :

Optimalité :

• Algorithmes gloutons : ne trouvent pas toujours la solution optimale globale, mais fonctionnent plus rapidement et sont plus faciles à implémenter.
• Programmation dynamique : trouve la solution optimale globale, mais nécessite plus de ressources computationnelles.

Exemples de problèmes :

• Algorithmes gloutons : problème du sac à dos fractionnaire (fractional knapsack), arbre de recouvrement minimal (MST).
• Programmation dynamique : problème du sac à dos (entier), plus longue sous-séquence commune (LCS).