Refactoring d'un composant logiciel (3/3)
La stratégie alwaysReduce
Travail à
faire : Nous allons maintenant
construire une stratégie (alwaysReduce) qui consiste à réduire
le problème à chaque étape. Contrairement aux autres
stratégies, cette dernière est susceptible de modifier
plusieurs domaines à chaque étape. Un travail de
sauvegarde/restauration est donc nécessaire.
- Prévoir une classe Backup qui se charge d'une sauvegarde et de l'opération de restauration associée.
- Il faut sans doute modifier l'interface IStrategy pour prendre en compte cette spécificité (void backup() et void restore()).
- Proposer une implémentation de cette stratégie et vérifier sur un problème que cette stratégie est bien plus efficace.
Travail à
faire : Pour tirer partie de cette
stratégie et de la réduction de la contrainte
diff, vous pouvez tester
la résolution du problème des N-Reines avec le code ci-dessous (92
solutions pour 8 reines).
public ISolver makeQueens(int n) { ISolver solver = new Solver(); var queens = new Variable[n]; // diagonals var diagonals1 = new Variable[n]; var diagonals2 = new Variable[n]; for (int i = 0; i < n; i++) { queens[i] = solver.newVar("R" + i, 1, n); diagonals1[i] = solver.expression(queens[i], "+", i); diagonals2[i] = solver.expression(queens[i], "-", i); } solver.addAllDiffRelation(queens); solver.addAllDiffRelation(diagonals1); solver.addAllDiffRelation(diagonals2); solver.alwaysReduceStrategy(); solver.setVerbose(false); return solver; }
Un problème d'optimisation
Cet exercice est optionnel mais très intéressant !
Nous allons maintenant changer le fonctionnement de notre solveur en ajoutant la minimisation de la valeur d'une variable. Par exemple, pour le problème ci-dessous, la plus petite valeur de COST est 330 pour X=70 et Y=30.
0 <= X, X <= 70, 0 <= Y, Y <= 70, X + Y = 100, COST = (3 * X) + (4 * Y)
Travail à
faire : Nous allons traiter cette
nouvelle fonctionnalité comme une nouvelle
stratégie :
- Préparer une classe OptimizationStrategy qui hérite de AlwaysReduceStrategy.
- Cette stratégie va conserver la valeur courante minimale de la variable à minimiser (variable qu'elle doit donc connaître).
- A chaque solution, cette valeur est éventuellement mise à jour.
- A chaque réduction, cette stratégie va réduire le domaine de la variable pour ne pas autoriser des valeurs plus grandes que celles déjà trouvées. Ainsi, à chaque étape, nous améliorons notre objectif.
- Amélioration : Comment faire pour ne plus renvoyer les solutions non-optimales ?
Travail à
faire : Considérons le problème
d'affectation ci-dessous. Nous avons des tâches à faire
et des agents pour les faire. Chaque tâche est faite
par un seul agent qui ne peut faire qu'au plus une
tâche. Cette affectation entraîne un coût qui est
détaillé dans le tableau ci-dessous.
Problème : quelle
est l'affection des tâches aux agents qui minimise le
coût ? Aidez-vous de la méthode ci-dessous afin de
construire un test unitaire qui va trouver la solution
de ce problème.
Agent 1 Agent 2 Agent 3 Agent 4 tâche 1 : 8 5 9 9 tâche 2 : 4 2 6 4 tâche 3 : 7 3 7 8
public ISolver buildAssignmentProblem(int[][] costs) { var solver = new Solver(); int nbTasks = costs.length; int nbAgents = costs[0].length; Variable[][] matrix = new Variable[nbTasks][nbAgents]; // create nbTasks * nbAgents variables 0..1 for (int t = 0; t < nbTasks; t++) { for (int a = 0; a < nbAgents; a++) { matrix[t][a] = solver.newVar("T" + t + "A" + a, 0, 1); } } // each task have one agent var zero = solver.newConstant(0); for (int t = 0; t < nbTasks; t++) { var sum = zero; for (int a = 0; a < nbAgents; a++) { sum = solver.expression(sum, "+", matrix[t][a]); } solver.addRelation(sum, "=", 1); } // each agent have at most one task for (int a = 0; a < nbAgents; a++) { var sum = zero; for (int t = 0; t < nbTasks; t++) { sum = solver.expression(sum, "+", matrix[t][a]); } solver.addRelation(sum, "<=", 1); } // compute cost var cost = zero; for (int t = 0; t < nbTasks; t++) { for (int a = 0; a < nbAgents; a++) { cost = solver.expression(cost, "+", matrix[t][a], "*", costs[t][a]); } } var varCost = solver.newVar("cost"); solver.addRelation(cost, "=", varCost); solver.setVerbose(false); solver.alwaysReduceStrategy(); // Code a adapter pour minimiser cost .... .... return solver; }
Modalités de rendu via etulab
- Le rendu de votre projet Solver est à faire pour le jeudi 23 octobre 2025 à 23h59. Il faudra que le dépôt git sur etulab soit à jour et que Jean-Luc Massat (identifiant massat) soit membre du projet avec des droits au moins égal à reporter.
- L'ajout de membre se fait via manage / members dans le menu de votre projet sur etulab, puis en cliquant sur le bouton invite members.
- Important : Vous devrez déclarer votre projet dans un questionnaire prévu sur Ametice.
- Votre projet devra contenir à sa racine un fichier README.md contenant les informations sur ses membres et les emprunts réalisés. Le format du fichier devra être le suivant :
# Solver ## Membres du projet - NOM Prénom du premier membre - NOM Prénom du deuxième membre (si applicable) ## Description des emprunts - Utilisation de ChatGPT pour les classes : `Main.java`, ... - ...