• 首页
  • 期刊简介
  • 编委会
  • 投稿指南
  • 收录情况
  • 杂志订阅
  • 联系我们
引用本文:蒋李鸣,吕佳宇,何哲华,冯泽斌.基于启发式的约束满足问题AC系列算法改进研究[J].软件工程,2018,21(2):30-34.【点击复制】
【打印本页】   【下载PDF全文】   【查看/发表评论】  【下载PDF阅读器】  
←前一篇|后一篇→ 过刊浏览
分享到: 微信 更多
基于启发式的约束满足问题AC系列算法改进研究
蒋李鸣,吕佳宇,何哲华,冯泽斌
(吉林大学软件学院,吉林 长春 130012)
摘 要: 约束满足问题是人工智能领域中一个重要的研究方向,其研究结果在符号推理、系统诊断、真值维护系 统、资源分配和产品配置等问题中有广泛的应用。局部相容性定义了约束满足问题在约束传播过程中必须满足的性质, 是约束传播发展的主要方向。而对于较为复杂的相容性问题中的AC系列算法的改进可谓难上之难。本文围绕着以弧相 容、Singleton弧相容为代表的相容性技术和求解算法展开,主要针对AC-2001算法、SAC算法等进行优化改进,重点 基于启发式进行改进,使之获得了更快的筛选速度。尤其对于SAC算法,大大减少了约束检查次数,获得了较为成功的 基于启发式的改进结果。
关键词: 人工智能;约束满足问题;启发式;AC系列算法;约束检查次数
中图分类号: TP3-0    文献标识码: A
基金项目: 本论文属吉林大学“大学生创新创业训练计划”创新训练项目。由吉林大学软件学院资助。
Heuristic Algorithm Based Improvement of AC Algorithms of Constraint Satisfaction Problems
JIANG Liming,Lv Jiayu,HE Zhehua,FENG Zebin
( College of Software, Jilin University, Changchun 130012, China)
Abstract: In the field of artificial intelligence,the Constraint Satisfaction Problem (CSP) is an important research direction,whose study results are widely used in Symbolic Reasoning,System Diagnosis,Truth Maintenance System,Resource Allocation,and Product Configuration and so on.Local consistency,which defines the properties that CSP must satisfy in the process of constraint propagation,is the main development direction of constraint propagation.It is much more difficult to improve the performance of the complex series of AC algorithms about consistency problems.Based on the algorithms and consistency technology represented by arc consistency and singleton arc consistency,the paper focuses on the improvement of AC-2001 algorithm and SAC algorithm.The improvement is based on the heuristic algorithm to achieve higher filtering speed.Especially,the improvement of SAC algorithm is quite successful because of its obvious reduction of constraint checking times.
Keywords: artificial intelligence;Constraints Satisfaction Problem;heuristic;AC algorithms;constraint checking times


版权所有:软件工程杂志社
地址:辽宁省沈阳市浑南区新秀街2号 邮政编码:110179
电话:0411-84767887 传真:0411-84835089 Email:semagazine@neusoft.edu.cn
备案号:辽ICP备17007376号-1
技术支持:北京勤云科技发展有限公司

用微信扫一扫

用微信扫一扫