Le glouton pris en défaut — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 6)

Le glouton pris en défaut

Redimensionner une image : le seam carving · niveau 2

Énoncé

Le glouton part du pixel d'énergie minimum de la ligne $0$ puis, à chaque ligne, monte sur celui des voisins NO, N, NE d'énergie minimum. On donne directement le tableau des énergies (ligne $0$ en bas) :

$l = 3 l = 2 l = 1 l = 0 9999888188891112$

Donner la couture gloutonne et son coût.
Calculer le tableau $M$ et une couture de coût minimum.
Montrer que, pour tout $K$ , on peut construire un tableau $4 \times 4$ où le coût glouton dépasse le coût minimum de plus de $K$ .

Corrigé

Le glouton part de $(0, 1)$ (énergie $1$ ), puis ses trois voisins du dessus valent $9$ , $8$ , $8$ : il monte en $(1, 1)$ et reste dans la colonne $1$ . Coût $1 + 8 + 8 + 8 = 25$ .


nom : E
valeurs : 9 1 9 2
colorier : 1
vert : 3
pointeurs : glouton=1 optimum=3
legende : ligne 0 de E : le glouton part du minimum 1, l'optimum part de 2

$M$ par lignes : $[9, 1, 9, 2]$ , puis $[10, 9, 9, 3]$ , puis $[18, 17, 11, 4]$ , puis $[26, 19, 12, 5]$ . Le minimum de la dernière ligne vaut $5$ , en colonne $3$ : la couture reste dans la colonne $3$ , de coût $2 + 1 + 1 + 1 = 5$ .


nom : M
valeurs : 26 19 12 5
vert : 3
legende : ligne 3 de M : minimum 5 en colonne 3, la couture y remonte


glouton : (0,1)->(1,1)->(2,1)->(3,1), coût 25
optimum : coût 5, colonnes [3, 3, 3, 3]

Remplacer les $8$ par une valeur $V$ arbitraire (et les $9$ par $V + 1$ ) : le glouton paie $1 + 3 V$ , l'optimum toujours $5$ . L'écart $3 V - 4$ dépasse n'importe quel $K$ .