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.

关键词： non-binary constraint satisfaction problem backtracking associated constraint based non-binary arc consistency random NCSP generator

作者: Wang kexi Yuan Jijun Shan Miyuan

作者单位: Management School Hunan University Changsha, China

会议类型: 国际会议

会议名称: 第三届IEEE无线通讯、网络技术暨移动计算国际会议

会议地点: 上海

会议语种:英文

在线出版日期: 2007-09-21（万方平台首次上网日期，不代表论文的发表时间）