Arangú Lobig, MA.; Salido, MA.; Barber Sanchís, F. (2012). A FILTERING TECHNIQUE TO ACHIEVE 2-CONSISTENCY
IN CONSTRAINT SATISFACTION PROBLEMS. International Journal of Innovative Computing Information and Control. 8(6):3891-3906. http://hdl.handle.net/10251/105823
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/105823
Title:
|
A FILTERING TECHNIQUE TO ACHIEVE 2-CONSISTENCY
IN CONSTRAINT SATISFACTION PROBLEMS
|
Author:
|
Arangú Lobig, Marlene Alicia
Salido, Miguel A.
Barber Sanchís, Federico
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació
|
Issued date:
|
|
Abstract:
|
[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 ...[+]
[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.
[-]
|
Subjects:
|
Constraint satisfaction problems
,
Consistency techniques
,
2-consistency
|
Copyrigths:
|
Cerrado |
Source:
|
International Journal of Innovative Computing Information and Control. (issn:
1349-4198
)
|
Publisher:
|
ICIC International
|
Publisher version:
|
http://www.ijicic.org/ijicic-11-02011.pdf
|
Project ID:
|
info:eu-repo/grantAgreement/MICINN//TIN2010-20976-C02-01/ES/TECNICAS PARA LA EVALUACION Y OBTENCION DE SOLUCIONES ESTABLES Y ROBUSTAS EN PROBLEMAS DE OPTIMIZACION Y SATISFACCION DE RESTRICCIONES/
|
Thanks:
|
This work has been partially supported by the research project TIN2010- 20976-C02-01 (Min. de Educacion y Ciencia, Spain-FEDER).
|
Type:
|
Artículo
|