吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (04): 1045-1051.doi: 10.7964/jdxbgxb201304032
李占山1,2, 张良1,2, 郭劲松1,2, 张乾1,2
LI Zhan-shan1,2, ZHANG Liang1,2, GUO Jin-song1,2, ZHANG Qian1,2
摘要：
现有启发式方法在处理Composed问题时会生成过多节点,造成求解效率下降。基于此类问题结构特性,设计并实现了一种新的变量排序启发式方法——边界启发式。针对问题结构,提出了边界变量的概念,在Composed问题上实现了对边界变量的筛选,检索过程中,同普通变量相比边界变量被赋予更高的实例化优先级,文中给出了新启发式方法的两种实现策略。实验结果表明,新启发式方法在求解效率上明显优于原有启发式方法。
中图分类号:
| [1] 朱兴军,张永刚,李莹,等. 多值传播的相容性技术[J]. 自动化学报,2009, 35(10):1296-1301. Zhu Xing-jun, Zhang Yong-gang, Li Ying, et al. Consistency technique of multi-value propagation[J]. Acta Automatica Sinica,2009, 35(10):1296-1301.[2] 刘春晖, 朱兴军, 孙吉贵,等. 一种改进的双向Singleton 弧相容算法[J]. 吉林大学学报:工学版, 2008, 38(3): 666-670. Liu Chun-hui, Zhu Xing-jun, Sun Ji-gui, et al. Improved bidirectional Singleton arc consistency algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2008, 38(3): 666-670.[3] 杜会盈,李占山,李宏博,等.图分割在Singleton弧相容算法中的应用[J].吉林大学学报:理学版,2010,48(6):981-986. Dui Hui-ying, Li Zhan-shan, Li Hong-bo,et al. Graph partitioning applied in Singleton algorithm[J]. Journal of Jilin University(Science Edition),2010,48(6):981-986.[4] 高健,孙吉贵,张永刚,等.参数化弧相容约束传播[J].吉林大学学报:信息科学版,2007,25(2):183-187. Gao Jian, Sun Ji-gui, Zhang Yong-gang,et al. Parameterized arc consistency constraint propagation[J]. Journal of Jilin University(Information Science Edition),2007,25(2):183-187.[5] van Beek Peter. Backtracking search algorithms//Handbook of Constraint Programming. Francesca Rossi, Peter van Beek, Toby Walsh (eds),New York: Elsevier, 2006:85-126.[6] Li Xing-jian, Epstein Susan L. Learning cluster-based structure to solve constraint satisfaction problems[J]. Annals of Mathematics and Artificial Intelligence,2010, 60:91-117.[7] Sabin Daniel, Freuder Eugene C. Contradicting conventional wisdom in constraint satisfaction//Proceedings of CP, Rosario, Orcas Island, Washington, 1994: 10-20.[8] Likitvivatanavong Chavalit, Zhang Yuan-lin, Bowen James, et al. Arc consistency during search//Veloso Manuela M (eds.). Proceedings of IJCAI, Hyderabad, India: Morgan Kaufmann, 2007: 137-142.[9] Christophe Lecoutre, Frederic Boussemart, Fred Hemery. Backjump-based techniques versus confict—directed heuristics//Proceedings of ICTAI,Boca Raton, Florida, USA: IEEE Press, 2004: 549-557.[10] Haralick Robert M, Elliott Gordon L. Increasing tree search efficiency for constraint satisfaction problems[J]. Artificial Intelligence, 1980, 14: 263- 313.[11] Grimes Diarmuid, Wallace Richard J. Learning from failures in constraint satisfaction search//Wheeler Ruml, Frank Hutter, AAAI Workshop on Learning for Search, Boston, Massachusetts, USA: AAAI Press, 2006.[12] Christophe Lecoutre, Fred Hemery. A study of residual supports in arc consistency//Veloso Manuela M(eds),Proceedings of IJCAI, Hyderabad, India, 2007: 125-130.[13] Frederic Boussemart, Fred Hemery, Christophe Lecoutre, et al. Boosting systematic search by weighting constraints//R. López De Mántaras, L. Saitta, Proceedings of ECAI, Valencia, Spain: IOS Press, 2004: 146-150.[14] http://www.cril.univ-artois.fr/~lecoutre/benchm arks.html# |
| [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. |
|