Constraint satisfaction problems (CSPs) have a rich history in Artificial Intelligence and have become one of the most versatile mechanisms for representing complex relationships in real life problems. A CSP's variables and constraints determine its primal constraint network. For every primal representation, there is an equivalent dual representation where the primal constraints are the dual variables, and the dual constraints are compatibility constraints on the primal variables shared between the primal constraints. In this paper, we compare the performance of local search in solving Constraint Satisfaction Problems using the primal constraint graph versus the dual constraint graph.
展开▼
