期刊专题

10.3969/j.issn.1002-137X.2013.12.052

弧一致性符号ADD算法及在CSP求解中的应用

引用
约束满足问题(CSP)是人工智能领域中一个重要的研究课题,弧一致性(AC)技术是提高约束满足问题求解效率的一种有效技术.对传统弧一致性技术进行了改进,给出了弧一致性的符号代数决策图(ADD)算法并将其应用于CSP求解.传统弧一致性技术在压缩问题的搜索空间时,一次只能处理一条约束上的一个值对;而借助ADD技术来压缩问题搜索空间,可以一次处理多条约束.算法首先通过01编码将CSP问题描述成伪布尔函数,并由ADD进行表示.然后基于传统弧一致性技术的算法思想,利用ADD的交、并和提取操作来实现约束传播和变量域过滤.最后将弧一致性的符号ADD算法嵌入到BT搜索算法中来实现对CSP的求解.对标准库中的测试用例以及随机生成的测试用例进行了实验仿真,结果表明,该算法求解CSP的时间既优于带弧一致性维护的回跳算法MAC3+BJ和MAC2001+ BJ,也优于采用传统数据结构进行预处理的CSP求解算法BT+ MPAC和BT+ MPAC*.

约束满足问题(CSP)、代数决策图(ADD)、弧一致性(AC)

40

TP301(计算技术、计算机技术)

国家自然科学基金60963010,61100025,61262030;广西研究生教育创新计划2011105950812M23

2014-01-19(万方平台首次上网日期,不代表论文的发表时间)

共5页

243-247

暂无封面信息
查看本期封面目录

计算机科学

1002-137X

50-1075/TP

40

2013,40(12)

专业内容知识聚合服务平台

国家重点研发计划“现代服务业共性关键技术研发及应用示范”重点专项“4.8专业内容知识聚合服务技术研发与创新服务示范”

国家重点研发计划资助 课题编号:2019YFB1406304
National Key R&D Program of China Grant No. 2019YFB1406304

©天津万方数据有限公司 津ICP备20003920号-1

信息网络传播视听节目许可证 许可证号:0108284

网络出版服务许可证:(总)网出证(京)字096号

违法和不良信息举报电话:4000115888    举报邮箱:problem@wanfangdata.com.cn

举报专区:https://www.12377.cn/

客服邮箱:op@wanfangdata.com.cn