A NEW BIDIRECTIONAL ARC CONSISTENCY ALGORITHM

摘要：

Arc consistency techniques have played an important role in constraint solving area. The paper presents a new bidirectional singleton arc consistency algorithm based on constraint networks, called BiSAC-2, and gives its correctness and completeness proof. BiSAC-2 shares the same simplification ability with BiSAC-1, furthermore, it decreases the times of keeping arc consistency. Namely, it avoids the redundant constraint propagation, and steadies more quickly than BiSAC-1. Finally the experiments on random constraint satisfaction problems show that BiSAC-2 has remarkable advantage over BiSAC-1 in performance.

关键词： Constraint satisfaction problem Arc consistency Bidirectional arc consistency

作者: CHUN-HUI LIU XING-JUN ZHU YONG-GANG ZHANG JI-GUI SUN

作者单位: College of Computer Science and Technology, Jilin University, Changchun, China, 130012

会议类型: 国际会议

会议名称: 2008 International Conference on Machine Learning and Cybernetics(2008机器学习与控制论国际会议)

会议地点: 昆明

会议语种:英文

页码: 148-152

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