Le robot part de n'importe où — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 5)

Le robot part de n'importe où

Chemins de valeur optimale · niveau 2

Énoncé

Le robot peut partir de n'importe quelle case de la ligne $0$ et doit arriver sur n'importe quelle case de la ligne $L - 1$ ; ses déplacements sont NO, N et NE (il monte d'une ligne à chaque pas).

Écrire la récurrence de la valeur maximum $m (l, c)$ d'un chemin qui arrive en $(l, c)$ . Où lire la réponse ?
Programmer et exécuter sur la grille du chapitre. Ce problème est le cœur du chapitre suivant.

Corrigé

Base. $\forall c, 0 \leq c < C$ : $m (0, c) = g (0, c)$ (on peut partir de partout).

Hérédité. $\forall l, 1 \leq l < L$ , $\forall c, 0 \leq c < C$ : $m (l, c) = max {m (l - 1, c - 1), m (l - 1, c), m (l - 1, c + 1)} + g (l, c)$ , les termes hors de la grille étant omis.

La réponse est $max_{0 \leq c < C} m (L - 1, c)$ : on arrive où l'on veut. -


for (int c = 0; c < C; c++) M[0][c] = G[0][c];             // base
for (int l = 1; l < L; l++)                                // par lignes croissantes
    for (int c = 0; c < C; c++) {
        int p = M[l - 1][c];
        if (c > 0) p = Math.max(p, M[l - 1][c - 1]);
        if (c < C - 1) p = Math.max(p, M[l - 1][c + 1]);
        M[l][c] = p + G[l][c];
    }


ligne 4 : [21, 22, 24, 29, 19]
ligne 3 : [11, 20, 21, 22, 8]
ligne 2 : [4, 11, 16, 11, -7]
ligne 1 : [-2, 1, 9, -11, -12]
ligne 0 : [-3, 8, -8, -2, -9]
Valeur maximum 29 : (0,1)->(1,2)->(2,2)->(3,3)->(4,3)


nom : M[4]
valeurs : 21 22 24 29 19
colorier : 3
legende : la réponse est le maximum de la dernière ligne : 29, en c = 3

C'est la récurrence du seam carving, au $max$ près.