Maintaining Arc Consistency with Multiple ResiduesReportar como inadecuado

Maintaining Arc Consistency with Multiple Residues - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 CRIL - Centre de Recherche en Informatique de Lens 2 School of Computing 3 CSE - Department of Computer Science and Engineering Texas A&M University

Abstract : Exploiting residual supports or residues has proved to be one of the most cost-effective approaches for Maintaining Arc Consistency during search MAC. While MAC based on optimal AC algorithm may have better theoretical time complexity in some cases, in practice the overhead for maintaining required data structure during search outweighs the benefit, not to mention themore complicated implementation. Implementing MAC with residues, on the other hand, is trivial. In this paper we extend previous work on residues and investigate the use of multiple residues during search. We first give a theoretical analysis of residue-based algorithms that explains their good practical performance. We then propose several heuristics on how to deal with multiple residues. Finally, our empirical study shows that with a proper and limited number of residues, many constraint checks can be saved. When the constraint check is expensive or a problem is hard, the multiple residues approach is competitive in both the number of constraint checks and cpu time.

Autor: Christophe Lecoutre - Chavalit Likitvivatanavong - Scott Shannon - Roland Yap - Yuanlin Zhang -



Documentos relacionados