ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 28/5 - 2014  - pp.547-569  - doi:10.3166/ria.28.547-569
TITRE
Maintenir des MDD persistants pour établir la consistance d’arc

TITLE
Maintaining persistent MDD for arc consistency

RÉSUMÉ
Dans cet article, nous présentons MDDF, un nouvel algorithme de révision de contraintes définies sous forme de diagramme de décision multivalué (MDD). En réalisant des copies partielles à la volée des MDD modifiés au cours de la recherche, MDDF parvient à une meilleure incrémentalité que MDDC proposé par Cheng et Yap (2010). La meilleure incrémentalité, couplée à la nouvelle possibilité d’exploiter les informations sur les variables modifiées permet d’éviter de parcourir systématiquement toute la structure de données à chaque filtrage, et ce malgré l’utilisation d’une file de propagation à gros grain. Outre ses performances sur les contraintes définies sous forme de MDD, les performances de MDDF sont proches de STR2 de Ullmann (2007) et Lecoutre (2011) sur les contraintes table peu dures et non structurées.


ABSTRACT
In this paper, we present MDDF, a new algorithm for revising constraints defined using multi-valued decision diagrams (MDD). MDDF copies modified parts of the MDD “on the fly” during the search of a solution, which yields a better incrementality than the previous MDDC algorithm by Cheng et Yap (2010), although coarse-grained propagation queues are still sufficient. MDDF can also be used to compress constraints defined as tables of allowed tuples. MDDF has then comparable performances to the STR2 algorithm by Ullmann (2007) and Lecoutre (2011) on loose, unstructured constraints.


AUTEUR(S)
Julien VION, Sylvain PIECHOWIAK

MOTS-CLÉS
Multi-valued Decision Diagram (MDD), Propagation, Constraint Satisfaction Problem (CSP), Tables

KEYWORDS
MDD, Propagation, CSP, Tables

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (366 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier