Programmation dynamique

$n$ objets de poids $p_i$ et valeur $v_i$, capacité $C$. Notons $M[i][c]$ la valeur maximale atteignable avec les $i$ premiers objets et une capacité $c$. Alors

$$M[i][c]=\{\begin{array}{ll}0& \text{si }i=0,\\ M[i-1][c]& \text{si }{p}_i>c\text{(l’objet ne rentre pas)},\\ \max (M[i-1][c],v_i+M[i-1][c-p_i])& \text{sinon.}\end{array}$$

La troisième ligne est le cœur : on compare ne pas prendre l'objet $i$ et le prendre, et l'on garde le meilleur.

/* Valeur maximale transportable. Préconditions : n >= 0, C >= 0,
   p[i] >= 0. Complexité : Theta(nC) en temps et en mémoire. */
int sac(const int p[], const int v[], int n, int C) {
    int m[n + 1][C + 1];
    for (int c = 0; c <= C; c = c + 1) { m[0][c] = 0; }
    for (int i = 1; i <= n; i = i + 1) {
        for (int c = 0; c <= C; c = c + 1) {
            m[i][c] = m[i - 1][c];                      /* on ne prend pas */
            if (p[i - 1] <= c) {
                int avec = v[i - 1] + m[i - 1][c - p[i - 1]];
                if (avec > m[i][c]) { m[i][c] = avec; }  /* on prend */
            }
        }
    }
    return m[n][C];
}

Une sous-suite s'obtient en supprimant des caractères sans changer l'ordre des autres. Pour $u$ et $v$ de longueurs $n$ et $m$, notons $L[i][j]$ la longueur de la plus longue sous-suite commune à $u_{\mathrm{1..}i}$ et $v_{\mathrm{1..}j}$ :

$$L[i][j]=\{\begin{array}{ll}0& \text{si }i=0\text{ ou }j=0,\\ 1+L[i-1][j-1]& \text{si }{u}_i=v_j,\\ \max (L[i-1][j],L[i][j-1])& \text{sinon.}\end{array}$$

(* Longueur de la plus longue sous-suite commune. Complexité : Theta(nm). *)
let plsc u v =
  let n = String.length u and m = String.length v in
  let l = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      l.(i).(j) <-
        if u.[i-1] = v.[j-1] then 1 + l.(i-1).(j-1)
        else max l.(i-1).(j) l.(i).(j-1)
    done
  done;
  l.(n).(m)

C'est l'algorithme au cœur de la commande diff et du calcul des différences entre deux versions d'un fichier.

Le nombre minimal d'insertions, suppressions et substitutions transformant $u$ en $v$ :

$$D[i][j]=\{\begin{array}{ll}j& \text{si }i=0,i\text{ si }j=0,\\ D[i-1][j-1]& \text{si }{u}_i=v_j,\\ 1+\min (D[i-1][j],D[i][j-1],D[i-1][j-1])& \text{sinon.}\end{array}$$

Les trois termes du minimum sont les trois opérations : supprimer $u_i$, insérer $v_j$, substituer l'un à l'autre.

De chaud à chat : distance $2$ — substituer u en t, supprimer d. La diagonale en gras est le chemin optimal, et c'est elle qu'on remonte pour reconstruire les opérations.

L'algorithme de Floyd-Warshall, que le chapitre chap:parcours détaillera, est un pur exercice de programmation dynamique. Le sous-problème est :

$$D_k[u][v]=\text{longueur du plus court chemin de }u\text{ aˋ }v\text{ n’utilisant que les sommets }\{0,\dots ,k-1\}\text{ comme intermeˊdiaires.}$$

et la récurrence tient en une ligne :

$$D_{k+1}[u][v]=\min (D_k[u][v],D_k[u][k]+D_k[k][v]).$$

Soit le plus court chemin passe par $k$, soit il n'y passe pas. Trois boucles imbriquées, $\Theta (n^3)$, et la sous-structure optimale y est parfaitement visible : un sous-chemin d'un plus court chemin est un plus court chemin.