Chemins de valeur optimale

Au chapitre 1, Zébulon cherchait un chemin de valeur maximum en sautant de case en case. Ce chapitre généralise cette situation : des villes reliées par des lignes de bus, puis un robot qui se déplace sur une grille. Dans tous les cas, la question clé est la même : d'où vient-on, au dernier pas ?

5.1 Deux lignes de bus

Les villes $0,1,\dots ,n-1$ sont alignées et desservies par deux lignes de bus. Depuis la ville $i$ on peut aller :

• à la ville $i+1$, pour un coût $d_1(i)$ ;
• directement à la ville $i+2$, pour un coût $d_2(i)$.

On veut un trajet de coût minimum de la ville $0$ à la ville $n-1$.

Exemple 5.1cinq villes

$D_1=[10,20,100,30,-]$ et $D_2=[40,50,60,-,-]$ (les cases marquées $-$ n'ont pas de sens : il n'y a pas de ville $5$ ou $6$). Le trajet $0\to 1\to 3\to 4$ coûte $10+50+30=90$.

Supposons le problème résolu

Notons $m(j)$ le coût minimum d'un trajet de la ville $0$ à la ville $j$. Un trajet optimal vers $j$ (avec $j\ge 2$) arrive par l'un des deux derniers trajets possibles :

• depuis $j-1$, par la ligne courte : le trajet de $0$ à $j-1$ est alors optimal (sinon on l'améliorerait), et le coût total est $m(j-1)+d_1(j-1)$ ;
• depuis $j-2$, par la ligne longue : coût $m(j-2)+d_2(j-2)$.

On calcule $M[0:n]$ par $j$ croissants, en $\Theta (n)$ :

static int[] calculerM(int[] D1, int[] D2) { int n = D1.length;
    // retourne M[0:n] de terme général M[j] = m(j)
    int[] M = new int[n];
    M[0] = 0;                                 // base
    if (n > 1) M[1] = D1[0];                  // base
    for (int j = 2; j < n; j++)               // hérédité, par j croissants
        M[j] = Math.min(M[j-1] + D1[j-1], M[j-2] + D2[j-2]);
    return M;
}

Pour afficher le trajet, on n'a pas mémorisé d'arguments : on retrouve le dernier trajet en testant laquelle des deux égalités est vérifiée. Notons $\mathrm{tr}(j)$ un trajet de coût minimum de $0$ à $j$ : $\mathrm{tr}(j)=\mathrm{tr}(j-1)\to j$ si $m(j)=m(j-1)+d_1(j-1)$, et $\mathrm{tr}(j)=\mathrm{tr}(j-2)\to j$ sinon.

static void afficherCheminMinimum(int[] M, int[] D1, int[] D2, int j) {
    // affiche tr(j). Appel principal : afficherCheminMinimum(M, D1, D2, n-1)
    if (j == 0) { System.out.print("0"); return; }  // tr(0) a été affiché
    if (M[j] == M[j-1] + D1[j-1]) {  // dernier trajet : j-1 -> j
        afficherCheminMinimum(M, D1, D2, j-1);  // tr(j-1) a été affiché
        System.out.printf("--(%d)-->%d", D1[j-1], j);
    } else {  // dernier trajet : j-2 -> j
        afficherCheminMinimum(M, D1, D2, j-2);  // tr(j-2) a été affiché
        System.out.printf("--(%d)-->%d", D2[j-2], j);
    }  // donc tr(j) a été affiché
}

$ java BusDeuxLignes
M = [0, 10, 30, 60, 90]
Coût minimum m(4) = 90 : 0--(10)-->1--(50)-->3--(30)-->4

Ici le minimum est atteint deux fois pour $j=4$ : $m(3)+30=90$ et $m(2)+60=90$. Il y a deux trajets optimaux ; la fonction affiche celui qu'elle teste en premier.