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

计算机工程与科学

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

李少兴,李占山,于海鸿

（吉林大学计算机科学与技术学院,吉林长春 130012）

收稿日期:2018-06-08 修回日期:2018-08-06 出版日期:2018-12-25 发布日期:2018-12-25
基金资助:
国家自然科学基金（61272208）；吉林省自然科学项目(20180101043JC)

An adaptive table compression method

for STR algorithms optimization

LI Shaoxing,LI Zhanshan,YU Haihong

（College of Computer Science and Technology,Jilin University,Changchun 130012,China）

Received:2018-06-08 Revised:2018-08-06 Online:2018-12-25 Published:2018-12-25

摘要/Abstract

摘要：

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

关键词: 约束编程, 表约束, 简单表缩减, 表压缩, 自适应选择, 比特向量

Abstract:

Table constraint, also called extensional constraint, is the most general form of finite domain constraint in the field of constraint programming. Table compressing methods can greatly reduce space consumption by compact representation of tuple set and accelerate the GAC algorithm. Cartesian product representation and short support are the two most common table compression methods in table constraint. We find that the compression ratio of the two table compression methods on the same problem is the main factor that affects their optimization results, and propose an adaptive table compression method based on STR algorithm. It adaptively selects the table compression method with larger compression ratio when solving the problem. We apply the adaptive table compression method to the STR2 algorithm, and propose an STR2-adaptive algorithm, which can cover the advantages of the two table compression methods. Experimental results show that the STR2-adaptive algorithm can adaptively select the best table compression method on most instances and effectively reduces space cost and CPU running time of the STR2 algorithm. Then we extend the adaptive table compression method to the STRbit algorithm using efficient bit vector representation, and we propose the STRbit-adaptive algorithm. Experimental results show that the efficiency of STRbit-adaptive algorithm generally has higher efficiency than that of the STRbit algorithm.

Key words: constraint programming, table constraint, simple tabular reduction, table compression, adaptive selection, bit vector

李少兴,李占山,于海鸿. 自适应表压缩方法优化STR算法[J]. 计算机工程与科学.

LI Shaoxing,LI Zhanshan,YU Haihong.

An adaptive table compression method

for STR algorithms optimization

[J]. Computer Engineering & Science.

[1]	宋威1,2,李雪松1. 基于标签自适应选择的矩阵分解推荐算法[J]. 计算机工程与科学, 2018, 40(10): 1731-1736.
[2]	黄玉，殷苌茗，周书仁. 基于YCbCr的自适应混合高斯模型背景建模[J]. J4, 2015, 37(01): 152-156.