摘要:表约束是一种外延的知识表示方法，每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容（generalized arc consistency，简称GAC）是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction（STR）是一类高效的维持GAC的算法.在回溯搜索中，STR动态地删除无效元组，降低了查找支持的开销，并拥有单位时间的回溯代价，在高元表约束上获得了广泛运用，并有大量基于STR的改进算法被提出，其中，元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想，为STR提出一种检测并删除无效元组和为变量更新支持的算法，作用于原始表约束并拥有单位时间的回溯代价.实验结果表明，该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法，并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.



Abstract:Table constraints define an arbitrary constraint explicitly as a set of solutions or non-solutions. Generalized arc consistency (GAC) is the most widely used consistency for solving non-binary constraint satisfaction problems (CSPs). Simple tabular reduction (STR), which dynamically deletes invalid tuples during search, speeds up the process of updating supports for variables and can restore in constant time when backtrack occurs. STR achieves dynamically maintaining valid parts of tables during search, which has been shown to be efficient for enforcing GAC. Recent research on improving STR mainly focuses on the compressed representation of tables. In this study, a new algorithm is proposed based on dynamically maintaining valid parts of tables, which deletes invalid tuples and updates supports when enforcing GAC on table constraints. The proposed algorithm is applied to original table constraints and can also restore in constant time. Experimental evaluations show that the proposed algorithm outperforms existing STR algorithms without table compression. In some classes of problems, the proposed algorithm is even more efficient than state-of-the-art compression based STR algorithms.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5559