Abstract: Non-binary Conditional Constraint Satisfaction Problem (NCCSP) is an extension of Binary Conditional Constraint Satisfaction Problem (BCCSP).A NCCSP- model was proposed.According to the change of variable statuses caused by activity constraints,the tactics of look backward and look forward combining with different levels of non-binary arc consistency technology were adopted to propose a non-binary conditional backtracking algorithm and two non-binary conditional forward checking algorithms,which could effectively deal with non-binary constraints and variability of variable status in NCCSP.The time complexities of three algorithms in worst cases were analyzed,and the performances of three algorithms were compared by the experiments on random problems.Experimental results demonstrated that the performances of two non-binary conditional forward checking algorithms were evidently better than that of non-binary conditional backtracking algorithm in hard problems,while there was distinct difference between the performances of the two non-binary conditional forward checking algorithms in the case of low dynamical medium-size problems and high dynamical large-size problems.

Key words: non-binary conditional constraint satisfaction problem, non-binary conditional backtracking algorithm, non-binary conditional forward checking algorithm, non-binary arc consistency

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

关键词: 非二元条件约束满足问题, 非二元条件回溯算法, 非二元条件前向检查算法, 非二元弧一致性