|<
<< Page précédente
1
Page suivante >>
>|
5
10
15
20
25
30
35
40
documents par page
Tri :
Date
Editeur
Auteur
Titre
Ecole Nationale Supérieure de l'Aéronautique et de l'Espace
/ 20-03-1995
Lesaint David
Voir le résumé
Voir le résumé
Le formalisme des problèmes de satisfaction de contraintes (CSP) et les méthodes associées offrent un cadre théorique de plus en plus utilisé pour traiter les problèmes d'Intelligence Artificielle. Toutefois, la plupart des méthodes se concentrent sur le calcul d'une solution ce qui constitue un objectif trop limité. Nous introduisons dans cette thèse la notion de relation complète qui permet de calculer et de représenter de façon compacte des ensembles de solutions. Nous proposons d'abord une méthode qui génère une partition des solutions d'un CSP binaire par relations complètes Cette méthode met en œuvre une décomposition structurelle et une décomposition des contraintes par identification de symétries (calcul d'interchangeabilité). Sa complexité, qui est fonction de la taille d'un transversal minimal du graphe, n'est pas liée au
nombre de solutions, à l'inverse des méthodes énumératives. Une évaluation expérimentale sur des problèmes jouets en démontrent le bon comportement. Nous montrons ensuite que cette méthode relève d'un schéma plus général qui consiste a résoudre le CSP dual d'un CSP pour obtenir une partition de ses solutions. Il est possible de construire un dual binaire pour tout CSP binaire : certaines classes polynomiales s'avèrent alors êtres stables par passage au dual binaire, assurant ainsi un coût polynomial pour le calcul d'un sous-ensemble des solutions. Nous proposons enfin une extension de l'algorithme backtrack standard pour le calcul de quelques solutions. Expérimentée sur problèmes aléatoires, cette extension entraîne un surcoût modeste par rapport au calcul d'une seule solution bien qu'elle fournisse en meilleur cas un
nombre exponentiel de solutions.
|
Texte intégral
|<
<< Page précédente
1
Page suivante >>
>|
5
10
15
20
25
30
35
40
documents par page