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

摘要：

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

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

所属期刊栏目：30

分类号：TP18(自动化基础理论)

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

在线出版日期：2019-11-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：3355-3363