基于成功回溯的约束推理技术

doi:10.13229/j.cnki.jdxbgxb201605035

吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (5): 1622-1626.doi: 10.13229/j.cnki.jdxbgxb201605035

基于成功回溯的约束推理技术

王涛¹, 张乾^2,3, 李占山^2,3, 张良^2,3

1.长春工业大学计算机科学与工程学院,长春 130012;
2.吉林大学计算机科学与技术学院, 长春 130012;
3.吉林大学符号计算与知识工程教育部重点实验室,长春 130012

收稿日期:2015-11-15 出版日期:2016-09-20 发布日期:2016-09-20
通讯作者: 李占山(1966-),男,教授,博士生导师.研究方向:约束求解,模型诊断,智能规划与调度.E-mail:zslizsli@163.com
作者简介:王涛(1969-),女,副教授.研究方向:约束程序与模型诊断.E-mail:wangtao690103@163.com
基金资助:
国家自然科学基金项目(61170314, 61272208); 吉林省科技发展计划项目(20140101200JC,20071106); 教育部高等学校博士学科点专项科研基金项目(20100061110031).

Reasoning from successful backtracking in constraint programming

WANG Tao¹, ZHANG Qian^2,3, LI Zhan-shan^2,3, ZHANG Liang^2,3

1.School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China;
2.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
3.Key Laboratory of Symbolic Computation and Knowledge Engineering, Ministry of Education, Jilin University, Changchun 130012, China

Received:2015-11-15 Online:2016-09-20 Published:2016-09-20

摘要/Abstract

摘要： 提出了基于成功回溯的约束推理技术及其相应的约束求解算法MAC_BTS,并证明了该算法在一条分枝上回溯到网络相容状态的最坏时间复杂度是O(ned³)。实验结果表明:新的MAC_BTS算法在大多数问题的求解上较国际上流行的MAC3rm算法以及MAC_LC算法取得了10%~20%的加速,甚至在某些问题上达到50%,可见该算法在效率上更优。

关键词: 人工智能, 约束满足问题, 约束推理, 成功回溯

Abstract: A new reasoning method based on successful backtracking is proposed, and a new corresponding constraint solving algorithm, named MAC_BTS, is developed. It is proved that the worst-case time complexity is O(ned³) on a branch. A large number of experimental results show that the proposed algorithm, MAC_BTS, is more efficient, which can obtain the accelerations about 10% to 20% (even 50% in some problems) compared with the popular existing constraint solving algorithms MAC3rm and MAC_LC.

Key words: artificial intelligence, constraint satisfaction problem, constraint reasoning, successful backtracking

中图分类号:

TP301

王涛, 张乾, 李占山, 张良. 基于成功回溯的约束推理技术[J]. 吉林大学学报(工学版), 2016, 46(5): 1622-1626.

WANG Tao, ZHANG Qian, LI Zhan-shan, ZHANG Liang. Reasoning from successful backtracking in constraint programming[J]. 吉林大学学报(工学版), 2016, 46(5): 1622-1626.

参考文献

[1] Freuder E C, Mackworth A K. Constraint Satisfaction: an Emerging Paradigm[M]. Amsterdam: Elsevier, 2006: 13-27.
[2] Bessière C. Constraint Propagation[M]. Amsterdam: Elsevier, 2006: 29-84.
[3] Van Beek P. Backtracking Search Algorithms[M]. Amsterdam: Elsevier, 2006: 85-134.
[4] Schiex T, Verfaillie G. Nogood recording for static and dynamic constraint satisfaction problems[J]. Int Journal on Artificial Intelligence Tools, 1994, 3(2): 187-207.
[5] Lecoutre C, Sais L, Tabary S, et al. Transposition tables for constraint satisfaction[C]∥Proc of AAAI'07. Menlo Park, CA: AAAI Press, 2007: 243-248.
[6] Lecoutre C, Sais L, Tabary S, et al. Reasoning from last conflict(s) in constraint programming[J]. Artificial Intelligence, 2009, 173(18): 1592-1614.
[7] Mackworth A K. Consistency in networks of relations[J]. Artificial Intelligence, 1977, 8(1): 99-118.
[8] Sabin D, Freuder E C. Contradicting conventional wisdom in constraint satisfaction[C]∥Principles and Practice of Constraint Programming 1994. Berlin: Springer, 1994: 10-20.
[9] Lecoutre C, Hemery F. A study of residual supports in arc consistency[C]∥Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2007: 125-130.
[10] Boussemart F, Hemery F, Lecoutre C, et al. Boosting systematic search by weighting constraints[C]∥Proc of the 16th European Conf on Artificial Intelligence. Hoboken, NJ: John Wiley & Sons, 2004: 146-150.
[11] Gent I P, Macintyre E, Prosser P, et al. Random constraint satisfaction: flaws and structure[J]. Constraints, 2001, 6(4): 345-372.
[12] Lecoutre C. Benchmarks of constraint satisfaction problem[EB/OL].[2012-04-16]. http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.

相关文章 15

[1]	董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577.
[2]	顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585.
[3]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4]	张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5]	黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6]	李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7]	刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8]	王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9]	杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10]	刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11]	曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[12]	李嘉菲, 孙小玉. 基于谱分解的不确定数据聚类方法[J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[13]	邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[14]	王生生, 王创峰, 谷方明. OPRA方向关系网络的时空推理[J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[15]	马淼, 李贻斌. 基于多级图像序列和卷积神经网络的人体行为识别[J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于成功回溯的约束推理技术

Reasoning from successful backtracking in constraint programming

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10