贪婪的Singleton弧相容算法的优化

吉林大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (增刊2): 264-268.

贪婪的Singleton弧相容算法的优化

孔垂柳^1,2, 邢士美³, 张浩³

1. 吉林大学交通学院, 长春130022;
2. 吉林建筑工程学院计算机科学与工程学院, 长春130118;
3. 吉林大学计算机与技术学院, 长春130012

收稿日期:2010-05-20 出版日期:2011-09-30 发布日期:2011-09-30
通讯作者: 张浩(1971),男,副教授。研究方向:生物信息学。E-mail:zhangh@jlu.edu.cn E-mail:zhangh@jlu.edu.cn
作者简介:孔垂柳(1972),女,博士研究生。研究方向:人工智能与交通数据流处理。E-mail:kongchuiliu@jliae.Edu.cn
基金资助:
吉林省教育厅科研规划项目[2010]第103号

Optimization of greedy singleton arc consistency

KONG Chui-liu^1,2, XING Shi-mei³, ZHANG Hao³

1. College of Transportation, Jilin Universtiy, Changchun 130022, China;
2. Department of computer Science and Engineer, Jinlin Institue of Architeture and Civil Engineering, Changchun 130118, China;
3. computer Science and Technologyon, Jilin University, Changchun, 130012, China

Received:2010-05-20 Online:2011-09-30 Published:2011-09-30

摘要/Abstract

摘要：

通过记录搜索过程中的有用信息避免了一些无用的约束传播,从而对预处理阶段的Singleton弧相容算法进行了改进,提出了改进的Singleton弧相容算法———SAC3-Revised,它能够减少约束传播的次数和时间。实验结果表明:对于随机问题,当p2在一定范围内取值时,算法效率可提高两倍以上;对于标准测试用例,算法SAC3_Revised的效率也优于SAC-3。

关键词: 人工智能, 相容性技术, 约束满足问题, 弧相容, Singleton弧相容

Abstract:

Storing useful information can avoid useless constraint propagation in the process of algorithm.According to that,Some improvements were made on Singleton Arc Consistency algorithm in the preprocessing step and propose a revised algorithm,denoted SAC3-Revised,which can decrease constraint propagation and time.In our experiments on random CSPs,the efficiency of our algorithm is 2 times of SAC-3 when p2 is in a certain scope and then reaches a steady behavior.Experiments on benchmark show that the efficiency of SAC3_Revised is better than that of SAC-3.

Key words: artificial intelligence, consistency technique, constraint satisfaction problem, arc consistency, Singleton arc consistency

中图分类号:

TP18

孔垂柳, 邢士美, 张浩. 贪婪的Singleton弧相容算法的优化[J]. 吉林大学学报(工学版), 2011, 41(增刊2): 264-268.

KONG Chui-liu, XING Shi-mei, ZHANG Hao. Optimization of greedy singleton arc consistency[J]. 吉林大学学报(工学版), 2011, 41(增刊2): 264-268.

参考文献

[1] Bessiere C,Regin J C.MAC and combined heuristics:two reasons to for sake FC(and CBJ)on hard problems
[C]∥In Proceedings of CP′96,Cambridge,Massachu-setts,USA,Pages:61-75.

[2] Debruyne R,Bessière C.Some practicable filtering techniques for the constraint satisfaction problem
[C]∥In Processings of IJCAI′97:412-417.

[3] Lecoutre C,Cardon S.A greedy approach to establishsingleton arc consistency
[C]∥In Proceedings of IJCAI′ 05,2005:154-160.

[4] Bessiere C.Arc consistency and arc consistency again
[J].AI′2004:179-190.

[5] Bessiere C,Régin J C,Yap R H C.et al.An optimal coarse-grained Arc Consistency algorithm
[J].Artificial Intelligence(AI′2005),2005,165(2):165-185.

[6] BessièreC,Freuder E C,Régin JC.Using inference to reduce arc consistency computation
[C]∥In Proceedings of the IJCAI′95,M ontréal,Québec,Canada,1995: 592-598.

[7] Sun Ji-gui,Zhu Xing-jun,Zhang Yong-gang,et al.Fail first principle for constraint propagation.
[J].Journal of Chinese computer Systems,2008(4):679-681.

[8] Bessière C,Régin J C.Refining the basic constraint propagation algorithm
[C]∥In Proceedings of(IJCAI'2 001),Seattle,Washington,USA,2001:309-315.

[9] Wallace R J,Freuder E C.Ordering heuristics for arc consistency algorithms
[C]∥In AI/GI/VI′92,Vancouver,British Columbia,Canada,1992:163-169.

[10] Bessière C,Debruyne R.Optimal and suboptimal sin-gleton arc consistency algorithms
[C]∥In Proceedings of IJCAI′05,2005:420-428.

相关文章 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