论文部分内容阅读
表约束是一种外延的知识表示方法,每个约束包含一组变量上所有支持或禁止的元组。广义弧相容(GAC)是求解多元约束满足问题应用最广泛的相容性。简单表缩减(STR)是一类在表约束上维持GAC的算法,基于动态维持元组集有效部分的策略,在搜索的每一阶段维持相容性时,STR移除当前的无效元组,从而降低了查找支持的开销。在搜索发生回溯时,STR拥有单位时间的恢复元组集有效部分的代价。STR在高元表约束上获得了广泛运用,大量基于STR的改进算法被提出,其中元组集的压缩表示是目前研究较多的方法。本文提出的STR2*同样基于动态维持元组集有效部分的策略,但采用一种新的基于列的方式存储约束关系中的元组,并将删除无效元组以及为变量值查找支持的操作分别转化为与之对应的列操作。此外,STR2*使用时间戳标记变量和约束上的操作次序,降低了获取论域发生改变的变量的计算开销,并精简了数据结构。实验结果表明该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法。MDDc、STR2和STR3均是表约束上维持GAC的算法,MDDc将约束关系构建成多元决策图,当元组之间存在较多交叠部分时,对应的多元决策图压缩效果显著,遍历多元决策图获取支持的代价降低,进而提升了维持GAC的效率。STR2将约束关系表示为表,在维持GAC时检测当前表中所有元组获取有效元组集,然后对有效元组集投影更新变量值的支持。STR3将约束关系表示为对偶表,每个变量值维护一个包含该值的所有元组的副本,在维持GAC时更新所有值维护的当前有效元组。STR2与STR3维持相容性的效率与元组集有效部分的缩减速度有关,当缩减较慢时,STR3的效率高于STR2,反之,STR2的效率高于STR3。分析发现,MDDc中查找节点的有效出边和STR3中删除无效元组是整个求解过程中最密集且耗时最多的操作。为此,本文提出一种采用自适应查找有效出边的MDDc算法——AdaptiveMDDc,以及一种采用自适应删除无效元组的STR算法——AdaptiveSTR。在回溯搜索的不同阶段,AdaptiveMDDc可以根据当前多元决策图有效部分的规模自适应地选择效率最高的查找有效出边的方法,而AdaptiveSTR可以根据当前对偶表有效部分的规模自适应地选择效率最高的删除无效元组的方法,得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比原算法速度提升显著,其中AdaptiveSTR在一些问题上相比STR3提速三倍以上。