Programmation dynamique

Les problèmes d'optimisation dynamique ont des applications importantes aussi bien dans l'industrie qu'en gestion. Il s'agit de minimiser le coût d'une trajectoire dans un espace d'états. On dispose d'une loi d'évolution, qui détermine l'état suivant à partir de l'état courant et d'une << commande >> ; les trajectoires sont construites à partir d'un état initial et d'une suite de commandes, suivant cette loi d'évolution ; on se donne également une fonction d'objectif, définie sur les trajectoires, qu'il s'agit de minimiser. La programmation dynamique est une méthode de résolution, pour les problèmes qui satisfont au principe d'optimalité de Bellman (1955) : une sous-trajectoire d'une trajectoire optimale est elle-même optimale pour la fonction d'objectif restreinte aux trajectoires ayant pour origine celle de cette sous-trajectoire. Ce principe permet une méthode de résolution ascendante^2.2, qui détermine une solution optimale d'un problème à partir des solutions de tous les sous-problèmes.

Une approche descendante pourrait être tentée : à partir du problème initial, générer ses sous-problèmes, les résoudre (récursivement), et déterminer la trajectoire optimale à partir des trajectoires optimales obtenues pour les sous-problèmes. Cette approche conduit en général à la génération d'un nombre exponentiel de sous-problèmes (par exemple, 2 à la première étape, 4 à la seconde, ..., 2ⁿ à la n-ème étape) ; cependant, quand l'ensemble des sous-problèmes a une taille inférieure à cette estimation du nombre de sous-problèmes générés, les sous-problèmes générés ne peuvent pas être tous distincts. Par exemple, pour le problème << trouver le plus court chemin entre deux sommets d'un graphe >>, quand le graphe a n sommets, il y a n² sous-problèmes << trouver le plus court chemin de u à v >>, pour chaque couple (u,v)de sommets. Pourtant, à chaque étape, il faudrait générer 2nsous-problèmes, << trouver le plus court chemin de u à w >> et << trouver le plus court chemin de w à v >>, pour chacun des nsommets du graphe. Dans ces situations, un même sous-problème sera résolu plusieurs fois. On peut combiner cette approche descendante avec une mise en mémoire (ou tabulation) du résultat d'un sous-problème : ainsi, quand le même sous-problème se présente une deuxième fois, il suffit de lire en mémoire le résultat, ce qui évite de tenter de le résoudre à nouveau.

L'approche descendante avec mise en mémoire peut être utilisée indépendamment du principe d'optimalité. Par exemple, le calcul de la fonction de Fibonacci peut en bénéficier, comme le montre le programme suivant, où la mise en mémoire utilise une liste :

import java.util.List;
import java.util.ArrayList;

class Fibonacci {

  private static List mémoire = new ArrayList(20);

  public static int fibonacci(int n) {
    if (n<=1)
      return 1;
    else {
      if (mémoire.get(n)!=null) {
        return ((Integer) mémoire.get(n)).intValue();
      } else {
        int f = fibonacci(n-1) + fibonacci(n-2);
        mémoire.set(n, new Integer(f));
        return f;
      }
    }
  }

  static void main(String[] args) {
    int max = Integer.parseInt(args[0]);
    for (int n=max-1; n>=0; n--) {
      System.out.println("fibonacci(" + n +") = " + 
                          fibonacci(n));
    }
  }
}

La programmation dynamique est au contraire une approche ascendante, non récursive. Signalons que le terme << programmation >> n'a pas ici de signification informatique, mais désigne plutôt une technique de << tabulation >> (comme par exemple, la programmation linéaire).