Heures et malheurs de l'optimisation

Cette année, quand d'autres traversaient la torpeur de l'été en s'adonnant au Sudoku, je m'exerçais au Jeu du gratte-ciel . Une grille N x N, des immeubles de hauteur 1 à N, chaque hauteur étant représentée une et une seule fois par ligne et par colonne. Sur les côtés, en guise d'indices, le nombre d'immeubles que verrait un observateur regardant vers l'intérieur de la grille.

Et comme en Août, la France entière s'arrête et que les après-midi s'étirent à n'en plus finir, je me suis mis en tête d'implémenter un algorithme capable de résoudre par lui-même toute grille de ce jeu. De nombreuses heures plus tard, voici le résultat (https://github.com/mathieueveillard/skyscrapers ) et quelques réflexions sur l'optimisation.

Eh oui… Car le jeu, facile au premier abord, se corse sérieusement quand la dimension augmente et que les indices se raréfient. Celui-ci , en dimension 5, est déjà nettement plus compliqué.

Si vous vous prenez au jeu et que l'envie vous vient de rechercher un algorithme, vous découvrirez rapidement qu'il s'agit d'un problème de programmation par contraintes , les contraintes étant ici :

Chacun connaît la mise en garde de Donald Knuth. Cependant, elle ne doit pas être comprise comme une invitation à écrire des algorithmes totalement naïfs, qui ignoreraient une difficulté connue depuis le début.

L'algorithme naïf consisterait ici à générer toutes les grilles possibles pour éliminer ensuite celles qui ne satisfont pas toutes les contraintes. Considérant les N hauteurs possibles pour chacun des N^2 immeubles, cela fait N^(N^2) grilles de N^2 valeurs… Oublions.

Non, il faut renverser le problème et générer les lignes/colonnes "candidates" à partir des contraintes dont nous disposons. L'idée est donc de partir d'une séquence

[1, 2, …, N]

correspondant à une vue de N (vue de gauche). Tout déplacement d'un immeuble vers la droite permet de faire baisser la vue de 1.

Exemple, en dimension 4 :

[1, 2, 3, 4] -> vue = 4
Déplacer le 1 : [2, 1, 3, 4] ou [2, 3, 1, 4] ou [2, 3, 4, 1] -> vue = 3
Déplacer le 2 : [1, 3, 2, 4] ou [1, 3, 4, 2] -> vue = 3
Déplacer le 3 : [1, 2, 4, 3] -> vue = 3

Dans le cas idéal, seul un candidat est valide, une fois positionné dans la grille. Mais dans la plupart des cas, plusieurs candidats le sont, et vous devrez faire à chaque fois une hypothèse, que vous validerez ou invaliderez ultérieurement (grille complétée vs. impasse quelques lignes ou colonnes plus loin). C'est donc un algorithme de backtracking , qui explore récursivement un arbre des possibles.

Et dans la famille "on évite de faire des choses trop dégueulasses", la mémoisation est votre amie 😊

Comme toujours, 20% du temps que vous passerez sur le sujet vous offriront 80% des bénéfices d'optimisation, tandis que vous transpirerez les 80% du temps restant pour atteindre les 100% d'optimisation (à supposer d'ailleurs qu'ils puissent être jamais atteints). Dur, dur.

Ici, 2 principaux axes de travail :

Tout mis ensemble, l'optimisation a permis de diviser le temps d'exécution par 50, mais une grille de dimension 7 se résout tout de même en 20s environ, et je ne me risquerais pas à estimer la complexité temporelle de l'algorithme 🥲

Optimiser un algorithme, c'est avancer en terre inconnue : quand vous vous lancez dans l'implémentation d'un axe d'amélioration, vous ne savez généralement pas quantifier à l'avance le bénéfice attendu, ceci étant d'autant plus vrai que l'arbre de recherche dépend de la donnée d'entrée. Attendez-vous à travailler parfois longtemps pour des résultats imperceptibles.

Et cela aura valeur de conclusion.