Aller au contenu

T3.2 Programmation dynamique⚓︎

On a déjà rencontré plusieurs paradigmes algorithmiques:

  • l'algorithme glouton : il construit de façon itérative une solution en optimisant un critère de manière locale, sans assurance de construire une solution globale optimale;
  • la méthode «diviser pour régner» : on divise un problème en sous-problèmes indépendants qu'on résout récursivement, puis on combine les solutions des sous-problèmes pour construire une solution globale.

Mais que se passe-t-il lorsque les sous-problèmes se chevauchent, c'est-à-dire qu'ils ne sont pas indépendants, comme dans le calcul (naïf) des termes de la suite de Fibonacci (exercice 6 du T2.2)?

Principe

La programmation dynamique consiste à diviser un problème en sous-problèmes indépendants puis à résoudre chaque sous-problème du plus petit au plus grand en stockant au fur et à mesure les résultats afin de ne pas avoir à les recalculer.

Cette technique a été développée par Richard Bellman dans les années 1950 chez RAND Corporation et permet de résoudre de nombreux problèmes d'optimisation de façon très performante.

Nous illustrerons cette technique par deux procédés: la mémoïsation et la méthode «bottom-up».

1. Principe de mémoïsation⚓︎

La mémoïsation consiste tout simplement à stocker les valeurs déjà calculées par une fonction pour des «petits» arguments. On peut pour cela utiliser un tableau ou un dictionnaire.

Exercice 1

Écrire une fonction fibo récursive et mémoïsée: on commence par consulter le dictionnaire pour savoir si la valeur est connue, auquel cas on se contente de la renvoyer, sinon on la calcule comme naïvement.

Rappel de la fonction naïve: 

1
2
3
4
5
def fibo(n):
    if n < 2:
        return 1
    else:
        return fibo(n-2) + fibo(n-1)

Python's corner

En Python il existe un décorateur qui permet de mémoïser automatiquement une fonction:

1
2
3
4
5
6
7
8
from functools import lru_cache

@lru_cache()
def fibo(n):
    if n < 2:
        return 1
    else:
        return fibo(n-2) + fibo(n-1)

Exercice 2

La fonction suivante donne le nombre minimal de pièces pour payer la somme demandée (cf. le problème du rendu de monnaie):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def rendu_monnaie(somme: int, pieces: list) -> int:
    '''
    Détermine le nombre minimal de pièces pour payer la somme demandée.
    La liste pieces est supposée triée dans l'ordre croissant.
    '''
    if somme == 0:
        return 0
    rendu = somme 
    for p in pieces:
        if p <= somme:
            rendu = min(rendu, 1 + rendu_monnaie(somme - p, pieces))
    return rendu

  1. Tester la fonction avec les appels:

    • rendu_monnaie(12, [1, 2, 5, 10, 20, 50, 100])
    • rendu_monnaie(28, [1, 2, 5, 10, 20, 50, 100])
    • rendu_monnaie(37, [1, 2, 5, 10, 20, 50, 100])

  2. Mémoïser la fonction rendu_monnaie:

    • initialiser correctement un dictionnaire memo_rendu;
    • consulter d'abord le dictionnaire pour voir si somme lui appartient;
    • sinon calculer la valeur rendu de la même façon et l'ajouter au dictionnaire memo_rendu avant de la renvoyer.

2. Méthode «bas-haut» («bottom-up»)⚓︎

Dans la méthode «bottom-up» on va construire un tableau (1D ou 2D) comme dans la méthode de mémoïsation, mais en commençant par les «petits» résultats pour aller vers la solution globale. On peut alors (parfois) transformer un programme récursif en un programme itératif.

Exemple avec Fibonacci

1
2
3
4
5
def fibo_bottom_up(n):
    lst_fibo = [1] * (n+1)
    for i in range(2, n+1):
        lst_fibo[i] = lst_fibo[i-2] + lst_fibo[i-1]
    return lst_fibo[n]

Exercice 3

Adapter la méthode «bottom-up» pour la fonction rendu_monnaie précédente en complétant le code suivant:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def rendu_monnaie_bu(somme: int, pieces: list) -> int:
    '''
    Détermine le nombre minimal de pièces pour payer la somme demandée.
    La liste pieces est supposée triée dans l'ordre croissant.
    '''
    rendu = [0] * ...
    for s in range(1, somme+1):
        rendu[s] = ... # on initialise avec le nombre de pieces dans le pire des cas
        for p in pieces:
            if p <= s:
                rendu[s] = min(..., ...)
    return rendu[...]

Exercice 4

Sur une grille rectangulaire, combien de chemins mènent du coin supérieur gauche au coin inférieur droit, en se déplaçant uniquement le long des traits horizontaux vers la droite et le long des traits verticaux vers le bas?

  1. Écrire une fonction récursive nb_chemins_rec qui répond au problème puis la «mémoïser».
  2. Écrire une fonction itérative nb_chemins selon la méthode «bottom-up» qui utilise un tableau 2D.

On remarquera:

  • qu'un déplacement uniquement vertical ou uniquement horizontal ne donne qu'un seul chemin.
  • que pour arriver en bas à droite, on ne peut arriver que de deux endroits: juste au-dessus ou juste à gauche.

3. Un problème pour finir en beauté⚓︎

Dans l'image ci-dessous, quel est la taille du plus grand carré blanc, c'est-à-dire qui ne contient aucun pixel noir?

Indication

On détermine la taille \(PGCB(x, y)\) du plus grand carré blanc dont le pixel en bas à droite a pour coordonnées \((x, y)\).