Efficient Path Consistency Algorithms for Constraint Satisfaction Problems

A large number of problems can be formulated as special cases of the Constraint Satisfaction Problem (CSP). In such a problem, the task specification can be formulated to consist of a set of variables, a domain for each variable and a set of constraints on these variables. A typical task is then to find an instantiation of these variables (to values in their respective domains) such that all the constraints are simultaneously satisfied. Most of the methods used to solve such problems are based on some backtracking scheme, which can be very inefficient with exponential run-time complexity for most nontrivial problems. Path consistency algorithms constitute an important class of algorithms used to simplify the search space, either before or during search, by eliminating inconsistent values from the domains of the corresponding variables. However, the use of these algorithms in real life applications has been limited, mainly, due to their high space complexity. Han and Lee [5] presented a path consistency algorithm, PC-4, with 0(n3a3) space complexity, which makes it practicable only for small problems. I present a new path consistency algorithm, PC-5, which has an 0(n3a2) space complexity while retaining the worst-case time complexity of PC-4. Moreover, the new algorithm exhibits a much better average-case time complexity. The new algorithm is based on the idea (due to Bessiere [1]) that, at any time, only a minimal amount of support has to be found and recorded for a labeling to establish its viability; one has to look for a new support only if the current support is eliminated. I also show that PC-5 can be improved further to yield an algorithm, PC5++, with even better average-case performance and the same space complexity. I present experimental results evaluating the performance of these algorithms on various classes of problems. The results show that both PC-5 and PC5++ significantly outperform PC-4, both in terms of space and time, with PC5++ being the better of the two algorithms presented