[1]李颖,杨罡,李占山.维持弧的唯一性优化粗粒度弧相容算法[J].哈尔滨工程大学学报,2018,39(04):744-750.[doi:10.11990/jheu.201610104]
 LI Ying,YANG Gang,LI Zhanshan.Optimized coarse-grained arc-consistency algorithm for maintaining the uniqueness of arc[J].hebgcdxxb,2018,39(04):744-750.[doi:10.11990/jheu.201610104]
点击复制

维持弧的唯一性优化粗粒度弧相容算法(/HTML)
分享到:

《哈尔滨工程大学学报》[ISSN:1006-6977/CN:61-1281/TN]

卷:
39
期数:
2018年04期
页码:
744-750
栏目:
出版日期:
2018-04-05

文章信息/Info

Title:
Optimized coarse-grained arc-consistency algorithm for maintaining the uniqueness of arc
作者:
李颖 杨罡 李占山
吉林大学 计算机科学与技术学院, 吉林 长春 130012
Author(s):
LI Ying YANG Gang LI Zhanshan
College of Computer Science and Technology, Jilin University, Changchun 130012, China
关键词:
人工智能约束满足问题维持弧相容粗粒度算法哈希算法唯一预处理一致性冗余回溯
分类号:
TP18
DOI:
10.11990/jheu.201610104
文献标志码:
A
摘要:
针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(arc corsistency,AC)执行过程中对于弧存在冗余的放回操作,并证明了这类放回是冗余的。同时提出一种改进方法AC_AO,避免这类冗余的弧放回操作,从而保证了弧的唯一性。改进后框架可用于改进所有的粗粒度弧相容算法。实验结果表明,经过AC_AO改进后的算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间。这将大大减少修正函数的调用次数,从而提高AC的执行效率,应用在维持弧相容算法求解的过程中提高效率是非常有意义的。

参考文献/References:

[1] ROSSI F, VAN BEEK P, WALSH T. Handbook of constraint programming[M]. Amsterdam, Netherlands:Elsevier Science, 2006:26-49.
[2] ZHOU Jianwei. Improved optimal conditions and iterative parameters for the optimal control problems with an integral constraint in square[J]. Journal of computational and applied mathematics, 2016, 307:367-373.
[3] HAN Jiangfeng, MIGÍRSKI S. A quasistatic viscoelastic frictional contact problem with multivalued normal compliance, unilateral constraint and material damage[J]. Journal of mathematical analysis and applications, 2016, 443(1):57-80.
[4] MACKWORTH A K. Consistency in networks of relations[J]. Artificial intelligence, 1977, 8(1):99-118.
[5] CAI Shaowei, SU Kaile. Local search for Boolean Satisfiability with configuration checking and subscore[J]. Artificial intelligence, 2013, 204:75-98.
[6] CHOI C W, LEE J H M, STUCKEY P J. Removing propagation redundant constraints in redundant modeling[J]. ACM transactions on computational logic, 2007, 8(4):23.
[7] BOUSSEMART F, HEMERY F, LECOUTRE C. Revision ordering heuristics for the Constraint Satisfaction Problem[C]//Proceedings of the 1st International Workshop on Constraint Propagation and Implementation held with CP’04(CPAI’04). Toronto, Canada, 2004:9-43.
[8] LEE J H M, ZHU Zichen. Boosting SBDS for partial symmetry breaking in constraint programming[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014). Québec City, Québec, Canada, 2014:2695-2702.
[9] MEHTA D, VAN DONGEN M R C. Reducing checks and revisions in coarse-grained MAC algorithms[C]//Proceedings of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, UK, 2005:236-241.
[10] LEE J H M, LEUNG K L. A stronger consistency for soft global constraints in weighted constraint satisfaction[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-2010). Atlanta, USA, 2010:121-127.
[11] LECOUTRE C. Constraint networks:techniques and algorithms[M]. Great Britain, Narendra Jussien, United States:Wiley, 2009:185-236.
[12] JAVED K, GOURIVEAU R, ZERHOUNI N, et al. Prognostics of proton exchange membrane fuel cells stack using an ensemble of constraints based connectionist networks[J]. Journal of power sources, 2016, 324:745-757.
[13] 王瑞伟, 李占山, 李宏博. 求解约束可满足问题的eSTR算法优化[J]. 计算机研究与发展, 2016, 53(7):1586-1595.WANG Ruiwei, LI Zhanshan, LI Hongbo. Optimizing eSTR algorithm for solving constraint satisfaction problems[J]. Journal of computer research and development, 2016, 53(7):1586-1595.
[14] 王涛, 张乾, 李占山, 等. 基于成功回溯的约束推理技术[J]. 吉林大学学报(工学版), 2016, 46(5):1622-1626.WANG Tao, ZHANG Qian, LI Zhanshan, et al. Reasoning from successful backtracking in constraint programming[J]. Journal of Jilin University (engineering and technology edition), 2016, 46(5):1622-1626.
[15] 李宏博, 梁艳春, 李占山. 概率最大受限路径相容算法[J]. 软件学报, 2015, 26(12):3140-3150.LI Hongbo, LIANG Yanchun, LI Zhanshan. Probabilistic max restricted path consistency[J]. Journal of software, 2015, 26(12):3140-3150.
[16] 李宏博, 李占山, 王涛. 改进求解约束满足问题粗粒度弧相容算法[J]. 软件学报, 2012, 23(7):1816-1823.LI Hongbo, LI Zhanshan, WANG Tao. Improving coarse-grained arc consistency algorithms in solving constraint satisfaction problems[J]. Journal of software, 2012, 23(7):1816-1823.

相似文献/References:

[1]孙宇嘉,王晓鸣,贾方秀,等.封锁雷智能防排系统[J].哈尔滨工程大学学报,2014,(05):580.[doi:10.3969/j.issn.10067043.201303071]
 SUN Yujia,WANG Xiaoming,JIA Fangxiu,et al.An intelligent anti removal system for blockage mines[J].hebgcdxxb,2014,(04):580.[doi:10.3969/j.issn.10067043.201303071]

备注/Memo

备注/Memo:
收稿日期:2016-10-28。
基金项目:国家自然科学基金项目(61272208,61373052);吉林省科技计划项目(20180101043JC).
作者简介:李颖(1965-),女,教授,博士生导师;李占山(1966-),男,教授,博士生导师.
通讯作者:李占山,E-mail:lizs@jlu.edu.cn
更新日期/Last Update: 2018-04-11