摘要
利用笛卡尔积压缩方法可有效减小负表约束规模的原理,提出一种在压缩负表上维持广义弧相容的高效算法STRC-N,以解决负表约束维持弧相容过程中遍历所有元组导致效率低的问题.实验结果表明,当压缩负表上压缩率较大时,得益于表规模的减小,新算法相对于主流的负表约束处理算法效率更高,性能更好,从而实现了对负表约束处理算法的改进.
Based on the principle that cartesian product compression could effectively reduce the scale of negative table constraint, we proposed an efficient algorithm STRC-N to maintain generalized arc consistency on compressed negative table, which solved the problem of traversal of all tuples and low efficiency in the process of maintaining generalized arc consistency on negative table constraint. Experimental results show that when the compression rate of negative table is large, the new algorithm has higher efficiency and better performance than the mainstream negative table constraint processing algorithm due to the reduction of table size. Thus, the negative table constraints processing algorithm is improved.
作者
蔡毛毛
李占山
董学阳
CAI Maomao;LI Zhanshan;DONG Xueyang(Key Laboratory of Symbolic Computation and Knowledge Engineering Ministry of Education,College of Computer Science and Technology,Jilin University,Changchun 130012,China;Public Computer Education and Research Center,Jilin University,Changchun 130012,China)
出处
《吉林大学学报（理学版）》
CAS
北大核心
2019年第3期591-597,共7页
Journal of Jilin University:Science Edition
基金
吉林省科技发展计划项目(批准号:20140101200JC)
关键词
约束满足问题
负表约束
表压缩
弧相容
constraint satisfaction problem
negative table constraint
table compression
arc consistency
