Partial Domain Search Tree For Constraint-Satisfaction Problems

Guni Sharon, Ariel Felner, Roni Stern, Nathan R. Sturtevant

Abstract

CSP solvers usually search a partial assignment search tree. We present a new formalization for CSP solvers, which spans a conceptually different search tree, where each node represents subsets of the original domains for the variables. We experiment with a simple backtracking algorithm for this search tree and show that it outperforms a simple backtracking algorithm on the traditional search tree in many cases.
BibTeX
@inproceedings{sharon2013partial,
  author = {Guni Sharon and Ariel Felner and Roni Stern and Nathan R. Sturtevant},
  title = {{Partial Domain Search Tree For Constraint-Satisfaction Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
}

Loading related content...

Figure