Optimiser encore le problème des gratte-ciel
Optimiser encore le problème des gratte-ciel
Complément à la formation
Bruno Mermet
I. Quelques pistes
Plusieurs pistes peuvent encore être exploitées pour optimiser encore le programme :
- Ne pas prendre les lignes dans l'ordre
-
Certaines lignes n'ont aucune contrainte, d'autres une, d'autres 2. Commencer par les lignes les plus contraintes permet d'élaguer plus vite l'arbre de résolution.
Certaines contraintes sont plus contraignantes que d'autres : plus est proche d'une valeur moyenne, plus cela est contraignant. Par exemple, sur une grille de 3x3, une contrainte à 1 (seule solution : [1, 2, 3]) est plus contraignante qu'une contrainte à 3 (2 solutions : [3, 1, 2] et [3, 2, 1]) qui est elle-même plus contraignante qu'une contrainte à 2 (3 solutions : [1,3, 2], [2, 1, 3]et [3, 1, 2]).
- Ne pas procéder par ligne
-
Certaines cases n'ont aucune contrainte au départ (pas de contrainte de visibilité, alors que d'autres peuvent être liées à 1, 2, 3, voire 4 contraintes. Il peut être intéressant de privilégier ces cases là. Par ailleurs, toute valeur placée dans une case contraint les cases de la même ligne et de la même colonne. Le nombre de contraintes d'une case va donc évoluer au cours du temps.
Remarques
Les suggestions des améliorations indiquées ci-dessus impliquent qu'on ne peut plus qu'on ne peut plus travailler sur le même objet lors des appels récursifs (à tout moment, il faut pouvoir prendre en compte ce qui est placé n'importe où sur la grille). Il devient alors indispensable de passer des copies lors des appels récursifs.
II. Exemple de mise en œuvre
Prenons la grille suivante, tirée de Tangente - Jeux & Stratégie :
Calculons les degrés de liberté de chaque case en raisonnant sur 1 niveau. Les voici figurant en rouge (toutes les cases non remplies ont un degré de liberté de 4 : toutes les valeurs sont possibles) :
La case la plus contrainte est celle marquée d'un 1 : une seule valeur est possible. La grille peut donc être complétée ainsi :
Les degrés de liberté peuvent alors être recalculés (par convention, on mettra 0 pour les cases déjà remplies) :
Tentons une valeur pour l'une des cases au plus faible degré de liberté (Embranchement 1) :
On peut alors remplir toutes les cases n'offrant qu'un degré de liberté :
| | | | | | |
| | 3 | 3 | 3 | 0 | |
| 1 | 0 | 2 | 2 | 0 | |
| | 1 | 3 | 3 | 0 | 3 |
| | 1 | 3 | 3 | 0 | |
| | 2 | | | 3 | |
On continue, toujours en ne remplissant que les cases n'ayant qu'un degré de liberté :
| | | | | | |
| | | | | 40 | |
| 1 | 40 | | | 30 | |
| | 20 | | | 10 | 3 |
| | 30 | | | 20 | |
| | 2 | | | 3 | |
| | | | | | |
| | 1 | 3 | 3 | 0 | |
| 1 | 0 | 2 | 2 | 0 | |
| | 0 | 1 | 1 | 0 | 3 |
| | 0 | 2 | 2 | 0 | |
| | 2 | | | 3 | |
Et ça continue, encore et encore... :
| | | | | | |
| | 10 | | | 40 | |
| 1 | 40 | | | 30 | |
| | 20 | 40 | 30 | 10 | 3 |
| | 30 | | | 20 | |
| | 2 | | | 3 | |
| | | | | | |
| | 0 | 2 | 1 | 0 | |
| 1 | 0 | 2 | 2 | 0 | |
| | 0 | 0 | 0 | 0 | 3 |
| | 0 | 1 | 2 | 0 | |
| | 2 | | | 3 | |
... C'est que le début, d'accord, d'accord :
| | | | | | |
| | 10 | | 20 | 40 | |
| 1 | 40 | | | 30 | |
| | 20 | 40 | 30 | 10 | 3 |
| | 30 | 10 | | 20 | |
| | 2 | | | 3 | |
| | | | | | |
| | 0 | 1 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 0 | |
| | 0 | 1 | 1 | 0 | 3 |
| | 0 | 0 | 1 | 0 | |
| | 2 | | | 3 | |
On poursuit... :
| | | | | | |
| | 10 | 30 | 20 | 40 | |
| 1 | 40 | 20 | 10 | 30 | |
| | 20 | 40 | 30 | 10 | 3 |
| | 30 | 10 | 40 | 20 | |
| | 2 | | | 3 | |
... Et on tombe sur la solution.
Il se peut qu'à un moment, on tombe sur une case avec aucune valeur possible. Il faut alors déclencher le back-tracking pour revenir sur le précédent point de choix et essayer une autre valeur possible.
Remarques
Dans l'exemple déroulé ci-dessus, le calcul des espaces de liberté pour une case c(i, j) a été fait en envisageant les différentes possibilités de permutation de la ligne i et de la colonne j, ce qui va au-delà de ce qui a été suggéré dans la première partie. Ceci risquerait par ailleurs d'exploser assez vite avec la taille de la grille (mais permettait de limiter les étapes pour l'explication). Dans les faits, il serait plus judicieux de s'en tenir aux contraintes directes (visibilité et unicité). Cela générerait plus de retour arrière, mais serait au final plus efficace.
III. Conseils pour l'implantation
Le fait de placer une nouvelle valeur sur la grille ne change les degrés de liberté que pour les cases de la même ligne et de la même colonne. Cela signifie donc que, pour gagner du temps, on peut :
- Passer la grille des degrés de liberté en paramètre de la fonction récursive ;
- Une fois une nouvelle valeur placée, ne calculer les degrés de liberté que pour les cases de la ligne et celles de la colonne de la case modifiée.
À un niveau donné, on peut rempir en un coup toutes les cases dont le degré de liberté est à 1. Cela évite de multiplier les appels récursifs impliquant une copie des 2 grilles (celles des gratte-ciel, et celle des degrés de liberté). Cependant, cela complique un peu la détermination des cases dont il faut recalculer les degrés de liberté.
IV. Influence de la visibilité sur les valeurs possibles
Nous allons commencer par une approche empirique sur une grille de taille 4. Pour simplifier, nous n'étudierons que la visibilité gauche d'une ligne.
Contrainte à 1 :
Liste des possibilités :
Degrés de liberté :
Contrainte à 2 :
Liste des possibilités :
Degrés de liberté :
Contrainte à 3 :
Liste des possibilités :
Degrés de liberté :
Contrainte à 4 :
Liste des possibilités :
Degrés de liberté :
Résumons cela en détaillant plutôt, pour chacun des cas, les valeurs possibles pour une case :
Liste des possibilités :
| 1 | {40} | {10, 20, 30} | {10, 20, 30} | {10, 20, 30} | |
| 2 | {10, 20, 30} | {10, 20, 40} | {10, 20, 30, 40} | {10, 20, 30, 40} | |
| 3 | {10, 20} | {10, 20, 30} | {10, 20, 30, 40} | {10, 20, 30, 40} | |
| 4 | {10} | {20} | {30} | {40} | |
Faisons le même travail sur un grille de taille 3... :
| 1 | {30} | {10, 20} | {10, 20} | |
| 2 | {10, 20} | {10,30} | {10, 20, 30} | |
| 3 | {10} | {20} | {30} | |
... et sur une grille de taille 5 :
| 1 | {50} | {10, 20, 30, 40} | {10, 20, 30, 40} | {10, 20, 30, 40} | {10, 20, 30, 40} | |
| 2 | {10, 20, 30, 40} | {10, 20, 30, 50} | {10, 20, 30, 40, 50} | {10, 20, 30, 40, 50} | {10, 20, 30, 40, 50} | |
| 3 | {10, 20, 30} | {10, 20, 30, 40} | {10, 20, 30, 40, 50} | {10, 20, 30, 40, 50} | {10, 20, 30, 40, 50} | |
| 4 | {10, 20} | {10, 20, 30} | {10, 20, 30, 40} | {10, 20, 30, 40, 50} | {10, 20, 30, 40, 50} | |
| 5 | {10} | {20} | {30} | {40} | {50} | |
On en déduit empiriquement une façon de déterminer les possibilités pour une case en fonction du critère de visibilité gauche. Cela est implanté dans le fichier determinerPossibilites.py. Dans de fichier, la fonction recherche_globale permet de déterminer par recherche exhaustive les possibilités pour une ville de taille donnée, et la fonction generer_visibilite_globale permet de générer les mêmes données, cette fois-ci par application de l'algorithme déterminé empiriquement. Avec la taille grandissante de la grille, les temps de calcul deviennent bien sûr rapidement incomparables.