Une ville désire construire un nouveau quartier sur un immense terrain vague de forme carrée. Concrètement, il s'agit d'y construire n*n immeubles, de hauteurs variées. Les architectes et le budget de la ville imposent les contraintes suivantes :
| 4 3 2 1 | -+---------+- 4| |1 3| |2 2| |2 1| |2 -+---------+- | 1 2 2 2 |prévoit que, sur la première ligne, 4 immeubles sont visibles depuis l'Ouest et seulement 1 est visible depuis l'Est ; sur la troisième colonne, 2 immeubles sont visibles depuis le Nord, et 2 sont visibles depuis le Sud, etc.
Le plan final suivant répond au cahier des charges :
| 4 3 2 1 | -+---------+- 4| 1 2 3 4 |1 3| 2 3 4 1 |2 2| 3 4 1 2 |2 1| 4 1 2 3 |2 -+---------+- | 1 2 2 2 |
En revanche, le plan prévisionnel suivant ne peut pas être réalisé :
| 3 2 1 | -+-------+- 3| |1 2| |2 1| |3 -+-------+- | 1 2 3 |
Dans ce TD, nous allons écrire un programme qui, étant données les contraintes des architectes, propose une solution s'il en existe une. Le programme doit donc explorer l'espace des possibilités, en prenant au fur et à mesure des décisions du type : « à la position (x,y) du terrain vague, nous placerons un immeuble de h étages ».
Téléchargez l'archive td_11.tar.gz et installez-la comme d'habitude dans éclipse. Vous y trouverez un package skyscrapers, un répertoire qui contient des exemples de contraintes, et une classe Test pour tester votre code à chacun des exercices. On lancera les tests par la méthode main de Test, que vous éditerez à chaque exercice pour qu'elle appelle la méthode de test correspondant à l'exercice.
La classe fournie Pos implémente les coordonnées (x,y) d'une position du terrain (pour un terrain de longueur n les coordonnées seront comprises entre 0 et n-1).class Pos{ final int x, y; Pos(int x,int y){ this.x=x; this.y=y; } ... }
Un état de notre algorithme de recherche sera un plan du terrain, qui pourra être complètement déterminé (une valeur a été décidée pour chaque position du terrain, comme à la fin de l'algorithme), pas du tout déterminé (aucune valeur n'a été décidée dans le terrain, comme au début de l'algorithme), ou partiellement déterminé (les états intermédiaires de l'algorithme). Pour représenter n'importe lequel de ces états, on utilisera un objet de la classe abstraite State (fournie dans le fichier State.java).
Complétez, dans le fichier MyState.java, la classe MyState qui hérite de State, en choisissant une structure de donnée adaptée pour représenter l'état, et en implémentant les méthodes abstraites de State :
boolean isDefined(Pos pos); int get(Pos pos);
Complétez donc les méthodes suivantes de MyState :
void set(Pos pos, int h); void unset(Pos pos);
Enfin, complétez le constructeur MyState(int n) qui construit un plan pour un terrain n*n, où rien n'a encore été décidé.
Testez votre code avec la fonction test1 de la classe Test. Vous devez obtenir :
test seems ok
Déposez le fichier MyState.java.
abstract boolean search(); abstract State getState();La première méthode doit renvoyer true s'il existe une solution qui vérifie les contraintes imposées par le budget et les architectes, et false sinon. Dans le premier cas, un appel à getState devra renvoyer la solution. Les contraintes sont données par un objet de la classe Architects, stocké dans l'attribut archi:
final Architects archi;
boolean checkState(State cs)qui renvoie true si l'état cs satisfait les contraintes des architectes, et false sinon. Notez que cette sémantique n'a de sens que si l'état est complètement décidé. Pour l'instant, il est inutile de comprendre le reste de la classe Architects.
Implémentez, dans la classe Naive (fichier Naive.java), un algorithme d'exploration naïve, en complétant le squelette de la méthode search.
Pour cela, il sera judicieux de conserver comme attribut de la classe un état courant, initialisé dans le constructeur comme l'état complètement indéterminé, et raffiné petit à petit par des appels récursifs à search. La spécification précise de la méthode search est donc de renvoyer true si l'état courant peut être complété en un plan final qui satisfait les contraintes, et false sinon.
La recherche naïve de solution, comme expliqué en cours, consiste à énumérer tous les plans possibles qui complètent l'état courant, et vérifier à chaque fois si ce plan satisfait les contraintes. Pour faire cette énumération, rappelez-vous que votre état courant possède les méthodes de la classe State (voir ci-dessous), et procédez ainsi :
Testez avec test2. Votre algorithme doit fournir une solution pour un problème de taille 3. En revanche, il ne s'arrêtera probablement pas en temps raisonnable pour le problème suivant, de taille 4.
Déposez le fichier Naive.java.
La première chose à faire, c'est de vérifier si l'état courant, même partiellement déterminé, est viable, c'est-à-dire a une chance d'aboutir à une solution.
Notez que, lors de ces vérifications intermédiaires, il n'est pas nécessaire de revérifier tout l'état :
si l'on sait qu'il était encore viable avant la dernière modification, et que la dernière case à avoir été modifiée est (i,j), seules la ligne i et la colonne j sont maintenant susceptibles de violer les contraintes.
Pour cette raison, vous trouverez dans la classe Architects une méthode
boolean viable(State cs,Pos p)qui ne vérifie que la ligne et la colonne de p. Comme cs peut n'être qu'un état partiel, la méthode renvoie false uniquement si l'on est sûr que cs ne peut pas être complété en un état complètement déterminé qui satisfait les contraintes ; si cette complétion est possible ou qu'il est trop coûteux de le déterminer à ce stade, la méthode renvoie true. Autrement dit, true et false correspondent respectivement aux réponses "Oui, peut-être" et "Certainement pas" à la question "l'état cs a-t-il une chance d'être complété en une solution du problème ?".
Implémentez, dans la classe EarlyChecks (fichier EarlyChecks.java), un algorithme récursif d'exploration, en complétant les squelettes des méthodes :
boolean search(){...} boolean checkAndSearch(Pos p){...}qui s'appellent mutuellement :
Testez avec test3. Votre algorithme doit fournir très rapidement des solutions pour les problèmes de taille 3, 4, 5, 6, 7 ; il mettra un peu plus de temps pour les problèmes de taille 8. Il ne s'arrêtera probablement pas en temps raisonnable pour le problème de taille 9.
Déposez le fichier EarlyChecks.java.
ISet getPossibilities(Pos p) void setPossibilities(Pos p,ISet possib)Comme décrit en cours, une position est définie si son ISet est un singleton.
Action createSetAction(Pos p,int h){...}L'objet renvoyé, comme tout autre objet de la classe Action (fichier Action.java), possède deux méthodes
boolean perform() void undo()qui, dans le cas de l'objet renvoyé par createSetAction, doivent correspondre à set et unset. En effet, createSetAction(Pos p,int h) renvoie une action particulière, objet de la classe ToSet qui hérite de Action.
Vous trouverez dans Action les attributs Pos p (la position à éditer), int h (la hauteur utilisée pour l'action), MySmartState cs (l'état à éditer), ISet backup (qui conservera une copie de sauvegarde des possibilités juste avant qu'elles soient modifiées), et une implémentation de undo() (qui rétablit la copie de sauvegarde). La méthode perform, elle, est spécifique à l'action, et est donc laissée abstraite pour que les sous-classes d'Action fournissent son implémentation.
Implémentez la méthode boolean perform() de la classe ToSet (dans Action.java), selon la spécification suivante :
Modifiez maintenant votre classe EarlyChecks en une classe SmartEarlyChecks (fichier SmartEarlyChecks.java) pour
Testez avec test4. Votre algorithme sera sans doute plus lent qu'à la question précédente. Pour l'instant, aucune partie de votre code ne réduit l'ensemble des valeurs possibles pour les différentes positions du terrain. Du coup, pour chaque position, l'ensemble des valeurs possibles reste {1..n}, et l'algorithme est le même qu'à la question précédente. La maintenance des ISet étant un peu coûteuse, on perd un certain facteur de rapidité.
Déposez le fichier Action.java.
Déposez le fichier SmartEarlyChecks.java.
Complétez la classe ToForbid (fichier Action.java), héritant de Action, en implémentant sa méthode perform selon la spécification suivante:
Vous pourrez pour cela utiliser la méthode ISet remove(int x) de la classe ISet.
Complétez maintenant la classe Propagation (fichier Propagation.java) : la méthode checkAndSearch des questions précédentes est remplacée par la méthode
boolean propagateAndSearch(Pos p,Queue<Action> todo)où todo est une file d'actions à effectuer : on supposera en effet qu'elles sont conséquences directes de la dernière décision.
La méthode propagateAndSearch ne doit rappeler search que si la file todo est vide ; sinon,
La méthode search appellera propagateAndSearch en lui passant une file vide (une LinkedList<Action> vide fera l'affaire).
Testez avec test5. Votre algorithme doit avoir le même comportement qu'à la question précédente.
Déposez le fichier Action.java.
Déposez le fichier Propagation.java.
Pour l'instant, aucune partie de votre code ne place d'actions dans la file todo. C'est ce que nous allons faire dans cet exercice. Concrètement, c'est lors de la vérification de l'état partiel que l'on peut deviner que certaines actions sont conséquences directes de la dernière décision, et doivent donc être placées dans la file todo.
Il nous faut donc une classe Architects plus intelligente que celle fournie, qui possède en particulier une méthode
boolean isPermutation(State cs, Pos p, boolean b,Queue<Action> todo)qui détermine si la ligne ou la colonne de p a encore une chance d'être complétée en une permutation (immeubles de hauteurs toutes distinctes). Si b est true, il s'agit de vérifier la ligne de p, sinon, sa colonne. La méthode de la classe Architects ne touche pas à todo.
Pour améliorer cette méthode de manière à ajouter des actions dans todo, nous allons la redéfinir dans une sous-classe SmartArchitects (fichier SmartArchitects.java) de la classe Architects.
La nouvelle version de isPermutation(State cs, Pos p, boolean b,Queue<Action> todo) doit appeler la méthode de la classe mère pour effectuer la vérification, et renvoyer false si celle-ci renvoie false. Si au contraire la ligne ou colonne est viable, et qu'on a décidé que l'immeuble en position p a une hauteur h, on va reparcourir chacune des positions sur cette ligne ou colonne (différentes de p), afin de retirer h de l'ensemble des valeurs qui y sont possibles. On ne retirera pas cette valeur immédiatement, mais on placera dans la file todo des actions ToForbid qui l'effectueront. Pour créer ces actions ToForbid, vous pourrez utiliser la méthode de la classe MySmartState :
Action createForbidAction(Pos p,int h)
Enfin, pour parcourir la liste ou colonne, on s'inspirera de la boucle effectuée dans la méthode de la classe mère, et de l'usage du constructeur
Pos(int n, Pos p, int j, boolean b, boolean side)où n est la longueur du terrain, p est la position dont on considère la ligne ou colonne, j est le numéro de la position dans cette ligne ou colonne (entre 0 et n-1), b détermine si l'on parle de la ligne ou de la colonne de p, et side indique si le numéro j est compté à partir du Nord/Ouest ou à partir du Sud/Est.
Testez avec test6. Votre algorithme doit avoir de meilleures performances qu'à la question précédente.
Déposez le fichier SmartArchitects.java.