Merging Constraint Satisfaction Subproblems to Avoid Redundant Search

Larrosa, Javier

Merging Constraint Satisfaction Subproblems to Avoid Redundant Search

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 424-432.

Abstract

When solving a constraint satisfaction problem we may find similar subproblems. Algorithms not exploiting this similarity are condemned to duplicate some work. In this paper we introduce a technique for merging sibling subproblems which avoids redundancy in search associated to their similarity. We show that, whenforward checking is enhanced with this capability, its performance may be increased . Experimental results on hard crossword puzzles support the practical validity of our approach.

Javier Larrosa. 1997. Merging Constraint Satisfaction Subproblems to Avoid Redundant Search. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 424–432. https://ijcai.org/proceedings/1997/63

@inproceedings{ijcai1997p63,
  title     = {Merging Constraint Satisfaction Subproblems to Avoid Redundant Search},
  author    = {Larrosa, Javier},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {424--432},
  year      = {1997},
  note      = {Constraint Satisfaction},
  url       = {https://ijcai.org/proceedings/1997/63},
}

TY  - CPAPER
TI  - Merging Constraint Satisfaction Subproblems to Avoid Redundant Search
AU  - Larrosa, Javier
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 424
EP  - 432
UR  - https://ijcai.org/proceedings/1997/63
ER  -