Le glouton peut rester bloqué — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 1)

Le glouton peut rester bloqué

Glouton ou dynamique ? · niveau 1 (application)

Énoncé

Sur le ruban $R = [0, 0, 0, 5, 0]$ , appliquer la stratégie gloutonne (sauter sur la meilleure des deux cases accessibles). Que se passe-t-il ? Quelle est la valeur maximum d'un chemin de la case $0$ à la case $4$ ? Expliquer pourquoi le calcul de $M$ ne peut jamais « rester bloqué ».

Corrigé

Depuis $0$ , le glouton compare $R [2] = 0$ et $R [3] = 5$ et saute en $3$ . Depuis $3$ , les cases $5$ et $6$ sont hors du ruban : Zébulon est bloqué, il n'atteint jamais la case $4$ . Le seul chemin de $0$ à $4$ est $0 \to 2 \to 4$ , de valeur $0$ , et le calcul donne bien $m (4) = 0$ .


nom : R
valeurs : 0 0 0 5 0
colorier : 3
vert : 0 2 4
fleches : 0->3:glouton
fleches-bas : 0->2 2->4
legende : le glouton reste bloqué en 3 ; seul chemin : 0 → 2 → 4, de valeur 0

Le calcul de $M$ ne fait aucun choix définitif : $m (4)$ examine tous les derniers sauts possibles vers $4$ (depuis $2$ et depuis $1$ ), pas les sauts qui partent d'une case choisie à l'avance. Un glouton décide en regardant vers l'avant, sans savoir si la case choisie mène au but ; la programmation dynamique raisonne à rebours, depuis le but.