吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (1): 229-235.doi: 10.13229/j.cnki.jdxbgxb201501034
李占山1，2，贾湘华1，2，许苍竹1，2，张舒娟1，2
LI Zhan-shan1,2,JIA Xiang-hua1,2,XU Cang-zhu1,2,ZHANG Shu-juan1,2
摘要： 针对绝大多数不可满足问题的特点，提出了一种将弧相容算法与最大限定路径相容算法相结合的相容性算法——基于论域折半的最大限定路径相容的算法。该算法充分利用了弧相容计算开销小和最大限定相容删值能力强的优点，可以减少在求解不可满足问题中生成的结点数，进而提高求解效率。实验结果表明，本文算法在处理不可满足问题时的求解效率明显优于传统的维持弧相容算法。
中图分类号:
| [1] Sabin Daniel, Freuder Eugene C. Contradicting conventional wisdom in constraint satisfaction[C]∥Proceedings of CP, Rosario, Orcas Island, Was- hington, 1994: 10-20. [2] Likitvivatanavong Chavalit,Zhang Yuan-lin, Bowen James,et al.Arc consistency during search[C]∥Proceedings of IJCAI, India: Morgan Kaufmann, 2007: 137-142. [3] Mackworth Alan K.Consistency in networks of relations[J]. Artificial Intelligence, 1977,8(1): 99-118. [4] Christophe Lecoutre, Fred Hemery. A study of residual supports in arc consistency[C]∥Proceeding of IJCAI, 2007:125-130. [5] Christophe Lecoutre, Julien Vion. Enforcing arc consistency using bitwise operations[J]. Const- raint Programming Letters,2008(2): 21-35. [6] Romuald Debruyne, Christian Bessiere. Some practical filtering techniques for the constraint satisfaction problem[C]∥Proceedings of IJCAI, 1997: 412-417. [7] Romuald Debruyne, Christian Bessiere. From restricted path consistency to max-restricted path consistency[C]∥Proceedings of CP, 1997: 312-326. [8] Thanasis Balafoutis, Anastasia Paparrizou, Kostas Stergiou, et al. New algorithms for max restricted path consistency[J]. Constraints, 2011,16(4): 372-406. [9] Christophe Lecoutre, Patrick Prosser. Maintaining singleton arc consistency[C]∥Proceedings of CPAI, 2006: 47-61. [10] Julien Vion, Romuald Debruyne. Light algorithms for maintaining max-RPC during search[C]∥Proceedings of SARA,2009. [11] Possi Francesca, Van Beek Peter, Walsh Toby. Handbook of Constraint Programming[M] .New York: Elsevier, 2006:13-29. [12] Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, et al. Boosting systematic search by weighting constraints[C]∥Proceedings of ECAI, 2004: 146-150. [13] 李占山,张良,郭劲松,等.基于问题结构的边界启发式方法[J].吉林大学学报:工学版,2013,43(5):1045-1051. Li Zhan-shan, Zhang Liang, Guo Jin-song, et al. Boundary heuristic based on problem structure[J]. Journal of Jilin University (Engineering and Technology Edition), 2013, 43(4):1045-1051. |
| [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. |
|
||