2-C3OP: An Improved Version of 2-Consistency
| Autor: | Miguel A. Salido, Marlene Arangú, Federico Barber |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Complexity of constraint satisfaction
Constraint learning Mathematical optimization Computer science Backtracking Hybrid algorithm (constraint satisfaction) Binary constraint Constraint satisfaction Min-conflicts algorithm Constraint graph AC-3 algorithm Constraint satisfaction dual problem Constraint logic programming Constraint programming Local consistency Difference-map algorithm Algorithm Constraint satisfaction problem |
| Zdroj: | ICTAI |
| DOI: | 10.1109/ictai.2009.54 |
| Popis: | Nowadays, many real problems can be modeled as constraint satisfaction problems. Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction. In this paper we present a new algorithm, called 2-C3OP, that achieves 2-consistency in binary and non-normalized CSPs. This algorithm is a reformulation of 2-C3 algorithm and it performs the constraint checks bidirectionally using inference. The evaluation section shows that 2-C3OP achieve 2-consistency like 2-C3 and it is 40% faster. Furthermore, 2-C3OP performs less number of constraint checks than both AC3 and 2-C3. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|