主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
杨明奇,李占山,张家晨.一种基于时间戳的简单表缩减弧相容算法.软件学报,0,(0):0
一种基于时间戳的简单表缩减弧相容算法
Time-Stamp Based Simple Tabular Reduction Algorithm
投稿时间:2017-07-25  修订日期:2017-09-28
DOI:10.13328/j.cnki.jos.005559
中文关键词:  约束满足问题  简单表缩减  表约束  广义弧相容
英文关键词:constraint satisfaction problem  simple tabular reduction  table constraint  generalized arc consistency
基金项目:国家自然科学基金(61272208,61373052);吉林省科技计划项目(20180101043JC)
作者单位E-mail
杨明奇 吉林大学 计算机科学与技术学院, 吉林省 长春市 130012
符号计算与知识工程教育部重点实验室(吉林大学), 吉林省 长春市 130012 
 
李占山 吉林大学 计算机科学与技术学院, 吉林省 长春市 130012
符号计算与知识工程教育部重点实验室(吉林大学), 吉林省 长春市 130012 
 
张家晨 吉林大学 计算机科学与技术学院, 吉林省 长春市 130012 zhangjc@jlu.edu.cn 
摘要点击次数: 903
全文下载次数: 424
中文摘要:
      表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容(generalized arc consistency)是求解约束满足问题应用最广泛的相容性.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 paper, we propose a new algorithm based on dynamically maintaining valid parts of tables, which deletes invalid tuples and updates supports when enforcing GAC on table constraints. Our algorithm is applied to original table constraints and can also restore in constant time. Experimental evaluations shows that our algorithm outperforms existing STR algorithms without table compression. In some classes of problems, our algorithm is even more efficient than state-of-the-art compression based STR algorithms.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利