一类约束满足问题及其算法

针对具有解析约束形式、同一变量多赋值的约束满足问题,提出了一种新的约束满足问题定义·通过一种特殊约束满足问题的研究提出一套建立在这个定义基础之上的概念和三种算法:整数规划法、不等式组法和直接求解不定方程法,详细研究了其中的第三种算法,并给出了最坏情况下的时间复杂度,从而能够比较清晰地描述一类约束满足问题的一般分析过程,揭示了约束满足问题同经典的整数规划、数论和整数环论的联系·

A Class of Constraint Satisfaction Problems and Its Algorithms

?A new definition is put forward to a class of constraint satisfaction problems(CSP) in form of analytic constraints with multi-assignment to single variable. Based on the new definition, a series of concepts and 3 algorithms, i.e, the integer programming, inequility set and direct solution to indefinite equation, are set up through analyzing a particalar type of CSP, of which the 3rd algorithm is discussed in detail with its time complexity in worst case presented. Thus, the general analysis procedure of a class of CSPs can be described clearly to reveal the relation between CSP and classical integer programming,number theory and integer ring theory.