自适应表压缩方法优化STR算法

作     者：李少兴 李占山 于海鸿 LI Shao-xing;LI Zhan-shan;YU Hai-hong

作者机构：吉林大学计算机科学与技术学院吉林长春130012 

出 版 物：《计算机工程与科学》 (Computer Engineering & Science)

年 卷 期：2018年第40卷第12期

页      面：2243-2251页

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61272208) 吉林省自然科学项目(20180101043JC) 

主　　题：约束编程 表约束 简单表缩减 表压缩 自适应选择 比特向量 

摘      要：表约束,也称为外延式约束,是约束编程领域最常见的约束形式,表压缩方法通过紧凑的表示元组集可以极大地缩减空间消耗,同时加速GAC算法。笛卡尔乘积表示和短支持是表约束中最常见的两种表压缩方法,两种表压缩方法在同一问题上的压缩率是影响它们优化效果的主要原因。基于STR算法提出一种自适应表压缩方法,在求解问题时自适应选择压缩率大的表压缩方法,将自适应表压缩方法应用到STR2上提出了STR2-Adaptive算法,可以同时覆盖两种表压缩方法的优势。实验结果表明,STR2-Adaptive算法在绝大部分实例上都能自适应选择最佳的表压缩方法,有效地减少了STR2算法空间消耗和CPU运行时间。然后将自适应表压缩方法扩展到采用了高效的比特向量表示的STRbit算法上提出了STRbit-Adaptive算法。实验结果表明,STRbit-Adaptive算法效率同样普遍优于STRbit算法。