A filtering technique to achieve 2-consistency in constraint satisfaction problems
| Autor: | Arangú Lobig, Marlene Alicia, Salido, Miguel A., Barber Sanchís, Federico |
|---|---|
| Předmět: | |
| Zdroj: | Scopus-Elsevier RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia instname |
| Popis: | [EN] Arc-Consistency algorithms are the most commonly used ltering techniques to prune the search space in Constraint Satisfaction Problems (CSPs). 2-consistency is a similar technique that guarantees that any instantiation of a value to a variable can be consistently extended to any second variable. Thus, 2-consistency can be stronger than arc-consistency in binary CSPs. In this work we present a new algorithm to achieve 2- consistency called 2-C4. This algorithm is a reformulation of AC4 algorithm that is able to reduce unnecessary checking and prune more search space than AC4. The experimental results show that 2-C4 was able to prune more search space than arc-consistency algo- rithms in non-normalized instances. Furthermore, 2-C4 was more efficient than other 2-consistency algorithms presented in the literature. This work has been partially supported by the research project TIN2010- 20976-C02-01 (Min. de Educacion y Ciencia, Spain-FEDER). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|