约束满足问题是人工智能领域重要的研究方向之一,主要用于求解实际问题和学术问题。约束满足问题技术解决问题的主要思想是:首先将待求解问题抽象成一个约束网络模型,然后利用约束满足问题相关求解算法对得到的约束网络模型进行求解。目前求解约束满足问题的算法主要包括:回溯搜索算法、局部推理算法以及启发式算法等。基于回溯搜索的MAC算法是目前求解约束满足问题使用最广泛的搜索算法,其算法思想是采用回溯搜索策略,在选择变量进行实例化后,利用相容性算法对约束网络进行约束传播,删除变量论域中不满足相容性条件的值,从而压缩约束网络,减小搜索空间,简化求解过程。在使用MAC算法求解规模较大的约束满足问题时,不合理的变量实例化顺序,常常会导致搜索树的体积过于庞大,严重影响求解效率。然而在回溯搜索过程中,由于约束网络的状态经常发生改变,因此寻找一个最优的变量实例化顺序的难度非常大。为了解决这一问题,学者们提出了启发式的概念。在对变量进行实例化之前,使用启发式算法进行变量和值的选择,尽可能地缩减搜索树的规模。变量排序启发式算法的作用是根据启发式规则指导回溯搜索算法选择变量进行实例化,避免冗余搜索,提高求解效率。变量排序启发式算法根据变量实例化顺序在搜索过程中是否发生改变分为静态变量排序启发式算法和动态变量排序启发式算法两种。静态变量排序启发式算法根据约束网络的初始结构和属性,在搜索开始前就确定了变量的实例化顺序。动态变量排序启发式算法的原理是利用回溯搜索过程中产生的有利于求解的启发信息,在选择变量时,首先为每个变量计算一个启发式得分,然后根据启发式得分选择变量。回溯搜索是一个动态的过程,静态变量排序启发式算法在搜索初始确定的变量实例化顺序,不能时刻适应不断变化的约束网络状态。因此,在实际求解中常使用动态变量排序启发式算法。目前学者们已经提出了许多优秀的动态变量排序启发式算法,其中包括基于变量论域大小的Dom启发式、基于变量动态度的Ddeg启发式、基于约束权重的Wdeg启发式、基于紧度的Tdeg启发式以及基于变量实例化次数的Variable_try启发式。启发式算法通常具有良好可扩展性,不同的启发式相互结合通常能够得到启发能力更强的启发式。结合了Dom启发式与Wdeg启发式的Dom/Wdeg启发式是目前平均求解效率最高的动态变量排序启发式算法。本文对目前使用比较广泛的Wdeg启发式进行研究分析,针对其不足之处,进行了相应的优化,提出了更加高效的启发式算法,具体工作如下:(1)对约束满足问题背景知识和目前主流的动态变量排序启发式进行了介绍和分析,主要包括约束满足问题基本概念、相容性算法、MAC算法、Ddeg启发式、Wdeg启发式、Tdeg启发式以及Variable_try启发式。(2)针对Wdeg启发式的不足,提出了变量权重的概念以及基于变量权重的相关动态变量排序启发式,并通过大量实验验证新启发式在求解约束满足问题时具有较强的启发能力。