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

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

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

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