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