一种改进的双向singleton弧相容算法

吉林大学学报(工学版)

一种改进的双向singleton弧相容算法

刘春晖;朱兴军;孙吉贵;姜珊珊

吉林大学计算机科学与技术学院，符号计算与知识工程教育部重点实验室，长春 130012

收稿日期:2007-06-13 修回日期:2007-07-13 出版日期:2008-05-01 发布日期:2008-05-01
通讯作者: 刘春晖

Improved bidirectional singleton arc consistency algorithm

Liu Chun-hui;Zhu Xing-jun;Sun Ji-gui;Jiang Shan-shan

College of Computer Science and Technology, Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Received:2007-06-13 Revised:2007-07-13 Online:2008-05-01 Published:2008-05-01

摘要/Abstract

摘要：

在现有相容性算法研究的基础上，提出了一种在约束网络中确立双向singleton弧相容的新算法——BiSAC-2，并给出了其正确性和完备性证明。该算法与原有算法BiSAC-1具有相同的化简问题能力，但BiSAC-2能够减少弧相容维护的次数，避免冗余约束传播过程的产生，从而可以快速地到达稳定点，进而实现高效的目的。对随机约束满足问题的测试结果表明，算法BiSAC-2比原始算法BiSAC-1具有更明显的性能优势。

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

Abstract: The existing notions and techniques of consistency algorithm were further investigated. Then a new algorithm——BiSAC-2 was proposed to enforce the bidirectional singleton arc consistency in constraint network. The soundness and completeness of the algorithm were proved. BiSAC-2 has the same ability to simplify the problem as that of the conventional BiSAC-1. However the number for maintaining the arc consistency is reduced and the fixpoint can be reached much quickly, hence the efficiency can be improved. Experiments on random CSPs show that the new algorithm, BiSAC-2, needs much less time compared with the conventional algorithm BiSAC-1.

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

中图分类号:

TP31

刘春晖;朱兴军;孙吉贵;姜珊珊 . 一种改进的双向singleton弧相容算法[J]. 吉林大学学报(工学版), 2008, 38(03): 666-0670.

Liu Chun-hui;Zhu Xing-jun;Sun Ji-gui;Jiang Shan-shan. Improved bidirectional singleton arc consistency algorithm[J]. 吉林大学学报(工学版), 2008, 38(03): 666-0670.

参考文献

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