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

发布时间：2024-01-23 14:32

　　约束编程(CP)是用于建模和求解组合约束问题的通用且灵活的框架。表约束(也称为扩展约束)明确表示它们所涉及的变量的值的允许组合作为元组序列,称为表。表约束理论上可以编码任何类型的约束,并且是约束编程中最有用的约束之一。这些约束可以从已经从配置问题中的数据库读取的数据生成,或者可以编码用户的偏好以及其他应用程序。表约束将任意约束明确定义为一组解(元组)或非解。因此,表约束的空间与元组的数量成比例。简单表缩减(STR)通过维护有效元组的表来动态地缩减表大小,已被证明可以有效地维持广义弧一致性(GAC)。基于STR改进的STR2和STR3算法是当前主流的广义弧一致性算法,STR2和STR3在不同类型的实例下各有优势。该领域最近的一个重大改进是在表约束中使用比特向量来表示元组的有效性,在为变量值寻找支持时使用高效的比特并行操作。算法STRbit和Compact-Table都是结合了STR和比特向量操作的优点,已经显示出比过去十年中开发的最佳GAC算法快一个数量级。表约束有一个主要的缺点:存储它们所需的内存空间可能会随着约束元数而呈指数增长,为了解决这个问题,相继提出各种表压缩方法。当表约束规模...

【文章页数】：54 页

【学位级别】：硕士

图2.3MAC算法求解一个四皇后问题过程

图3.1稀疏集表示

图3.2STR2算法伪代码

图3.4Greedy-Compress算法Greedy-Compress算法以全长支持（即提及所有r变量）开始，并尝试使用上述基本步骤将它们压缩为大小为r-1变量的短支持

本文编号：3882829