约束满足问题(Constraint Satisfaction Problem-CSP)是人工智能中的一个重要研究领域,是近年来很多学者所研究的一个非常活跃的内容和方向。实践证明,在我们周围的世界里,“约束”广泛的存在于生活和科研的各个领域当中,比如地图着色问题、生产调度问题、产品配置、路由选择、物流规划、人力资源管理问题等等。但在实际应用的时候,常常会遇到约束条件过多的情况,这种情况往往会使得问题无解。此时需要求出一个最优解使其最好的满足所有约束,即代价最少。因此研究者们便提出了加权约束满足问题(Weighted Constraint Satisfaction Problem, WCSP)的概念。CSP是WCSP的一个特例。对于经典CSP的求解是NP难的,因为在对CSP的求解时产生结果的阶段往往因过度回溯而陷入困境。减少回溯次数甚至实现无回溯搜索变得意义重大。而对WCSP的求解也是NP难的,在利用单纯遗传算法(GA)对WCSP的求解时,由于WCSP自身的结构特点使得遗传算法向最优解收敛的速度低,对最优解的搜索能力不强。鉴于此,本文针对CSP与WCSP的求解进行了研究,取得的主要成果如下:　　(1)ZBDD是描述和操作稀疏二进制向量的一种高效技术,是OBDD的一种扩展形式,其更适用于高效的处理组合集合问题。以零压缩二叉决策图(ZBDD)作为存储结构,基于树分解思想给出了CSP的一种新的求解方法。通过对CSP的ZBDD描述,将CSP的求解转变成对组合集合的交、并、补等基本操作,在一次操作内实现多条约束的并行处理,大大的提高了算法的效率。　　(2)给出了基于弧相容的ZBDD符号求解方法,首先提出的是一种求解最小环切割集的Get_CutSet算法,来构造原CSP的树形结构并实现无回溯搜索,该算法能够找到目前最小的环切割集。并且在单弧相容(Singleton AC)的基础之上提出了比弧相容强度更大的环相容(LC)的概念;然后通过环相容技术对环切割集中的变量进行实例化,得到原问题的局部解,并证明了该局部解一定可以扩展为原CSP的一个解;若原问题无解,则环相容技术在环切割上也找不到局部解。最终实现了对经典CSP的无回溯搜索的ZCS+BTF符号算法　　(3)结合树分解技术对遗传算法进行了改进,给出了RCGA算法。首先把WCSP的约束图分割为若干最小相关的子图,进而重新确定变量序进行编码,实验表明本文所提出的RCGA算法能够使父代的优点更好的遗传给下一代,有效的提高了向最优解收敛的速度,并增强了对最优解的搜索能力,整体性能明显优于单纯GA算法。