一种基于时间戳的简单表缩减算法  

Simple Tabular Reduction Algorithm Based on Time-stamp Mechanism

作　　者：杨明奇 李占山[1,2] 张家晨[1] YANG Ming-Qi;LI Zhan-Shan;ZHANG Jia-Chen(College of Computer Science and Technology,Jilin University,Changchun 130012,China;Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University),Ministry of Education,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]符号计算与知识工程教育部重点实验室(吉林大学),吉林长春130012

出　　处：《软件学报》2019年第11期3355-3363,共9页Journal of Software

基　　金：国家自然科学基金(61272208,61373052);吉林省科技计划(20180101043JC)~~

摘　　要：表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容(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.

关 键 词：约束满足问题 简单表缩减 表约束 广义弧相容 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]