主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李宏博,李占山,王涛.改进求解约束满足问题粗粒度弧相容算法.软件学报,2012,23(7):1816-1823
改进求解约束满足问题粗粒度弧相容算法
Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems
投稿时间:2011-06-29  修订日期:2011-10-08
DOI:10.3724/SP.J.1001.2012.04129
中文关键词:  约束满足问题  维持弧相容  粗粒度算法  修正检查
英文关键词:constraint satisfaction problem  maintaining arc consistency  coarse-grained algorithm  revision
基金项目:国家自然科学基金(60773097, 60873148, 60973089); 吉林省自然科学基金(201101039, 20071106, 20080107); 国家教育部博士点专项基金(20100061110031)
作者单位E-mail
李宏博 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
 
李占山 吉林大学 计算机科学与技术学院,吉林 长春 130012
吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012 
zslizsli@163.com 
王涛 长春工业大学 计算机科学与工程学院,吉林 长春 130012  
摘要点击次数: 3195
全文下载次数: 3329
中文摘要:
      约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR 改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.
英文摘要:
      Constraint satisfaction problems have been widely investigated in artificial intelligence area. This paper investigates whether the coarse-grained maintaining arc is consistent, which is used to solve CSPs. The study has found that during the search for a solution, there are ineffective revisions, which revise the arcs that point to assigned variables. This study has proved that such revisions are redundant and proposed a method to avoid such redundant revisions. The paper gives the improved basic frame for the coarse-grained arc consistency algorithms, named AC3_frame_ARR. The new frame can be applied to improve all the coarse-grained AC algorithms. The experimental results show that the improved algorithms can save at most 80% revisions and 40% CPU time.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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