1996 | ReviewPaper | Buchkapitel
A labelling arc consistency method for functional constraints
verfasst von : M. S. Affane, H. Bennaceur
Erschienen in: Principles and Practice of Constraint Programming — CP96
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Numerous arc consistency algorithms have been developed for filtering constraint satisfaction problems (CSP). But, few of them considered the semantic of the constraints. Arc consistency algorithms work with a queue containing element to reconsider. Then, some constraints may be checked many times. Recently, Liu has proposed an improved specific version AC5+ of the AC5 algorithm. AC5+ deals with a subclass of functional constraints, called “Increasing Functional Constraints (IFC)”. It allows some IFC constraints of a CSP to be checked only once, when achieving arc consistency. In this paper, we propose a labelling arc consistency method (LAC) for filtering CSPs containing functional constraints. LAC uses two concepts:arc consistency and label-arc consistency. It allows all functional constraints to be checked only once, and some general constraints to be checked at most twice. Although, the complexity of LAC is still in O(ed) for functional constraints, where e is the number of constraints and d the size of the largest domain, the technique used in LAC leads to improve the performances and the effectiveness of classical arc consistency algorithms for CSPs containing functional constraints. The empirical results presented show the substantial gain brought by the LAC method.