Refactoring d'un composant logiciel (2/3)
Sommaire
Le type des contraintes
Travail à
faire : Actuellement, le type d'une
contrainte est codé par un caractère. Définir un
enum et l'utiliser.
Gérer les solutions
À ce stade, nous affichons les solutions sur la sortie standard. Nous allons améliorer ce point.
Travail à
faire : Créer une classe Solutions qui va offrir des méthodes
de gestion des solutions :
- comptage
- mémorisation (avec un record pour chaque affectation)
- affichage (ou pas)
Isoler la phase de vérification
Dans le solveur, une série de méthodes a la charge de la vérification des contraintes (check*). Nous allons les isoler dans une classe spécifique.
Travail à
faire :
- Créer une classe Checker qui va offrir des méthodes
de vérification :
- construction (pour un problème à vérifier),
- vérification,
- gestion d'un compteur de vérifications élémentaires.
- Prévoir deux tests unitaires de cette classe (cas positif et cas négatif).
- Utiliser cette classe afin de simplifier le solveur.
Amélioration : Vous pouvez changer la
classe Checker afin
qu'elle ne vérifie que les contraintes susceptibles
d'être devenues fausses (il faut lui indiquer la
variable qui a changé). Attention : la
vérification générale est toujours nécessaire,
notamment au début de la recherche. Les étapes sont
- Associer à chaque variable la liste de ses contraintes (à construire dans l'étape de fabrication).
- Utiliser une vérification centrée sur la dernière variable modifiée.
Gérer les stratégies
Note :
Une stratégie peut agir sur quatre points :
- un travail de simplification du problème à faire avant la recherche : boolean before()
- le choix de la prochaine variable à instancier : Variable chooseVariable()
- la manière d'explorer le domaine de cette variable int step(Variable v)
- le travail de vérification à faire après chaque exploration d'un domaine : boolean check()
Travail à
faire :
- Créer une interface IStrategy avec les quatre méthodes évoquées.
- Créer une classe DefaultStrategy qui implémente les choix par défaut.
- Utiliser l'interface et la classe afin de simplifier le solveur.
- Créer une deuxième classe pour la stratégie reduceAndCheckIntervalsStrategy.
La réduction d'intervalles
La réduction d'intervalles est très importante afin de diminuer l'espace de recherche et d'identifier des impasses (intervalles vides). Nous allons isoler cette étape afin de la simplifier et la tester.
Travail à
faire :
- Créer une classe Reducer qui travaille sur un problème à résoudre et propose une méthode de réduction (méthodes à récupérer depuis le solveur).
- Créer un test unitaire afin de vérifier la réduction d'un ensemble de contraintes (par exemple A+B=1000, A+B=2000).
- Créer un test unitaire afin de vérifier la réduction de la contrainte multiplicative.
La contrainte diff
Travail à
faire : Réduire la contrainte
<>. Cette réduction
n'est pas prévue. Elle n'est possible que si l'un des
deux variables est fixée et si sa valeur correspond au
min/max de l'autre variable. Voila trois exemples qui
peuvent servir à construire un test unitaire.
Réduction de X <> Y
Comment
faire ? Dans la méthode reduce() il manque le cas de la
différence. Il faut donc
X in [10,20], Y in [20,20] ---> X in [10,19], Y in [20,20] X in [10,10], Y in [10,11] ---> X in [10,10], Y in [11,11] X in [15,15], Y in [15,15] ---> X in [], Y in []
- créer une méthode reduceDiffConstraint(c) qui fait la réduction,
- appeler cette méthode dans reduce(c),
- tester les cas proposés (dans un TU).
Améliorer l'efficacité
Travail à
faire : L'opération de réduction est
coûteuse car, à chaque étape, toutes les contraintes
sont réétudiées. Améliorons ce calcul avec l'aide d'un
(observateur). La classe de réduction
va observer les variations de domaine des variables.
Nous obtenons :
Réduction de B=A+2, C=B+4 sur un
changement de A dans [5,7]
Travail à faire | Contraintes à étudier
---------------------------------------------------- | ---------------------
Réduction de la variable A | {}
--> Appel de l'observateur de A | {}
--> Ajout de B=A+2 dans la liste | {B=A+2}
Étude de la contrainte B=A+2 | {}
--> Réduction de la variable B (dans [7,9]) | {}
--> Appel de l'observateur de B | {}
--> Ajout de C=B+4 dans la liste | {C=B+4}
Étude de la contrainte C=B+4 | {}
--> Réduction de la variable C (dans [11,13]) | {}
--> Appel de l'observateur de C | {}
Aucune contrainte à étudier | {}
- Lors de l'amélioration du Checker, vous avez sûrement associé à chaque variable la liste de ses contraintes.
- Associer à chaque variable un observateur (interface Consumer<Variable>) qui va être informé de la réduction du domaine (méthode reduce).
- Maintenir, au niveau du Reducer, un ensemble de contraintes à étudier (en observant les variations de domaine des variables).