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

Associated Constraint Based Non-binary Arc-consistency for Constraint Satisfaction Problems

作　　者：袁际军[1] 单汨源[1] 王克喜[1] 

机构地区：[1]湖南大学工商管理学院,长沙410082

出　　处：《计算机科学》2008年第5期158-162,共5页Computer Science

基　　金：国家自然科学基金项目(70671037);高等学校博士学科点专项科研基金项目(20050532005)

摘　　要：弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP)。本文提出了处理NCSP的关联约束非二元弧一致性算法。通过随机NCSP生成器产生问题实例,分别采用关联约束非二元孤一致性算法和非二元孤一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解。对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元孤一致性算法可以有效地别除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性。Arc consistency has been successfully applied to binary constraint satisfaction problem but cannot be generalized to effectively preprocess non-binary constraint satisfaction problem （NCSP）. Associated constraint based non-bina- ry arc-consistency （nACBA） for preprocessing NCSP is proposed in this paper. Some NCSP instances generated by random NCSP generator are first preprocessed by nACBA and non-binary arc-consistency （nAC） respectively, and then solved by backtracking algorithm. Performance of backtracking, nACBA based backtracking and nAC based backtracking are evaluated and compared. The computational results indicate that nACBA based backtracking is even more ro-bust than the other two algorithms, which means associated constraint based non-binary arc-consistency can more ettectively eliminate redundant variable values and constraint tuples.

关 键 词：非二元约束满足问题 回溯算法 关联约束非二元弧一致性 随机NCSP生成器 

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