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

A Class of Constraint Satisfaction Problems and Its Algorithms

作　　者：蒋本铁[1] 毕世飞[2] 

机构地区：[1]东北大学计算中心,辽宁沈阳110004 [2]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2003年第12期1169-1172,共4页Journal of Northeastern University(Natural Science)

基　　金：辽宁省自然科学基金资助项目(9910701001)

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

关 键 词：约束满足问题(CSP) 不定方程 整数规划 偏移方程 时间复杂度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]