PW-CT: Extending Compact-Table to Enforce Pairwise Consistency on Table Constraints

Autor:	Berthe Y. Choueiry, Anthony Schneider
Rok vydání:	2018
Předmět:	High memory Offset (computer science) Computer science 020204 information systems 0202 electrical engineering electronic engineering information engineering Local consistency CPU time 020201 artificial intelligence & image processing Pairwise comparison 02 engineering and technology Algorithm
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319983332 CP
DOI:	10.1007/978-3-319-98334-9_23
Popis:	The Compact-Table (CT) algorithm is the current state-of-the-art algorithm for enforcing Generalized Arc Consistency (GAC) on table constraints during search. Recently, algorithms for enforcing Pairwise Consistency (PWC), which is strictly stronger than GAC, were shown to be advantageous for solving difficult problems. However, PWC algorithms can be costly in terms of CPU time and memory consumption. As a result, their overhead may offset the savings of search-space reduction. In this paper, we introduce PW-CT, an algorithm that modifies CT to enforce full PWC. We show that PW-CT avoids the high memory requirements of prior PWC algorithms and significantly reduces the time required to enforce PWC.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2f92f4085c764c1aa2b4a60630499a89 https://doi.org/10.1007/978-3-319-98334-9_23 Zobrazit plný text záznamu