Jeffrey L. Duffany
Optimal Solution of Constraint Satisfaction Problems
216 - 219
2009
3
1
International Journal of Computer and Information Engineering
https://publications.waset.org/pdf/2428
https://publications.waset.org/vol/25
World Academy of Science, Engineering and Technology
An optimal solution for a large number of constraint
satisfaction problems can be found using the technique of
substitution and elimination of variables analogous to the technique
that is used to solve systems of equations. A decision function
f(A)max(A2) is used to determine which variables to eliminate. The
algorithm can be expressed in six lines and is remarkable in both its
simplicity and its ability to find an optimal solution. However it is
inefficient in that it needs to square the updated A matrix after each
variable elimination. To overcome this inefficiency the algorithm is
analyzed and it is shown that the A matrix only needs to be squared
once at the first step of the algorithm and then incrementally updated
for subsequent steps, resulting in significant improvement and an
algorithm complexity of O(n3).
Open Science Index 25, 2009