Increasing Functional Constraints Need to Be Checked Only Once

摘要

Central to solving Constraint Satisfaction Problem (CSP) is the problem of consistency check. Past research has produced many general and specific consistency algorithms. Specific algorithms are efficient specializations of the general ones for specific constraints. Functional, anti-functional and monotonic constraints are three important classes of specific constraints. They form the basis of the current constraint programming languages. This paper proposes a more efficient method for checking an important subclass of functional constraints, increasing functional constraints. Rather than checking them many times as in a typical consistency check process, in the new method they (almost all of them) only need to be checked once. This results in a substantial saving in computation.