论文部分内容阅读
约束满足问题是人工智能领域的一个重要问题,近三十年来有关约束满足问题的研究方兴未艾,己有的绝大多数关子约束满足问题的研究成果都是基于经典约束满足问题定义的,是从变量的集合出发,针对变量之间的制约关系来研究如何得到满足约束条件的变量的取值本文从变量取值出发,针对具有解析约束形式、同一变量多赋值的约柬满足问题,提出了一种新的约束满足问题定义。本文通过一种特殊约束满足问题的研究提出一套建立在这个定义基础之上的概念和三种算法:整数规划法、不等式组法和直接求解不定方程法,详细研究了其中的第三种算法,并给出了最坏情况下的时间复杂度,从而能够比较清晰的描述一类约束满足问题的一般分析过程,揭示了约束满足问题同经典的整数规划、数论和整数环论的联系、这三种算法都属于精确算法,得到的解是精确解.此外,基于实际问题的需要,本文还提出了用于求解约束满足问题的一类近似算法;开放一封闭算法及其改进算法。本文的后半部分介绍了约束满足问题在自动化组卷题库系统中的一个具体应用。这部分基本按照结构化软件开发的一般步骤,讨论了需求分析,总体设计、详细设计的主要过程和遇到的一些重点问题在详细分析中,比较详细地描述了本文前半部分所讨论约束满足问题算法在题库系统中的具体应用。