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

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

An adaptive table compression method for STR algorithms optimization

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.