ACCUEIL

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

L'Objet

1262-1137
logiciel, bases de données, réseaux
Publication abandonné
 

 ARTICLE VOL 9/RSTI1 - 2003  - pp.267-280
TITRE
De AC3 à AC7

RÉSUMÉ
La consistance d'arc joue un rôle central dans la résolution de Problèmes de Satisfaction de Contraintes (CSPs). Récemment, un même algorithme appelé AC2001 et AC3.1 a été présenté indépendamment par leurs auteurs respectifs. Cet algorithme qui est considéré comme une amélioration de AC3 a l'avantage d'être simple (à implémenter) et compétitif. Cependant, il ne prend pas en compte la bidirectionalité des contraintes comme le fait AC7. Dans ce papier, nous abordons cette question en proposant deux algorithmes appelés AC3.2 et AC3.3 qui bénéficient des bonnes propriétés à la fois de AC3 et de AC7. Plus précisément, AC3.2 est un algorithme général qui exploite partiellement la bidirectionalité des contraintes tandis que AC3.3 est un algorithme binaire qui exploite totalement la bidirectionalité. Néanmoins, lorsque la consistance d'arc est maintenue pendant la recherche d'une solution, MAC3.2 (grâce à un effet de mémoire), s'avère plus efficace que MAC3.3 à la fois en termes de tests de consistance et de temps CPU. Comparé à MAC2001/3.1, nos résultats expérimentaux montrent que MAC3.2 économise environ 50% des tests de consistance et, en moyenne, 15% du temps CPU.


ABSTRACT
Arc consistency plays a central role in solving Constraint Satisfaction Problems. Recently, an algorithm called AC2001 and AC3.1 has been independently presented by their authors. This algorithm which is considered as a refinement of the basic algorithm AC3 has the advantage of being simple (to implement) and competitive. However, it does not take into account constraint bidirectionality as AC7 does. In this paper, we address this issue, and, in particular, introduce two new algorithms called AC3.2 and AC3.3 which benefit from good properties of both AC3 and AC7. More precisely, AC3.2 is a general algorithm which partially exploits bidirectionality whereas AC3.3 is a binary algorithm which fully exploits bidirectionality. It turns out that, when Maintaining Arc Consistency during search, MAC3.2, due to a memorization effect, is more efficient than MAC3.3 both in terms of constraint checks and CPU time. Compared to MAC2001/3.1, our experimental results show that MAC3.2 saves about 50% of constraint checks and, on average, 15% of CPU time.


AUTEUR(S)


MOTS-CLÉS
problèmes de satisfaction de contraintes, consistance d'arc.

KEYWORDS
constraint satisfaction problems, arc consistency.

LANGUE DE L'ARTICLE
Français

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



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
made by WAW Lavoisier