约束满足问题在人工智能领域有着广泛的应用。目前有许多求解约束满足问题的方法,本文对常用的求解约束满足问题的维持弧相容算法做了改进,对求解约束满足问题的效率起到至关重要的两个部分--弧相容和启发式分别做了改进,从两个方面整体地提高求解约束满足问题的效率。本文通过分析约束满足问题的粗粒度维持弧相容求解算法在弧相容(arc containing,AC)的执行过程,发现在对弧的修正检查算法中存在冗余的弧放回操作,并对弧的冗余放回给出了完整的证明。启发式是约束满足问题求解的一个重要组成部分,它通过一定的策略来选择并确定变量和值来搜索约束满足问题的解。目前已有许多成熟的变量启发式能够针对特定的问题属性进行搜索路径选择,但是由于针对性极强,一旦被求解问题针对的特性并不明显,则相应的启发式不能发挥选择作用,有时甚至使得问题求解效率下降极大。基于此,考虑设计一种鲁棒性强的启发式,来避免断崖式的求解效率波动。本文对约束满足问题求解的改进主要体现在以下两个方面:(1)在AC3算法的基础上提出了一种改进算法AC_AO通过保证弧的唯一性来避免冗余弧的放回队列的操作。这种通过维持弧的唯一性改进弧相容算法的模式可以形成框架并适用于AC系列算法,包括AC3算法、AC2001算法、AC3rm算法,本文将提出的改进算法框架AC_AO应用于AC3、AC2001、AC3rm算法与原算法做实验对比,实验结果表明,应用AC_AO算法框架后的AC系列算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间,AC_AO算法通过减少弧的检查进而减少修正函数的调用次数,从而提高AC的执行效率,缩短弧相容算法的执行时间。将AC_AO算法应用在维持弧相容算法求解的过程中对求解效率提高是非常有意义的。(2)提出了一种基于遗传选择的启发式方法,能够针对问题属性进行自适应地选择合适启发式指导变量选择。本文对该方法进行了详细分析与描述,将之与最新版本的Choco求解器中最常用的默认启发式domOverWdeg启发式、activityBased启发式作对比,并且针对遗传选择的启发式算法,分别做了两组实验,一组弧相容算法选择AC3算法,另一组弧相容算法选择AC_AO算法,分别进行约束满足问题的求解,实验结果表明在约束满足问题的求解上,AC_AO算法优于AC3算法。基于遗传选择的启发式算法的求解效率最高是domOverWdeg启发式的2.35倍,activityBased启发式的2.26倍。在求解效率的鲁棒性上也优于其他启发式算法。