zbMATH — the first resource for mathematics

A path-optimal GAC algorithm for table constraints. (English) Zbl 1327.68220
De Raedt, Luc (ed.) et al., ECAI 2012. 20th European conference on artificial intelligence, Montpellier, France, August 27–31, 2012. Proceedings. Including proceedings of the 7th conference on prestigious applications of artificial intelligence (PAIS-2012) and the system demonstrations track. Amsterdam: IOS Press (ISBN 978-1-61499-097-0/pbk; 978-1-61499-098-7/ebook). Frontiers in Artificial Intelligence and Applications 242, 510-515 (2012).
Summary: Filtering by Generalized Arc Consistency (GAC) is a fundamental technique in Constraint Programming. Recent advances in GAC algorithms for extensional constraints rely on direct manipulation of tables during search. Simple Tabular Reduction (STR), which systematically removes invalid tuples from tables, has been shown to be a simple yet efficient approach. STR2, a refinement of STR, is considered to be among the best filtering algorithms for positive table constraints. In this paper, we introduce a new GAC algorithm called STR3 that is specifically designed to enforce GAC during search. STR3 can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. Our experiments show that STR3 is much faster than STR2 when the average size of the tables is not reduced drastically during search.
For the entire collection see [Zbl 1272.68015].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P10 Searching and sorting
Full Text: Link