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

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

弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(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.