Chapitre 16 : Programmation dynamique.

Introduction :

La programmation dynamique repose sur une idée simple mais puissante : pourquoi recalculer un résultat si on l'a déjà trouvé ?

En décomposant un problème complexe en sous-problèmes plus simples, on peut mémoriser les solutions déjà obtenues et les réutiliser. Cela permet d'éviter des calculs redondants et d'améliorer l'efficacité des algorithmes.

1. La programmation dynamique :

A copier dans le cahier.

La programmation dynamique est une méthode de conception d’algorithmes utilisée pour résoudre efficacement des problèmes complexes en les décomposant en sous-problèmes qui se répètent. Elle repose sur l’idée de mémoriser les résultats des sous-problèmes déjà résolus afin d’éviter de refaire plusieurs fois les mêmes calculs.

La programmation dynamique est souvent utilisée pour optimiser des calculs répétitifs, par exemple dans la suite de Fibonacci, les problèmes de plus court chemin (algorithme de Dijkstra), ou les problèmes de sac à dos (knapsack).

2. Etapes de la programmation dynamique :

Identification des sous-problèmes : le problème global peut être découpé en sous-problèmes plus petits et qui se recoupent.
Mémorisation : les solutions aux sous-problèmes sont stockées (dans un tableau ou un dictionnaire).
Réutilisation : lorsqu’un sous-problème réapparaît, on utilise directement la solution mémorisée.
Construction de la solution : la réponse finale est obtenue en combinant les solutions des sous-problèmes.

3. Activité : Suite de Fibonacci — itératif, récursif et dynamique

On considère la suite de Fibonacci définie à l'aide d'une suite \(F\) définie ainsi :

\(F(0)=0\)
\(F(1)=1\)
Pour tout \(n \ge 2\) : \(F(n)=F(n-1)+F(n-2)\)

Programmer la fonction fibo_itera(n) (version itérative).
Programmer la fonction fibo_recur(n) (version récursive simple).
Programmer la fonction fibo_recur_dyna(n) (récursif avec mémoïsation).
Programmer la fonction fibo_itera_dyna(n) (itératif avec tableau dynamique).

Exemples :

F(0)=0, F(1)=1, F(2)=1, F(5)=5, F(10)=55

def fibo_itera(n): """Version itérative: renvoie F(n).""" if n == 0: return ... if n == 1: return ... # on itère en gardant F(k-2) et F(k-1) a, b = 0, 1 for _ in range(...): # compléter la borne a, b = b, a + b return ... def fibo_recur(n): """Version récursive simple: renvoie F(n).""" if n == 0: return ... if n == 1: return ... return ... + ... def fibo_recur_dyna(n, memo=None): """Récursif + mémoïsation (dynamique top-down).""" if memo is None: memo = {} if n in memo: return memo[n] if n == 0: memo[0] = ... return ... if n == 1: memo[1] = ... return ... memo[n] = ... + ... # appels mémoïsés pour n-1 et n-2 return memo[n] def fibo_itera_dyna(n): """Itératif avec tableau (dynamique bottom-up).""" # construire une liste dp telle que dp[k] = F(k) dp = [0] * (... ) # longueur n+1 if n >= 1: dp[1] = 1 for k in range(2, ...): dp[k] = dp[k-1] + dp[k-2] return dp[...] n = 5 print(f"fibo_itera({n}) renvoie {fibo_itera(n)}.") print(f"fibo_recur({n}) renvoie {fibo_recur(n)}.") print(f"fibo_recur_dyna({n}) renvoie {fibo_recur_dyna(n)}.") print(f"fibo_itera_dyna({n}) renvoie {fibo_itera_dyna(n)}.")

Tests :

Affichage :

Console:

>>>

4. Exercice : Coût minimal dans une grille (programmation dynamique)

On dispose d’une grille rectangulaire de coûts (entiers positifs). On part de la case en haut à gauche et on veut atteindre la case en bas à droite.

À chaque étape, on peut se déplacer uniquement vers la droite ou vers le bas. Le coût d’un chemin est la somme des coûts des cases traversées (départ et arrivée inclus).

Objectif : écrire une fonction cout_chemin_min(grille, affiche_dp = False) qui renvoie le coût minimal pour aller du coin haut-gauche au coin bas-droit.

Idée (raisonnement dynamique) :

La case de départ « hérite » simplement de son propre coût.
Sur la première colonne, on ne peut venir que d’en haut : on additionne donc les coûts en descendant.
Sur la première ligne, on ne peut venir que de la gauche : on additionne donc les coûts en avançant.
Pour toute autre case, on arrive soit de la case du haut, soit de la case de gauche : on choisit le meilleur des deux chemins déjà calculés, puis on ajoute le coût de la case actuelle.

Exemples :

grille1 = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
# coût minimal attendu = 7

grille2 = [[5]]  # coût = 5

Un paramètre affiche_dp qui vaut par défaut False permettra de visualiser les deux grilles (matrices) si on le souhaite.

def cout_chemin_min(grille, affiche_dp = False): """ Renvoie le coût minimal pour aller de (0,0) à (n-1,m-1) en ne se déplaçant que vers la droite ou vers le bas. Paramètre: - grille : liste de listes d'entiers positifs (n x m, n>=1, m>=1) """ n = len(grille) m = len(grille[0]) # Table dp : dp[i][j] = coût minimal pour atteindre (i,j) dp = [[0 for _ in range(m)] for _ in range(n)] # Case de départ dp[0][0] = ... # coût de la case (0,0) # Première colonne : ne peut venir que d'en haut for i in range(1, n): dp[i][0] = ... # cumuler avec la case au-dessus # Première ligne : ne peut venir que de la gauche for j in range(1, m): dp[0][j] = ... # cumuler avec la case à gauche # Reste de la grille : meilleur des deux chemins (haut/gauche) + coût actuel for i in range(1, n): for j in range(1, m): dp[i][j] = ... if affiche_dp: print("Matrice initiale : grille") for ligne in grille: print(" ".join(f"{elem:3}" for elem in ligne)) print("") print("Matrice dp :") for ligne in dp: print(" ".join(f"{elem:3}" for elem in ligne)) print("") return ... # valeur en bas à droite # --- Grille de démonstration 6x6 (pour visualiser le résultat) --- grille_demo = [ [1, 3, 1, 2, 8, 2], [2, 1, 4, 1, 2, 3], [3, 2, 1, 5, 1, 4], [4, 3, 2, 1, 3, 1], [5, 1, 1, 1, 1, 2], [2, 2, 2, 2, 2, 1], ] print(cout_chemin_min(grille_demo, True))

Tests :

Affichage :

Console:

>>>

5. Exercice : Nombre de chemins dans une grille avec obstacles (programmation dynamique)

On modélise un plateau par une grille de 0 et 1 :

0 : case libre (on peut la traverser)
1 : obstacle (on ne peut pas la traverser)

On part du coin haut-gauche de la grille et on veut atteindre le coin bas-droit.

À chaque étape on peut se déplacer uniquement vers la droite ou vers le bas.

Objectif : écrire une fonction nombre_chemins(grille, affiche_dp=False) qui renvoie le nombre de chemins possibles de la case de départ à la case d’arrivée, en évitant les obstacles.

Idée (raisonnement dynamique) :

Si une case est un obstacle, le nombre de chemins jusqu’à cette case est 0.
La case de départ vaut 1 s’il n’y a pas d’obstacle dessus.
Sur la première ligne : on ne peut venir que de gauche (et seulement si toutes les cases précédentes sont libres).
Sur la première colonne : on ne peut venir que d’en haut (et seulement si toutes les cases au-dessus sont libres).
Ailleurs : le nombre de chemins pour atteindre une case libre est la somme des chemins venant de la case du haut et de la case de gauche.

Exemples :

grilleA = [
  [0, 0, 0],
  [0, 0, 0]
]
# 2 lignes, 3 colonnes, pas d'obstacle → il n'existe qu'un seul chemin par la première ligne
# puis tout droit vers le bas, OU bien tout droit en bas puis à droite → ici le résultat est 3.

grilleB = [
  [0, 1],
  [0, 0]
]
# Un obstacle en (0,1) (première ligne, deuxième colonne) bloque un des chemins.

Le paramètre affiche_dp permettra, s’il vaut True, d’afficher la grille et la matrice des nombres de chemins calculée.

def nombre_chemins(grille, affiche_dp=False): """ Renvoie le nombre de chemins du coin (0,0) au coin (n-1,m-1) en ne se déplaçant que vers la droite ou vers le bas, en évitant les obstacles (1). Paramètre: - grille : liste de listes d'entiers 0/1 (0=libre, 1=obstacle), taille n x m (n>=1, m>=1) - affiche_dp : si True, affiche la grille et la matrice DP """ n = len(grille) m = len(grille[0]) # Matrice DP : dp[i][j] = nb de chemins pour atteindre (i,j) dp = [[0 for _ in range(m)] for _ in range(n)] # Case de départ if grille[0][0] == 0: # 1 chemin possible de la case départ à la case départ dp[0][0] = 1 else: return 0 # aucun chemin possible # Première colonne : ne peut venir que d'en haut (si pas d'obstacle) for i in range(1, n): if grille[i][0] == 1: dp[i][0] = ... else: dp[i][0] = ... # si au-dessus 0, ça propage 0, sinon 1 # Première ligne : ne peut venir que de la gauche (si pas d'obstacle) for j in range(1, m): if grille[0][j] == 1: dp[0][j] = ... else: dp[0][j] = ... # Reste de la grille : somme (haut + gauche) si la case est libre for i in range(1, n): for j in range(1, m): if grille[i][j] == 1: dp[i][j] = ... else: dp[i][j] = ... if affiche_dp: print("Grille (0=libre, 1=obstacle) :") for ligne in grille: print(" ".join(str(x) for x in ligne)) print("") print("Matrice dp (nombre de chemins jusqu à la case) :") for ligne in dp: print(" ".join(f"{x:3}" for x in ligne)) print("") return ... # --- Grille de démonstration 6x6 (pour visualiser le résultat) --- # 0 = libre, 1 = obstacle grille_demo = [ [0,0,0,0,0,0], [0,1,0,0,1,0], [0,0,0,1,0,0], [1,0,0,0,0,0], [0,0,1,0,1,0], [0,0,0,0,0,0], ] print(nombre_chemins(grille_demo, True))

Tests :

Affichage :

Console:

>>>

6. Exercice : Sac à dos 0/1 (programmation dynamique)

Vous préparez un sac de randonnée. Chaque objet possède un poids (combien il pèse) et une valeur (son utilité/intérêt). Le sac a une capacité maximale : la somme des poids des objets choisis ne doit pas dépasser cette capacité. Chaque objet peut être pris au plus une fois.

Votre sac a une capacité maximale capacite (même unité que les poids). Vous ne pouvez pas dépasser cette capacité et vous ne pouvez prendre chaque objet au plus une fois (problème du sac à dos 0/1).

Objectif : écrire une fonction valeur_max_sac(liste_poids, liste_valeurs, capacite, affiche_dp=False) qui renvoie la valeur totale maximale transportable sans dépasser la capacité.

liste_poids[i] : le poids de l’objet i (par exemple en kg ou en centaines de grammes).
liste_valeurs[i] : l’utilité (ou score) de l’objet i. Plus la valeur est grande, plus l’objet est intéressant à emporter.

Idée de l'algorithme en programmation dynamique:

On raisonne par états : pour chaque nombre d’objets considérés (de 0 à n) et pour chaque capacité intermédiaire (de 0 à capacite), on mémorise la meilleure valeur atteignable.
Tableau de décision : chaque case répond à la question « en utilisant seulement les i premiers objets et en se limitant à une capacité w, quelle valeur maximale peut-on obtenir ? ».
Transition :
- Si l’objet courant est trop lourd pour w, on ne peut pas l’ajouter : la meilleure valeur reste celle obtenue sans cet objet.
- Sinon, on compare deux choix :
  - ne pas prendre l’objet → la valeur reste celle du meilleur choix précédent à capacité w ;
  - prendre l’objet → on ajoute sa valeur à la meilleure valeur obtenue avec la capacité w – poids_objet en ne considérant que les objets précédents.
  On retient le meilleur des deux choix.
Initialisation : avec 0 objet ou capacité 0, la meilleure valeur est 0.
Résultat : la case finale de la table correspond à « tous les objets considérés » et « capacité maximale » ; c’est la valeur optimale recherchée.
Affichage (optionnel) : si affiche_dp=True, afficher la table pour visualiser la construction de la solution.

def valeur_max_sac(liste_poids, liste_valeurs, capacite, affiche_dp=False): """ Renvoie la valeur maximale transportable sans dépasser 'capacite'. - liste_poids : liste d'entiers (poids des objets) - liste_valeurs : liste d'entiers (utilités/valeurs des objets, même ordre que 'poids') - capacite : entier (capacité maximale du sac) - affiche_dp : si True, affiche la table DP (lignes = objets 0..n, colonnes = 0..capacite) """ assert len(liste_poids) == len(liste_valeurs), "les deux listes doivent être de même taille" n = len(liste_poids) # dp[i][capacite_testee] : valeur max en utilisant les i premiers objets avec une capacité capacite_testee dp = [[0 for _ in range(capacite + 1)] for _ in range(n + 1)] for i in range(1, n + 1): i_eme_poids = liste_poids[i - 1] # poids de l'objet i (indexé i-1) i_eme_valeur = liste_valeurs[i - 1] # valeur de l'objet i for capacite_testee in range(0, capacite + 1): if i_eme_poids > capacite_testee: dp[i][capacite_testee] = ... # trop lourd : on ne prend pas else: dp[i][capacite_testee] = ... if affiche_dp: print("Table DP (lignes = objets 0..n, colonnes = capacités 0..C) :") for ligne in dp: print(" ".join(f"{v:3}" for v in ligne)) print("") return ... # --- Démo (optionnelle) --- poids_demo = [2, 3, 4, 5, 9, 7] valeurs_demo = [3, 4, 5, 8, 10, 9] cap_demo = 12 print(valeur_max_sac(poids_demo, valeurs_demo, cap_demo, True))

Tests :

Affichage :

Console:

>>>

7. Exercice type bac :

Cet exercice porte sur l’algorithmique, les listes et la programmation dynamique.

Dans un jeu de stratégie, la carte est un carré de \(n \times n\) cases, où \(n\) est un entier strictement positif. Certaines cases sont dites constructibles, d’autres ne le sont pas. Toutes les cartes contiennent au moins une case constructible.

Une telle carte est représentée en Python par une liste de listes. Les cases constructibles sont représentées par des cellules contenant la valeur 1, celles qui sont non constructibles par des cellules contenant la valeur 0.

On fournit ci-dessous la représentation d’une carte pour laquelle n est égal à 5 :

carte_A = [
    [0, 0, 1, 1, 1],
    [1, 1, 0, 1, 1],
    [0, 1, 1, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 1, 1, 0],
]

Une base dans la carte est un carré formé de cases constructibles. On cherche à construire la plus grande base possible, ce qui revient donc à trouver un plus grand carré, inclus dans la carte, ne contenant que des valeurs 1. Il peut en exister plusieurs.

Dans la carte précédente, la plus grande base possible est un carré de 3 cases de côté, son coin supérieur gauche est la cellule carte_A[2][1], de coordonnées (2,1). On dit que cette base est issue de la cellule carte_A[2][1] et que sa taille vaut 3.

Partie A

On considère la carte_B donnée ci-dessous.

carte_B = [
    [1, 1, 1, 1],
    [0, 1, 1, 1],
    [0, 1, 1, 1],
    [1, 0, 1, 1],
]

Donner la taille de la plus grande base carrée ainsi que les coordonnées de la cellule dont elle est issue.

Afin de répondre à ce problème, on envisage une recherche exhaustive de solution. Cela signifie que l’on teste tous les carrés inclus dans la carte initiale afin de vérifier s’ils ne contiennent que des cases constructibles. On considère dans un premier temps le carré de taille \(n\), puis les quatre carrés de taille \(n - 1\) et ainsi de suite jusqu’aux carrés de taille 1. Dès que l’on trouve un carré constructible, on renvoie sa taille et les coordonnées de son coin supérieur gauche.

On considère un entier taille strictement positif. Déterminer la somme des valeurs de toutes les cellules d’un carré constructible de taille taille cases de côté.

La fonction est_constructible prend en paramètres :

la liste de listes carte représentant la carte ;
les entiers i_coin et j_coin indiquant les coordonnées de la cellule dont est issu le carré considéré ;
l’entier positif taille indiquant la taille de ce carré.

Cette fonction renvoie True si le carré décrit par les paramètres est constructible, False dans le cas contraire.

Cette fonction n’a pas besoin de vérifier que les coordonnées et la taille passées en paramètres définissent toujours un carré valide dont toutes les cases sont incluses dans la carte. On suppose que c’est toujours le cas.

Compléter le code de la fonction est_constructible.

def est_constructible(carte, i_coin, j_coin, taille):
    s = 0
    for i in range(i_coin, i_coin + taille):
        for j in range(..., ...):
            s = ...
    ... # Plusieurs lignes possibles

La fonction plus_grande_base_exhaustive prend en paramètre la liste de listes carte représentant une carte et renvoie un triplet (taille, i, j) dans lequel taille est la taille d’un carré constructible de taille maximale et i et j sont les coordonnées de son coin supérieur gauche.

Cette fonction utilise la méthode exhaustive décrite plus haut.

On rappelle qu’une carte contient toujours au moins une case constructible et que cette fonction renverra donc toujours un résultat.

Compléter le code de la fonction plus_grande_base_exhaustive.

def plus_grande_base_exhaustive(carte):
    n = len(carte)
    # les tailles vont de n à 1, de -1 en -1
    for taille in range(n, 0, -1):
        i = 0
        while i + taille <= n:
            j = ...
            while ...:
                if est_constructible(...):
                    return (taille, i, j)
                j = ...
            i = i + 1

Un décompte du nombre de carrés à étudier dans le pire des cas en fonction de la taille de la carte initiale permet de construire la figure 1 ci-dessous.

Expliquer pourquoi cette approche exhaustive est inapplicable dans le cas de grandes cartes.

Partie B

On souhaite désormais résoudre ce problème en utilisant la programmation dynamique. Pour cela, on construit une liste de listes auxiliaire aux de mêmes dimensions que la carte et telle que aux[i][j] contienne la taille de la plus grande base (carrée) issue de carte[i][j].

En reprenant l’exemple de carte_A, on obtient la liste de listes aux_A :

carte_A = [
    [0, 0, 1, 1, 1],
    [1, 1, 0, 1, 1],
    [0, 1, 1, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 1, 1, 0],
]


aux_A = [
    [0, 0, 1, 2, 1],
    [1, 1, 0, 1, 1],
    [0, 3, 2, 1, 0],
    [0, 2, 2, 1, 0],
    [0, 1, 1, 1, 0],
]

aux_A[2][1] contient la valeur 3 car la plus grande base issue de la cellule carte_A[2][1] a une taille de 3.

Une fois la liste de listes auxiliaire aux remplie, on détermine la taille et les coordonnées de la plus grande base (carrée) de la carte en cherchant la valeur maximale dans aux.

Déterminer la liste auxiliaire aux_B associée à la carte représentée par carte_B.

carte_B = [
    [1, 1, 1, 1],
    [0, 1, 1, 1],
    [0, 1, 1, 1],
    [1, 0, 1, 1],
]

On considère une carte carte_C de taille 6 ainsi que la liste auxiliaire aux_C associée. Seules certaines valeurs sont données ci-dessous.

carte_C = [
    [..., ..., ..., 0, ..., ...],
    [1, ..., ..., ..., ..., ...],
    [..., ..., ..., ..., ..., ...],
    [..., ..., ..., 1, ..., ...],
    [1, ..., ..., ..., ..., ...],
    [..., ..., ..., ..., ..., ...],
]

aux_C = [
    [..., ..., ..., a, 2, ...],
    [b, 0, ..., 1, 1, ...],
    [3, 2, ..., ..., ..., ...],
    [..., ..., ..., c, 2, ...],
    [d, 2, ..., 2, 2, ...],
    [1, 1, ..., ..., ..., ...],
]

Déterminer les valeurs des coefficients a, b, c et d.

Pour une liste de listes carte donnée, lorsqu’on construit la liste auxiliaire aux associée, on commence par remplir les cellules de la dernière ligne et de la dernière colonne de aux en recopiant celles de carte.

On admet de façon générale que, pour toutes les autres cellules, si carte[i][j] vaut 0 alors aux[i][j] prend aussi la valeur 0, et, si carte[i][j] = 1, alors aux[i][j] se calcule à l’aide de l’expression suivante :

1 + min(aux[i + 1][j], aux[i][j + 1], aux[i + 1][j + 1])

Recopier et compléter les lignes 8, 9, 14 et 15 de la fonction calcule_aux qui prend en paramètre une liste de liste carte et renvoie la liste auxiliaire associée.

def calcule_aux(carte):
    n = len(carte)
    aux = [[0 for j in range(n)] for i in range(n)]

    # Remplissage de la dernière ligne
    # et de la dernière colonne
    for k in range(n):
        aux[n - 1][k] = ...
        aux[...][...] = ...

    # On complète les lignes de bas en haut
    for i in range(n - 2, -1, -1):
        # On complète les colonnes de droite à gauche
        for j in range(...):
            if ...:
                aux[i][j] = 1 + min(aux[i + 1][j],
                                    aux[i][j + 1],
                                    aux[i + 1][j + 1])
    return aux

La fonction plus_grande_base prend en paramètre une liste de listes carte et renvoie la taille et les coordonnées du coin supérieur gauche d’une base de taille maximale. Cette fonction utilise la liste auxiliaire aux renvoyée par l’appel calcule_aux(carte).

Compléter la fonction plus_grande_base à partir de la ligne 7. Il est possible d’écrire plusieurs lignes.

def plus_grande_base(carte):
    n = len(carte)
    aux = calcule_aux(carte)
    taille_max = aux[0][0]
    i_max = 0
    j_max = 0
    ...

carte_1000 est la liste représentant une carte de 1 000 × 1 000 cases et carte_3000 celle représentant une carte de 3 000 × 3 000 cases.

L’appel plus_grande_base(carte_1000) s’exécute en 0,4 seconde.

Parmi les durées suivantes, indiquer celle qui permet d’estimer le temps d’exécution de l’appel plus_grande_base(carte_3000) :
- 0,4 seconde ;
- 1,2 seconde ;
- 3,6 secondes.
Justifier.