Couture droite ou couture souple ? — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 6)

Couture droite ou couture souple ?

Redimensionner une image : le seam carving · niveau 1 (application)

Énoncé

Une idée simple consiste à retirer la colonne d'énergie totale minimum.

Écrire le calcul de la meilleure colonne. Quelle est sa complexité ?
Comparer, sur l'image du chapitre, le coût de la meilleure colonne et celui de la meilleure couture.
Le coût de la meilleure couture est-il toujours inférieur ou égal à celui de la meilleure colonne ?

Corrigé

On somme les énergies de chaque colonne et l'on garde la plus petite somme : $Θ (L C)$ .


int[] S = new int[C];
for (int c = 0; c < C; c++) for (int l = 0; l < L; l++) S[c] += E[l][c];
int best = 0;
for (int c = 1; c < C; c++) if (S[c] < S[best]) best = c;


sommes des colonnes : [500, 426, 384, 328, 356, 458, 432, 500]
meilleure colonne 3, coût 328
meilleure couture : coût 308

La couture souple économise $20$ en zigzaguant entre les colonnes $3$ et $4$ .


nom : S
valeurs : 500 426 384 328 356 458 432 500
vert : 3
legende : sommes des colonnes : la meilleure, 328, en colonne 3

Oui : une colonne droite est une couture particulière (que des pas N). Le minimum sur toutes les coutures est donc inférieur ou égal au minimum sur les colonnes. La couture souple n'est jamais pire, pour le même ordre de complexité.