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_8.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 State (fournie dans le fichier State.java), avec les méthodes ci-dessus.
class State {
State(int n){...}
boolean isDefined(Pos pos){...}
int get(Pos pos){...}
void set(Pos pos, int h){...}
void unset(Pos pos){...}
}
Testez la code avec la fonction test0 de la classe Test. Vous devez obtenir :
test0 seems ok
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 test1. 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 le squelette de la méthode search. Cette méthode search suppose que l'état courant est viable partout ; elle prendra alors une décision pour une position non décidée, et elle appellera viable pour vérifier la ligne et la colonne pour cette position (pas nécessairement complètement remplies), avant de se rappeler (récursivement) pour continuer à compléter l'état.
Testez avec test2. 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){...}
de SmartState.
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), SmartState 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 test3. 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 les méthodes ISet remove(int x) et boolean isEmpty() de la classe ISet.
Complétez maintenant la classe Propagation (fichier Propagation.java). Il est conseillé d'avoir deux méthodes :
boolean search() boolean propagateAndSearch(Pos p,Queue<Action> todo)qui s'appellent mutuellement.
La méthode propagateAndSearch prend comme argument une position p qui vient d'être modifiée (on a pas encore vérifié la viabilité de cette modification, et l'on a pas encore calculé ses conséquences), ainsi qu'une file todo d'actions à effectuer.
La méthode search est la même qu'à la question précédente, sauf qu'au lieu de directement vérifier la viabilité de l'état et de s'appeler récursivement, elle appelle propagateAndSearch en lui passant la position où une décision vient d'être prise et une file d'actions vide (une LinkedList<Action> vide fera l'affaire).
La méthode propagateAndSearch va alors,
Testez avec test4. 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 SmartState :
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)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), et b détermine si l'on parle de la ligne ou de la colonne de p.
Testez avec test5. Votre algorithme doit avoir de meilleures performances qu'à la question précédente.
Déposez le fichier SmartArchitects.java.