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

计算机科学 ›› 2008, Vol. 35 ›› Issue (5): 158-162.

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

袁际军单汨源王克喜

湖南大学工商管理学院,长沙410082

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
国家自然科学基金项目（70671037）;高等学校博士学科点专项科研基金项目（20050532005）.

YUAN Ji-jun SHAN Mi-yuan WANG Ke-xi （Management School, Hunan Universit y, Changsha 410082, China）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 弧一致性算法在二元约束满足问题中取得了成功的应用，但并不能被有效泛化至预处理非二元约束满足问题（NCSP）。本文提出了处理NCSP的关联约束非二元弧一致性算法。通过随机NCSP生成器产生问题实例，分别采用关联约束非二元弧一致性算法和非二元弧一致性算法进行预处理，并对预处理后的问题实例应用回溯算法进行求解。对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能，仿真实验结果表明关联约束非二元弧一致性算法可以有效地剔除冗余的约束元组和变量域值，使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性。

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

Abstract: 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）

Key words: Non-binary constraint satisfaction problem, Backtracking, Associated constraint based non-binary arc-con-sistency, Random NCSP generator

袁际军单汨源王克喜. 基于关联约束非二元弧一致性的约束满足问题求解[J]. 计算机科学, 2008, 35(5): 158-162. https://doi.org/

YUAN Ji-jun SHAN Mi-yuan WANG Ke-xi （Management School, Hunan Universit y, Changsha 410082, China）. [J]. Computer Science, 2008, 35(5): 158-162. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed