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

来源：软件学报杂志2019年第11期北京时间：

作者：杨明奇,李占山,张家晨

单位：杨明奇，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001211,李占山，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001202,张家晨，吉林大学 计算机科学与技术学院, 吉林 长春 13001203

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

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

基金资助：国家自然科学基金（61272208，61373052）；吉林省科技计划（20180101043JC）