Programmation dynamique

Rappel : Définition de suites récurrentes

Exemple de la factorielle: \[u_0 = 1 \qquad \text{ et }\qquad \forall n\geq 1 \quad u_n = n\times u_{n-1}\]

def factorielle(n: int) -> int:
   assert n >= 0
   if n == 0:
       return 1
   return n * factorielle(n - 1)

Fonctions récursives : attention aux écueils

Suite de Fibonacci:

\[F_0 = F_1 = 1 \qquad \text{ et }\qquad \forall n\geq 2 \quad F_{n} = F_{n-1} + F_{n-2}\]

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

Graphe d’appels

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

Graphe d’appels et nombre total d’appels nécessaires

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

Pour faire mieux : calcul ascendant

• Calculer l’ensemble \(S\) des sommets accessibles depuis le sommet \(v\) dont on cherche à calculer la valeur
• Ordonner \(S\) selon un tri topologique \(<\) (c’est-à-dire tel que si \((u,v)\) est un arc du graphe d’appels alors \(v < u\)) : cf séance sur les parcours de graphes
• Par ordre croissant, calculer et stocker l’image de chaque sommet de \(S\)

Calcul ascendant pour Fibonacci

• Si on veut calculer \(F_n\), l’ordre topologique nous dit de calculer tous les \(F_i\) pour \(i\) de \(0\) à \(n\)…
• On les stocke dans une liste !

def fibonacci(n):
    resultats = [1, 1] # on connait les valeurs de F0 et F1
    for i in range(2, n + 1):
        resultats.append(resultats[-1] + resultats[-2])
    return resultats[n]

Programmation dynamique

Une méthodologie pour aborder certains problèmes…

Lorsque les sous-problèmes ont des sous-sous-problèmes en commun, il faut les résoudre une seule fois et mettre le résultat dans une table !

Méthodologie

Problèmes d’optimisation

• des problèmes qui admettent un ensemble de solutions \(\mathcal S\)
• \(c\colon \mathcal S \to \mathbf R\) fonction objectif
• on cherche une solution \({s^*}\) telle que \(c(s^* ) = \min \{c(s)\mid s\in \mathcal S\}\)

Conception d’un algorithme de programmation dynamique

1. Caractérisation de la structure des solutions optimales
2. Définition récursive de la valeur optimale
3. Calcul ascendant de la valeur optimale
4. Construction d’une solution optimale à partir des informations obtenues en 3 (facultatif)

Exemple : ordonnancement de chaînes de montage

• Un constructeur automobile possède un atelier avec deux chaînes de montage (1 et 2) comportant chacune \(n\) postes.
• Chaque véhicule doit passer par les \(n\) postes dans l’ordre.

Exemple : ordonnancement de chaînes de montage

Données du problème

• \(S_{i,j}\) le \(j\)-ième poste de la chaîne \(i\)
• \(e_i\) le temps d’entrée d’un véhicule sur la chaîne \(i\)
• \(a_{i,j}\) le temps de montage pour le poste \(j\) sur la chaîne \(i\) (on peut avoir \(a_{1,j}\neq a_{2,j}\))
• \(t_{i,j}\) le temps de transfert d’un véhicule de la chaîne \(i\) vers l’autre chaîne après le poste \(S_{i,j}\)
• \(x_i\) le temps de sortie d’un véhicule de la chaîne \(i\)

Problème

Déterminer quels sont les postes à sélectionner sur la chaîne 1 et sur la chaîne 2 pour minimiser le délai de transit d’une auto à travers l’atelier

Exemple

Espace des solutions

• Chaque solution est définie par le sous-ensemble de postes de la chaîne 1 utilisés (les postes restants sont choisis dans la chaîne 2)

Combien de solutions possibles ?

Étape 1 : sous-structures optimales

Les sous-problèmes à considérer consistent à calculer un itinéraire optimal jusqu’au poste \(S_{i,j}\) pour \(i= 1, 2\) et \(j = 1, \ldots, n\)

Par exemple, considérons un itinéraire optimal jusqu’au poste \(S_{1,j}\):

• Si \(j=1\), il n’y a qu’un seul chemin possible
• Pour \(j=2, \ldots, n\), il y a deux possibilités:
  • ou bien l’itinéraire optimal jusqu’à \(S_{1,j-1}\) suivi du poste \(S_{1,j}\)
  • ou bien l’itinéraire optimal jusqu’à \(S_{2,j-1}\) suivi d’un changement de chaîne et du poste \(S_{1,j}\)

Étape 2 : solution récursive

\(f_{i}[j]\) : délai optimal jusqu’à \(S_{i,j}\)

\({f^*}\) : délai optimal pour traverser l’atelier \[f^* = \min (f_1[n] + x_1, f_2[n] + x_2)\]

Exemple

Information pour la construction de la solution

Les \(f_i[j]\) sont les valeurs des solutions optimales des sous-problèmes

Pour pouvoir reconstruire les solutions optimales elles-mêmes, on définit

• \(l_i[j]\) le numéro de la chaîne (1 ou 2) dont le poste \(j-1\) est utilisé par un chemin optimal jusqu’au poste \(S_{i,j}\)

• \(l_1[j]\) n’est pas défini car aucun poste ne vient avant le poste 1

Exemple

Étape 3 : calcul des temps optimaux de manière ascendante

Étape 4 : construction du chemin optimal

Affichage par ordre décroissant des numéros de poste :