一种笛卡尔积压缩的负表约束上表缩减算法  

A Tabular Reduction Algorithm on Negative Table Constraint Compressed by Cartesian Product

作　　者：蔡毛毛 李占山[1] 董学阳[2] 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)

机构地区：[1]吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室,长春130012 [2]吉林大学公共计算机教学与研究中心,长春130012

出　　处：《吉林大学学报（理学版）》2019年第3期591-597,共7页Journal of Jilin University:Science Edition

基　　金：吉林省科技发展计划项目(批准号:20140101200JC)

摘　　要：利用笛卡尔积压缩方法可有效减小负表约束规模的原理,提出一种在压缩负表上维持广义弧相容的高效算法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.

关 键 词：约束满足问题 负表约束 表压缩 弧相容 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]