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

• 作者: 于海鸿 李占山 李少兴
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 约束编程 表约束 简单表缩减 表压缩 自适应选择 比特向量
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 人工智能与数据挖掘
• 页码范围: 2243-2251
• 页数: 9页
• 分类号: TP301.6
• 字数: 7833字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2018.12.020

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李占山	吉林大学计算机科学与技术学院	43	234	7.0	13.0
2	李少兴	吉林大学计算机科学与技术学院	1	0	0.0	0.0
3	于海鸿	吉林大学计算机科学与技术学院	12	90	4.0	9.0