Associated Constraint Based Non-Binary Arc Consistency for Non-Binary CSP

摘要

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-binary arc consistency (nACBA) for preprocessing NCSP was proposed in this paper. Some NCSP instances generated by random NCSP generator were first preprocessed by nACBA and non-binary arc- consistency (nAC) respectively, and then solved by backtracking algorithm. Performances of backtracking, nACBA based backtracking and nAC based backtracking were evaluated and compared. The experimental results indicate that nACBA based backtracking is even more robust than the other two algorithms, which means associated constraint based non-binary arc-consistency can more effectively eliminate inconsistent values from the domains of variables or redundant constraint tuples from constraints than non-binary arc consistency.