Name
Abstract | ||
|---|---|---|
In this paper, a state-based approach for the Constraint Sat- isfaction Problem (CSP) is proposed. The key novelty is an original use of state memorization during search to prevent the exploration of similar subnetworks. Classical techniques to avoid the resurgence of previously encountered conicts involve recording conict sets. This contrasts with our state- based approach which records subnetworks ñ a snapshot of some selected domains ñ already explored. This knowledge is later used to either prune inconsistent states or avoid re- computing the solutions of these subnetworks. Interestingly enough, the two approaches present some complementarity: different states can be pruned from the same partial instan- tiation or conict set, whereas different partial instantiations can lead to the same state that needs to be explored only once. Also, our proposed approach is able to dynamically break some kinds of symmetries (e.g. neighborhood interchange- ability). The obtained experimental results demonstrate the promising prospects of state-based search. |
Year | Venue | Keywords |
|---|---|---|
2007 | AAAI | state-based approach,different partial instantiations,state-based search,different state,constraint satisfaction,conflict set,partial instantiation,state memorization,transposition table,inconsistent state,similar subnetworks |
Field | DocType | Citations |
Complementarity (molecular biology),Constraint satisfaction,Mathematical optimization,Computer science,Interchangeability,Constraint satisfaction problem,Transposition table,Artificial intelligence,Novelty,Snapshot (computer storage),Memorization,Machine learning | Conference | 4 |
PageRank | References | Authors |
0.45 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christophe Lecoutre | 1 | 709 | 45.10 |
| Lakhdar Sais | 2 | 859 | 65.57 |
| Sébastien Tabary | 3 | 66 | 6.58 |
| Vincent Vidal | 4 | 4 | 0.78 |