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

Non-binary conditional constraint satisfaction problems solution

作　　者：袁际军[1] 黄敏镁[2] 

机构地区：[1]广东财经大学金融学院,广东广州510320 [2]华南师范大学管理科学系,广东广州510006

出　　处：《计算机集成制造系统》2014年第3期636-651,共16页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(71272084;71102146);教育部人文社会科学研究青年基金资助项目(12YJC630278);广东省普通高校人文社科研究资助项目(2012LYM_0065);广东商学院校级一般资助项目(11YB63001)~~

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]