Table de matières

Un exercice d'algorithmique - mise en page de paragraphe, résolutions gourmande et dynamique

Source : http://lacl.fr/~lpellissier/Algo1/TD3.pdf, auteur : Luc Pélissier (2020-21).

Le problème étudié est l’impression équilibrée d’un paragraphe sur une imprimante. Le texte d’entrée est modélisé comme une séquence de $n$ mots de longueurs $l_1,l_2, \dots, l_n$ (mesurées en caractères, que l'on suppose tous de même largeur - c'est le cas par exemple avec une police dite à chasse fixe).

On souhaite imprimer ce paragraphe de manière équilibrée sur un certain nombre de lignes qui contiennent un maximum de $M\geq1$ caractères chacune. Le critère d’équilibre est le suivant : Si une ligne donnée contient les mots $i$ à $j$ (avec $i \leq j$) et qu’on laisse exactement une espace) entre deux mots, le nombre de caractères d’espacements supplémentaires à la fin de la ligne est $f(M - j+i - \sum\limits_{k=i}^j l_k)$, qui doit être positif ou nul pour que les mots tiennent sur la ligne. L’objectif est de minimiser la somme, sur toutes les lignes hormis la dernière, des cubes des nombres de caractères d’espacement présents à la fin de chaque ligne : cela correspond à $f(s) = s^3$.

Remarque : pour bien visualiser ces espaces en fin de fichier, je termine chaque ligne par ;.

Question 1.

1. Est-ce que l’algorithme glouton consistant à remplir les lignes une à une en mettant à chaque fois le maximum de mots possibles sur la ligne en cours, fournit l’optimum ?

Réponse : non !

Contre exemple de taille fixée

Comme le coût est la somme des cubes d'espaces en fin de ligne, on peut penser à un contre-exemple qui va exploiter le fait que $(2x)^3 >> 2 x^3$, et produire un texte qui aura deux lignes identiques (avec $k$ espaces en fin de lignes) lorsqu'on le met en page optimalement, et une ligne quasi complète mais une deuxième ligne quasi vide :

Pour l'instant, j'ai codé ça vite fait en Bash pour calculer le coût des deux fichiers :

On voit que la solution gourmande a un coût de 54873 alors que la solution non gourmande (optimale) a un coût de 16000.

Faire croître la différence entre les deux coûts vers l'infini

On peut juste produire $n$ fois ces deux lignes, et le coût de la solution gourmande sera $54873 n$ et le coût optimal sera $16000 n$. Cela montre que la différence entre les deux coûts n'est pas bornée.

Bonus : faire croître le rapport vers l'infini ?

On devrait pouvoir aussi faire croître le rapport des deux coûts vers l'infini : plutôt que de générer ces $n$ lignes identiques, on a juste à augmenter la longueur de ces lignes (et n'en avoir que deux, mais très longues). Comme le coût est cubique en le nombre d'espaces, on aura bien un rapport non borné entre le coût gourmand (sous optimal) et le coût optimal.

Corollaire : cela montre que la solution gourmande n'est pas un k-approximation du problème étudié.

Code Python pour la méthode gloutonne

Même si elle n'est pas efficace, on va commencer par écrire cette méthode gloutonne :

Exemples

Un premier exemple simple :

Peut-on retrouver la solution suivante, qui avait été calculée à la main ?

Vérifions cela :

Question 2.

2. Donner un algorithme de programmation dynamique résolvant le problème. Analyser sa complexité en temps et en espace. Et implémenter le dans le langage de votre choix. Vérifier qu'il donne la réponse optimale sur l'exemple trouvé en question 1. (ou en tous cas, une meilleure réponse).

On va déjà écrire le problème d'optimisation à résoudre, puis une relation de récurrence. En écrivant un algorithme récursif naïf mais avec mémoïsation, on obtiendra un algorithme de programmation dynamique.

Problème d'optimisation à résoudre

On se donne $M\in\mathbb{N}^*$ la taille de ligne, et un nombre $N\in\mathbb{N}^*$ objets, de longueurs $l_k \in [1,\dots,M]$. On souhaite minimiser le coût suivant, qui dépend de :

$$ \min_{ L\in\{1,\dots,M\}, \\ \ell_1,\dots,\ell_{L-1}\in\{1,\dots,N\},\\ \forall x\in\{1,\dots,L-1\}, \ell_{x+1} \geq \ell_x + 1, } \sum_{x=1}^{L-1} (M - \ell_{x+1} + \ell_x - \sum_{k=\ell_x}^{\ell_{x+1}} l_k)^3 $$

Relation de récurrence

Initialisation : S'il n'y a qu'un seul mot, la solution est triviale : on le place sur la première ligne, et on a terminé.

Hérédité : On considère le premier mot $l_1$ et le deuxième mot $l_2$. Le coût de la solution optimale est le minimum des coûts des deux solutions optimales aux sous-problèmes suivants (de taille strictement plus petite) :

  1. on place les deux premiers mots ensemble, et on remplace donc $l_1,l_2$ par $l_1' := l_1 + l_2 + 1$, et la suite des mots est juste décalée : $l_k' := l_{k+1}$. Ce cas a $N-1$ mots ;
  2. on place le premier mot sur sa propre ligne (cas de base), et on résound avec les mots restants : $l_k' := l_{k+1}$. Ce cas a aussi $1$ et $N-1$ mots sur les deux sous-problèmes.

TODO

Implémentation naïve par mémoïsation

Exemples

Vérifions cela :

Peut-on retrouver la solution suivante, qui avait été calculée à la main ?

Vérifions cela :

Et pour la solution dynamique :

Question 3.

3. Supposons que pour la fonction de coût à minimiser, on ait simplement choisi la somme des nombres de caractères d’espacement présents à la fin de chaque ligne. Est-ce que l’on peut faire mieux en complexité que pour la question ?

Oui la solution gourmande, qui est donc au plus linéaire en temps et demande une mémoire de travail supplémentaire constante (ou bornée par la taille du plus long mot, selon de savoir si len(mot) est en $O(1)$ ou en $O(|\text{mot}|)$), sera optimale.

Question 4. Pourquoi un coût cubique et pas linéaire ?

4. (Plus informel) Qu’est-ce qui à votre avis peut justifier le choix de prendre les cubes plutôt quesimplement les nombres de caractères d’espacement en fin de ligne ?

Si le coût est linéaire, alors la solution gourmande sera optimale (ou en tous cas une approximation à facteur constant). Mais c'est aussi que l'affichage ne fera pas de différence entre les deux exemples ci dessous, alors que l'on est clairement plus satisfait du rendu visuel du deuxième, qui équilibre mieux les deux lignes.

(je ne suis pas trop sûr de tout ça)

TODO mieux expliquer !

On peut vérifier la solution trouvée avec un coût carré et pas cubique :

Sur cet exemple, on obtient exactement la même solution.

Mais je pense qu'on peut trouver des exemples où la solution avec un coût cubique est différente de celle avec un coût quadratique.

Conclusion

Et si vous cherchiez à résoudre ça dans votre langage de programmation favori ? En Python ou en OCaml, cela ne devrait pas être trop difficile.