论文部分内容阅读
约束传播作为约束编程的关键方法,在许多工业应用中被广泛使用,例如在设计与配置问题,数据库问题,参数选择建模问题,调度问题中已成为一种解决问题的有效手段。其中,约束建模技术作为一种解决问题的常用方法,尤其当问题规模较大时,求解效果非常显著。在组合建模问题中,表约束是约束表示方法中一种非常实用的方式,表约束是指外延约束通过将允许元组或禁止元组以表的形式罗列出来,这种表示形式在约束编程方法中有着举足轻重的地位。在大多数情况下,表约束提供了一种独特的实际方法为非专家用户表述他的约束需求。因此,研究人员的目光集中在如何使表约束算法可以更快的维持GAC。关于表约束的GAC算法研究可追溯到GAC4和GAC-Schema,经典算法通过不同方法来迭代循环当前元组。最近研究的一种基于AC5的算法,在小规模约束表中算法的执行效率非常好,而对于规模较大的约束表,由于在表中为了动态维持支持从而降低了算法效率。由于约束表的规模可能随着变量个数的增加呈现指数级的增大,所以近些年来针对如何降低约束表空间规模的研究一直如火如荼,在一些约束传播算法中频繁用到表压缩的方式来降低约束表的空间消耗,同时提高GAC算法的运行速度。其中Tries,MDDs,DFA是当前以紧凑方式表示约束表的通用结构,目的是促进过滤进程。在这些压缩方式中有使用笛卡儿积压缩的方法,利用C-tuple将约束表压缩变成较小的压缩表,这种方式成功应用于破对称技术和处理解决方案集;还有一种基于数据挖掘的频繁模式方法,将表中最频繁出现的模式用模式表中的序号替代,从而降低空间消耗;而在频繁模式的基础上提出的分割表方法,降低了模式的限制条件并将约束表切割成不同大小的切割片;比特操作将约束表用比特向量的方式表示为比特表,是近几年来算法提升速度最快的方法;以及利用元组特性将原有约束表压缩成短表的短支持方法。短支持方法是近些年来在约束传播算法中使用最广泛的一种表压缩方式,但当约束表压缩率较低时,短支持方法提高运行速度效果不明显。基于此本文提出一种压缩约束表的新方法STRO,结合短支持压缩和比特操作,在提高STR算法的运行速度的同时压缩表空间效果更好。实验结果表明,在表的平均大小不是特别小的情况下,STRO与主流表缩减算法STR2及使用短支持压缩的ShortSTR2算法相比,速度更快,效率更高;与利用比特操作的STRbit算法相比,STRO的表压缩率更大,更加节省空间,并且在时间上可以替代STRbit。