线上期刊服务咨询,发表咨询:400-808-1701 订阅咨询:400-808-1721

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

杨明奇; 李占山; 张家晨 软件学报 2019年第11期

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

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

单位:吉林大学计算机科学与技术学院; 吉林长春130012; 符号计算与知识工程教育部重点实验室(吉林大学); 吉林长春130012

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

软件学报

北大期刊

¥1128.00

关注 22人评论|3人关注