Partial domain search tree for constraint-satisfaction problems
Guni Sharon, Ariel Felner, Roni Stern, Nathan Sturtevant · 2013
The traditional approach for solving Constraint satisfaction Problems (CSPs) is searching the Assignment Space in which each state represents an assignment to some variables. This paper suggests a new search space formalization for CSPs, the Partial Domain Search Tree (PDST). In each PDST node a unique subset of the original domain is considered, values are excluded from the domains in each node to insure that a given set of constraints is satisfied. We provide theoretical analy-sis of this new approach showing that searching the PDST is beneficial for loosely constrained problems. Experimental re-sults show that this new formalization is a promising direction for future research. In some cases searching the PDST out-performs the traditional approach by an order of magnitude. Furthermore, PDST can enhance Local Search techniques re-sulting in solutions that violate up to 30 % less constraints.