Embed Size (px)
Citation preview
Travail d'étude et de recherche
VISUALISATION DE RESOLUTION DE PROBLEMES PAR SATISFACTION DE CONTRAINTES
Alexandre KOWALMaster 1 Mathématiques InformatiqueFaculté des sciences Jean Perrin de Lens
Encadrant:Stéphane CARDON
Table des matières
1) Introduction
1.1: Description du sujet
1.2: Ce qui a déjà été fait
1.3:Utilisation de la librairie QT4
1.3.1: Les signaux
1.3.2: Compilation
2) Modélisation
2.1: Analyse du problème
2.1.1: Recueil des besoins
2.1.2: Diagramme des cas d'utilisation
2.1.3: Diagrammes de séquences
2.1.3.1: Chargement d'un problème
2.1.3.2: Résolution automatique
2.1.3.3: Résolution manuelle
2.2: Rappel
2.2.1: Filtrage
2.2.1.1: Revise (consistance d'arc)
2.2.1.2: AC1
2.2.1.3: classe Filtre
2.2.2: Solveur
2.3: Diagramme principal
2.3.1: Explication des classes
2.3.1.1: Interface IParametres
2.3.1.2: Interface Probleme
2.3.1.3: Interface IFabrique
2.3.1.4: Classe Problemes
2.3.1.5: Boundary GProblèmes
2.3.1.6: Boundary GMain
2.4: Communication entre le viewer et le solveur
2.4.1: Le Pattern Observer
2.4.2: Définition
2.4.3: La classe IObserver
2.4.4: le solveur
2.5: La classe Viewer
2.5.1: L'historique pour la classe Viewer
2.6: Exemple concret d'implémentation de problèmes
2.6.1: Le problème des NReines
2.6.2: Rappel
2.6.3: Création du CSP relatif au problème
2.6.3.1: Création de la classe Nreines
2.6.4: Création du viewer personnalisée
2.6.5: Enregistrement du problème dans la liste des problèmes
2.7: Séquence de lancement d'un problème
2.8: Représentation sous forme de graphe
3) Conclusion
3.1: Améliorations
3.2: Bug
1) Introduction:
1.1: Description du sujet
Le but de ce sujet est de réaliser une interface graphique permettant de visualiser sous forme de graphe la solution d'un CSP (réseau de contraintes binaires) car une image est plus parlante que des données brutes. Ce graphe devait pouvoir être interactif de sorte que l'utilisateur puisse choisir les valeurs données à chaque variable.
Les problèmes peuvent aussi avoir une représentation plus concrète encore que le graphe avec, comme par exemple, le problème des NReines pouvant être soit affiché sous forme de graphe ou alors sous la forme d'un échiquier.
1.2: Ce qui a déjà été fait
Pour ce sujet, une partie du travail à déjà été réalisée par un autre étudiant l'année dernière.
Cet étudiant avait réalisé les diagrammes de base concernant la représentation interne de CSP, ainsi qu'un loader de CSP non finalisé, un algorithme de filtrage et un modèle de solveur.
Nous ferons un petit rappel de tout ceci dans un autre chapitre. Pour de plus amples informations se référer au rapport de stage de Sébastien RAMON « réalisation objet d'un minisolveur CSP »
1.3 : Utilisation de la librairie QT4
Pour ce stage, deux librairies pouvaient être utilisées : GTK ou QT.
L'avantage de QT par rapport à GTK fut qu'elle proposait des composants puissants pour l'affichage (QGraphicsView) ainsi qu'un composant XML permettant de charger les fichiers de ce type facilement et de plus un système de création de plugins très facile d'utilisation.
1.3.1: Les signaux
La communication entre objets dans QT se fait par un mécanisme de « signals and slots ». Cela ressemble au pattern observer.
Un signal est connecté à un slot par la méthode connect.
On peut connecter autant de slots que l'on souhaite à un même signal. Lorsqu'un signal est émis par un objet, tous les slots lui étant connectés sont appelés.
La méthode connect permet de faire la liaison entre les signaux et les slots.
Cidessous un schéma explicatif du fonctionnement de ce mécanisme.
1.3.2: Compilation
La compilation d'un programme QT s'effectue en 3 étapes:
qmake projet //crée un fichier *.pro utilisé par qmake
qmake //permet de créer un makefile à partir du *.pro
make //effectue la compilation et la création de l'exécutable
Illustration : signaux et slots en QT4.3
2) Modélisation
2.1: Analyse du problème
2.1.1: Recueil des besoins
Le but de l'application est de charger des problèmes au formats XML ou ceux intégrés directement dans le programme, pour ensuite les résoudre.
Il fallait donc trouver de quelle façon les représenter. Après réflexion, il a été décidé que chaque problème pourrait avoir deux modes de vue différentes.
● Mode standard: représentant le problème sous forme de graphe.
● Mode personnalisé: représentant le problème sous une autre forme qu'un graphe.
Pour cela va être créée une classe Viewer pour représenter cette idée.
Une autre demande avait été faite, il fallait aussi ajouter de l'interactivité lors de la résolution des problèmes, là aussi deux modes devaient être intégré.
● Mode automatique: la résolution se fait en temps réelle devant nos yeux.
● Mode manuel: l'utilisateur affecte lui même les variables du problème.
On comprend ici que pour le mode automatique, le solveur du problème doit communiquer avec le Viewer pour que l'affichage puisse changer en temps réel. De même, en poussant la réflexion plus loin, en mode manuel, l'utilisateur doit communiquer également avec le solveur.
Ici nous voyons donc que le Viewer devra communiquer avec le solveur. Pour cela on intégrera le concept de design pattern observer qui répondra parfaitement à nos besoins.
Concernant le mode manuel, il se pourrait que l'utilisateur de l'application s'aperçoive qu'il a choisi une mauvaise valeur pour des variables du problème et donc qu'il souhaiterai revenir en arrière pour corriger son erreur. Pour cela un historique des actions sera réalisé et la classe viewer devra donc l'implémenter.
En ce qui concerne les problèmes, il ne sera pas possible de choisir le solveur désiré lors de la sélection du problème à résoudre. De ce fait le solveur à utiliser sera stocké dans chaque dérivation de la classe Problème.
Chaque problème pouvant être paramétré si besoin est, une classe s'occupant de recueillir ces informations sera introduite.
Toutes les interfaces et classes citées précédemment seront en fait codées en tant que classes
abstraites dans lesquelles une majorité de méthodes auront une implémentation de base afin de simplifier la programmation lors de l'ajout de problèmes.
2.1.2: Diagramme des cas d'utilisation
Diagramme des cas d'utilisation
2.1.3: Diagrammes de séquences
2.1.3.1: Chargement d'un problème
Ce diagramme explique les principales étapes réalisées lors du chargement d'un problème.
Diagramme de séquence de chargement d'un problème
2.1.3.2: Résolution automatique
Lorsque l'utilisateur clique sur le bouton de résolution automatique, le viewer appelle la méthode solve du solveur et celuici envoie des messages de mise à jour du viewer pour qu'il puisse se rafraîchir.
Diagramme de séquence de résolution automatique d'un CSP
2.1.3.3: Résolution manuelle
L'utilisateur demande au viewer de modifier la variable souhaitée (par l'intermédiaire du solveur).
Diagramme de séquence de résolution manuelle d'un CSP
2.2: Rappel
Pour pouvoir visualiser l'effet d'une affectation effectuée par un utilisateur (l'affectation d'une variable implique la modification du domaines des autres variables), il nous faut un filtre.
Cette partie va fournir les rappels pour expliquer le fonctionnement de l'affectation et ses effets sur le problème.
Un problème de satisfaction de contraintes peut être représenté par un triplet {X,D,C} où:
– X = { v1 , v2 ,..., vn } est un ensemble de n variables;
– D = { d 1 , d 2 ,..., d n } est un ensemble des n domaines finis associés aux variables; chaque d i est de cardinalité finie.
– C = { c1 , c2 ,..., ce } est l'ensemble des e contraintes, chaque contrainte c i est définie par un couple ( v i , r i ):
– v i est une séquence de variables x i1 ,... , xit ∈X sur lesquelles porte la contrainte c i .
– r i est une relation définie par un sousensemble du produit cartésien d i1 x ... x d it des domaines associés aux variables de v i . Il représente les nuplets de valeurs autorisées pour ces variables.
2.2.1: Filtrage
Le filtrage consiste en l'élimination d'éléments dont on est assuré qu'ils ne peuvent figurer dans une quelconque solution (valeurs ou nuplets de relation). Il tend donc vers la simplification du problème par réduction de l'espace de recherche.
Méthode de filtrage:
Nous allons voir ici la méthode de filtrage qui a été implémentée pour cette application.
2.2.1.1: Revise (consistance d'arc)
La procédure Revise C ij , d i , d j retire du domaine de x i toutes les valeurs sans support pour la contrainte C ij et retourne un booleen indiquant si le domaine de x i a été modifié.
2.2.1.2: AC1
Le filtrage par consistance d'arc AC1 consiste à appliquer la consistance d'arc Revise(Cij,di,dj) sur toutes les contraintes (propagation de contraintes) jusqu'à ce que plus aucune réduction ne s'effectue. De cette manière on palie au problème de la simple application de Revise sur tous les couples de variables.
2.2.1.3: classe Filtre
Ceci est l'interface à implémenter pour créer de nouveau filtre.
Pour cela, il suffit juste de redéfinir la méthode filtrer dans une classe fille.
2.2.2: Solveur
Son rôle est de résoudre un problème.
Lors de la phase de résolution, à chaque changement de valeur pour une variable, un algorithme de filtrage est lancé.
Pour créer un nouveau solveur il suffit juste de redéfinir la méthode solve dans une classe fille.
2.3: Diagramme principal
2.3.1: Explication des classes
2.3.1.1: Interface IParametres
Cette interface est utilisée pour ajouter des paramètres à un problème. Une fonction permet de créer le QWidget qui représentera cette classe dans l'interface graphique.
2.3.1.2: Interface Probleme
Classe abstraite dont tous problèmes doivent dériver.
Utilisation:
Deux méthodes sont à redéfinir pour créer un problème:
//c'est ici que l'on crée le réseau CSP relatif à notre problème, à noter que les paramètre sont //stoqués dans la variable _parametre virtual void creer();
et
//retourne le viewer du problème virtual Viewer* getViewerPersonnalise();
2.3.1.3: Interface IFabrique
Permet de centraliser la création d'objets de même type dans un même endroit pour avoir un code plus commode à utiliser.
Redéfinir:
//indique si l'objet donc on entre le nom possède des paramètres. //sera utile pour savoir quelle méthode d'instanciation utiliser virtual bool possedeParametres(const QString & name) = 0;
//retourne un void* correspondant à l'objet dont on a donné son nom à la fonction. //Les noms des objets instanciables sont fournis par la méthode getListe
virtual void* instancie(const QString & name) = 0;
2.3.1.4: Classe Problemes
C'est à l'intérieur de cette classe que les problèmes nouvellement créés sont ajoutés.
=> Cette classe ne contient que la liste des problèmes nouvellement créés. A chaque nouveau problème, une ligne est ajoutée dans la méthode instancie(const QString & name) afin que le problème soit accessible à l'utilisateur.
2.3.1.5: Boundary GProblemes
Cette classe affiche la boite de dialogue de sélection et création d'un problème.
2.3.1.6: Boundary Gmain
C'est la fenêtre principale de l'application, elle permet le chargement de la liste des problèmes, et l'affichage des viewers se fait dedans.
Dans la barre des menus, le menu édit permet d'accéder à la fonction rollback utilisée pour des retours arrières lors de manipulation de problèmes.
2.3: Communication entre le viewer et le solveur
Le solveur occupe une place importante dans les interactions avec l'utilisateur.
Chaque fois que l'on voudra modifier la valeur d'une variable, une « autorisation » devra être demandée au solveur pour qu'il vérifie si l'affectation est correcte.
Deux cas sont possibles:
– soit l'affectation n'est pas possible et donc rien ne se passe
– soit l'affectation est possible et le solveur enregistre cela dans son historique, puis émet un signal pour prévenir le viewer que l'affectation s'est passée et que l'affichage peut être modifié en conséquence.
Lors d'une annulation d'une action, un message sera envoyé au solveur qui se remettra dans son état précédent et émettra un signal pour prévenir le viewer que le rollback a bien eu lieu.
Pour réaliser tout cela le design pattern Observer a été utilisé
2.4.1: Le Pattern Observer
2.4.2: Définition
Le design pattern observateur/observable est utilisé pour envoyer un signal à des modules qui jouent le rôle d'observateur. En cas de notification, les observateurs effectuent alors l'action adéquate en fonction des informations qui parviennent depuis les modules qu'ils observent (les "observables").
Pour cette application le Subject sera le solveur et l'Observer sera le viewer.
2.4.3: La classe IObserver
Elle est implémentée par la classe Viewer.
class IObserver: {
public:virtual void update(int id_variable, int valeur, ISolveur::State state) = 0;
};
Cette fonction est appelée par le Solveur à chaque fois qu'il change d'état.
Nous reviendrons sur cette classe plus tard.
2.4.4: le solveur
class ISolveur : public QObject, public Historique {
public:
enum State{
State_Solving, State_Solved, State_Unsolved, State_Rollback, State_Commit };
ISolveur(Reseau *reseau);
virtual ~Isolveur();
virtual void solve() = 0;
void attach(IObserver *obs);
Reseau* getReseau();
virtual void setVariable(int id_variable, int valeur) = 0;
virtual void valueChanged(int id_variable, int valeur, State state);
};
les méthodes:
virtual void solve() = 0;
réalise la résolution du problème
void attach(IObserver *obs);
permet d'attacher les observer (notre viewer) à avertir en cas de modification du solveur.
Reseau* getReseau();
retourne le réseau(CSP) sur lequel porte la résolution
virtual void setVariable(int id_variable, int valeur) = 0;
permet de changer la variable d'indice id_variable en lui mettant valeur comme nouvelle affectation
Cette méthode appelle valueChanged pour avertir les observateurs (le viewer) du changement effectué
virtual void valueChanged(int id_variable, int valeur, State state);
C'est la méthode qui va se charger d'avertir chaque observer que le Solveur vient d'effectuer une certaine action de type State.
Les actions du solveurs sont :
State_Solving: le solveur est en cours de calcul State_Solved: la solution vient d'être trouvée State_Unsolved: pas de solution trouvée State_Rollback: un rollback viens d'être effectué State_Commit: un commit viens d'être effectué
ces états seront utilisées par les viewers personnalisés pour rafraîchir le visuel du problème correctement et pour d'autres choses que nous verrons plus tard.
2.5: La classe Viewer
Classe de base pour visualiser un CSP sous une forme plus conviviale et possédant les mécanismes pour communiquer avec le solveur
class Viewer : public QWidget, public Historique, public IObserver {protected:
Viewer(ISolveur *solveur);
public:void desireNewAffectation(int id_variable, int valeur);
virtual update(int id_variable, int valeur, ISolveur::State state) = 0;
virtual void paintEvent( QPaintEvent * event) = 0;
};
La classe Viewer est commune à toute représentation de problèmes que se soit sous forme de graphe ou autre.Elle entretient une relation étroite avec le solveur car toutes les communications passent par elle.
Deux méthodes principales permettent cette communication:
Envoie requête d'affectation de variable:
Lorsque l'on souhaite modifier la valeur d'une variable, il suffit d'appeler la méthode:
void desireNewAffectation(int id_variable, int valeur)
en paramètres:
id_variable: l'indice de la variable sur laquelle va porter la modification
valeur: la nouvelle valeur que l'on souhaite lui donner
Lorsque l'on envoie une requête de modification d'une variable il faut savoir que parfois cette affectation n'est pas possible (violation de contrainte). C'est ici que la seconde méthode vient jouer un rôle.
Réception de la validation de l'affectation:
Comme expliqué cidessus une modification de variable n'est pas toujours possible. Si une affectation est correcte la méthode qui suit est appelée:
void update(int id_variable, int valeur, ISolveur::State state) ;
en paramètres:
id_variable: l'indice de la variable sur laquelle va porter la modification
valeur: la nouvelle valeur que l'on souhaite lui donner
state: l'état dans lequel est le solveur
Cette méthode est virtuelle pour qu'on puisse la redéfinir pour gérer correctement la mise à jour du Qwidget.
2.5.1: L'historique pour la classe Viewer
Le viewer réalisant l'interface Historique, à chaque fois qu'une modification de variable est faite cela est immédiatement enregistré pour pouvoir faire des retours arrières.
2.6: Exemple concret d'implémentation de problème
2.6.1: Le problème des NReines
2.6.2: Rappel
Il s'agit de placer n reines sur un échiquier (n x n) sans qu'elles se menacent. Deux reines ne doivent pas se trouver sur la même ligne, sur la même colonne ou sur la même diagonale.
Illustration : solution possible avec 8 reines
2.6.3: Création du CSP relatif au problème
2.6.3.1: Création de la classe NReines
On dériver la classe problème pour y redéfinir la méthode creer et getViewerPersonnalise :
class NReines : public Probleme {public:
NReines();
virtual void creer();
virtual Viewer* getViewerPersonnalise();
};
dans cette méthode on peut voir un exemple utilisant un objet de type IPrametres vu dans le point 2.1.1.1.
NReines::NReines() {//Création des données qui figureront dans la boîte de paramétrage du problème lors de sa sélection
//création d'un domaineQList<QString> domaineParametre; //valeurs possiblesdomaineParametre << "4" << "7" << "8"; //ajout à la liste des paramètres (_parametres est de type Iparametres, se trouve dans la classe
//probleme_parametres.ajouterParametre("nb reines:",COMBO_BOX, domaineParametre);
}
void NReines::creer() {//création d'un csp videBFabrique *reseauFactory = Bfabrique::get_instance();_reseau = reseauFactory>creer();
//récupération du nombre de reines désiréint nbReines = parametres.getValeurParametre("nb reines:").toInt();
//CREATION DES VARIABLES, DES CONTRAINTES ICI
}
Viewer* Nreines::getViewerPersonnalise() {
//retourne le viewer personnaliséreturn new NReinesViewer(reseau);
}
2.6.4: Création du viewer personnalisée
On dérive notre viewerNReines de la classe Viwer et réimplémente les méthodes paintevent et update.
Une méthode pour détecter les clics sur la souris sera aussi nécessaire
class ViewerNReines : public Viewer {
public:
ViewerNReines(ISolveur *solveur): Viewer(solveur) {}
protected:virtual void update(int id_variable, int valeur, ISolveur::State state);virtual void paintEvent( QPaintEvent * event);
void mousePressEvent ( QMouseEvent * event );
};
void ViewerNReines::paintEvent(QPaintEvent * event){
drawEchiquier();//dessine l'échiquier
drawCaseAutorisees();//illumine les cases autorisées pour la reine courante
drawReines();//dessine les reines présentes sur l'échiquier
}
//gère les clics sur les cases
void ViewerNReines::mousePressEvent( QMouseEvent * event ){
valeur = valeurDeLaCase();//retourne le numéro de la case cliquée. 1 en cas d'erreur
if(valeur != 1)
desireNewAffectationl(id_courante_reine, valeur);
}
//appelée par le solveur après avoir effectué une action
void ViewerNReines::update(int id_variable, int valeur, ISolveur::State state){
switch(state) {
case ISolveur::State_Solving:
//le solveur vient de valider une modification du graphe
id_courante_reine++;//on passe à la reine suivante
break;
case ISolveur::State_Solved:
QMessageBox::warning(NULL, "NReines","Une solution a été trouvée",
QMessageBox::Ok);
break;
case ISolveur::State_Solved:QMessageBox::warning(NULL, "NReines","problème inconsistant",
QMessageBox::Ok);
break;
case ISolveur::State_Rollback:
//un retour arrière a été fait on retourne vers la reine précédente
id_courante_reine;
break;
default:;
}repaint();
}
2.6.5: Enregistrement du problème dans la liste des problèmes
Une classe Problème existant déjà il suffit de la modifier pour prendre en compte le nouveau problème
Problemes::Problemes(){
//ajout du prblème des NReines dans la liste des problèmes
_lesNomsProblemes << "ColoGraph";
_lesNomsProblemes << "NReines";
}
//retourne le problème dont le nom est passé en paramètre
void* Problemes::instancie(const QString & name){
if(name == "ColoGraph") return new ColoGraph;
if(name == "NReines") return new NReines;
return NULL;
}
2.7: Séquence de lancement d'un problème
Lors du clic sur Fichier>liste CSP... la fenêtre cidessous s'affiche.
Dans le 1er encadré liste problèmes :
Choix du problème: liste tous les problèmes disponibles (NReines,ColoGraph...).
Visualisation: au maximum 2 types de visualisation sont disponibles :
Standard: affiche le problème sous forme de graphe.
Personnalisée: affiche le problème sous une forme plus élégante (ex: pour les NReines l'affichage serait un échiquier sur lequel des images de pions de reines s'afficheraient)
Lors du clic sur valider, la liste des paramètres du problème s'affiche nous permettant de choisir les valeurs désirées.
Lors du clic sur générer, le viewer est généré et passé à la fenêtre principale.
Représentation personnalisée du problème des NReines
2.8: Représentation sous forme de graphe
Cette partie montre l'affichage standard de tous problèmes, c'est à dire sous forme de graphe.Celuici utilise l'algorithme des graphes élastiques basé sur les forces d'attraction et de répulsion exercées sur des nœuds.
Utilisation:
La partie gauche de l'image cidessous montre les variables du graphe, il suffit de choisir une valeur pour chaque et d'appuyer sur le commit correspondant pour valider l'action.
Le graphique réagira automatiquement en illuminant le nœud assigné.
Lorsqu'une solution est trouvée une boite de dialogue apparaît pour vous prévenir.
Représentation sous forme de graphe d'un problème
3)Conclusion
3.1: Améliorations
Le processus de création de problèmes dans ce modèle est assez lourd. En effet pour en ajouter un nouveau il faut modifier la classe Problemes pour qu'il se retrouve dans la liste de sélection. Mais le désavantage majeur est la recompilation obligatoire de toute l'application pour que le problème soit réellement intégré dans l'application ce qui est très lourd.
Une solution serait de créer un système de plugin pour éviter tout cela. Chaque problème serait donc un plugin et il suffirait de ne compiler que ce problème et de le placer dans un dossier « plugins » pour que le programme puisse le charger automatiquement.
3.2: Bug
Un bug n'a pas pu être corrigé à temps, celuici concerne les listeurs des domaines des variables. De ce fait des erreurs lors des rolback peuvent survenir. Cela a empêché d'implémenter la méthode solve du solveur utilisé.
