TY - JFULL
AU - Jeffrey L. Duffany
PY - 2009/2/
TI - Optimal Solution of Constraint Satisfaction Problems
T2 - International Journal of Computer and Information Engineering
SP - 215
EP - 219
VL - 3
SN - 1307-6892
UR - https://publications.waset.org/pdf/2428
PU - World Academy of Science, Engineering and Technology
NX - Open Science Index 25, 2009
N2 - 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).
ER -