An Optimal Filtering Algorithm for Table Constraints
An Optimal Filtering Algorithm for Table Constraints
复制标题
一种针对表约束的最优过滤算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Y. Deville
中科院分区：
文献类型：
--
作者：
Jean;Pascal Van Hentenryck;Y. Deville
表约束的过滤算法是基于约束的，这意味着传播队列仅包含有关必须重新考虑的约束的信息。本文提出了四种有效的基于值的表约束算法，这意味着传播队列还包含有关已删除值的信息。其中一种算法 (AC5TC-Tr) 被证明具有每个表约束的 O(r·t+r·d) 的最佳时间复杂度。实验结果表明，在结构化实例上，我们所有的算法都比最先进的 STR2+ 和 MDDc 算法快两到三倍。
Filtering algorithms for table constraints are constraint-based, which means that the propagation queue only contains information on the constraints that must be reconsidered. This paper proposes four efficient value-based algorithms for table constraints, meaning that the propagation queue also contains information on the removed values. One of these algorithms (AC5TC-Tr) is proved to have an optimal time complexity of O(r·t+r ·d) per table constraint. Experimental results show that, on structured instances, all our algorithms are two or three times faster than the state of the art STR2+ and MDDc algorithms.