Optimizing the Method for Finding an Optimal Solution of a Constraint Satisfaction Problem

Abstract

Abstract — Constraint satisfaction problems are the subject of intense research in both artificial intelligence and operations research. They are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. Often, they exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Most optimal solutions for a constraint satisfaction problem are found by a standard substitution and elimination technique, similar to the procedure used to solve systems of equations, with the decision function f(A)=max(A2). However, this method involves squaring the A matrix after each substitution, making it time consuming for larger matrices. This can be remedied using a different method that only requires A to be squared once, and subsequently updated thereafter. Key Terms - Algorithm, Complexity, Constraint, Matrix.