Simple Tabular Reduction Algorithm Based on Time-stamp Mechanism

DOI：10.13328/j.cnki.jos.005559

 作者 单位 E-mail 杨明奇 吉林大学 计算机科学与技术学院, 吉林 长春 130012符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012 李占山 吉林大学 计算机科学与技术学院, 吉林 长春 130012符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012 张家晨 吉林大学 计算机科学与技术学院, 吉林 长春 130012 zhangjc@jlu.edu.cn

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

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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器