非二元约束满足问题求解

在约束满足问题 (CSP)的研究中 ,大部分工作集中在二元约束 ,但处理实际问题时 ,常常会遇到非二元约束的情况 .该文在概要地讨论了两类求解非二元约束问题方法的基础上 ,研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法 ,并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法 ,以典型例子给出了实现系统的运行结果 .

基于非二元约束满足的配置问题求解方法

依据产品的可配置性,提出基于非二元约束的逻辑产品模型,给出基于动态变量序的一类配置求解算法。采用仿真实验比较各种算法的求解效率,指出各算法在不同配置约束密度下快速求解配置问题时的适用范围。基于逻辑产品模型,依据配置问题实际性质,采用相应配置求解算法,能够更快地生成符合客户要求的产品配置方案。

基于关联约束非二元弧一致性的约束满足问题求解

弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP)。本文提出了处理NCSP的关联约束非二元弧一致性算法。通过随机NCSP生成器产生问题实例,分别采用关联约束非二元孤一致性算法和非二元孤一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解。对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元孤一致性算法可以有效地别除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性。

非二元约束满足问题的产品配置建模与求解

针对传统二元约束满足问题直观建模产品配置问题存在的不足,提出了一种更适宜表示配置知识、基于非二元约束满足问题的产品配置方法。根据配置问题中配置知识的表现形式,提出了配置问题向非二元约束满足问题转化的映射方法,并建立了配置问题的非二元约束满足问题模型。通过仿真实验发现,基于非二元约束满足问题的产品配置方法具有知识表示便捷、求解效率高、求解方面丰富的优良特点,适于处理各类复杂配置问题。

非二元条件约束满足问题求解

非二元条件约束满足问题是二元条件约束满足问题的泛化。给出了非二元条件约束满足问题模型;针对求解过程中激活性约束引起的变量空间变化,分别采用"后看"策略和嵌入不同程度非二元弧一致性的"前看"策略思想,提出一种非二元条件回溯算法和两种非二元条件前向检查算法,以有效处理约束维数的非二元性及变量依条件参与求解的动态性等问题;分析了三种算法最坏情况下的时间复杂性;通过随机生成的测试实例仿真实验比较了三种算法的求解性能。实验结果表明:在处理难问题时,两种非二元条件前向检查算法的性能均显著优于非二元条件回溯算法;而在分别处理中小规模低动态性特征与大规模高动态性特征问题时,两种非二元条件前向检查算法性能存在显著差异。