Trois lignes de bus

Un trajet optimal vers $j$ arrive de $j - 1$ , $j - 2$ ou $j - 3$ . L'hérédité à trois termes n'a de sens que pour $j \geq 3$ : la base compte trois valeurs, $m (0) = 0$ , $m (1) = d_{1} (0)$ , $m (2) = min {m (1) + d_{1} (1), d_{2} (0)}$ . Hérédité : $\forall j, 3 \leq j < n$ ,

$m (j) = min {m (j - 1) + d_{1} (j - 1), m (j - 2) + d_{2} (j - 2), m (j - 3) + d_{3} (j - 3)} .$

En ne considérant que les lignes $l$ telles que $j - l \geq 0$ , une seule boucle couvre la base et l'hérédité :


static int[][] calculerMA(int[] D1, int[] D2, int[] D3) {
    int n = D1.length;
    int[][] D = {D1, D2, D3};                     // D[l-1][i] : coût de i -> i+l
    int[] M = new int[n], A = new int[n];
    M[0] = 0; A[0] = -1;                          // base
    for (int j = 1; j < n; j++) {                 // par j croissants
        M[j] = Integer.MAX_VALUE;
        for (int l = 1; l <= 3 && j - l >= 0; l++)
            if (M[j - l] + D[l - 1][j - l] < M[j]) {
                M[j] = M[j - l] + D[l - 1][j - l]; A[j] = j - l;
            }
    }
    return new int[][] {M, A};
}

$m (2) = min {10 + 20, 40} = 30$ , $m (3) = min {30 + 100, 10 + 50, 0 + 70} = 60$ , $m (4) = min {60 + 30, 30 + 60, 10 + 25} = 35$ :


M = [0, 10, 30, 60, 35]
A = [-1, 0, 1, 1, 1]
Coût minimum 35 : 0 -> 1 -> 4


nom : M
valeurs : 0 10 30 60 35
colorier : 4
vert : 0..3
fleches : 3->4 2->4 1->4
legende : m(4) = min(60 + 30, 30 + 60, 10 + 25) = 35 : trajet 0 → 1 → 4

On pose $d (i, i + 1) = d_{1} (i)$ , $d (i, i + 2) = d_{2} (i)$ , $d (i, i + 3) = d_{3} (i)$ et $d (i, j) = + \infty$ pour $j > i + 3$ : la récurrence des lignes directes redonne celle-ci. Mais elle coûte $Θ (n^{2})$ au lieu de $Θ (n)$ : le cas particulier se résout plus vite.

Énoncé

Corrigé