最大受限路径相容约束传播算法的研究进展

计算机科学 ›› 2018, Vol. 45 ›› Issue (6A): 41-45.

最大受限路径相容约束传播算法的研究进展

张永刚,程竹元

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

出版日期:2018-06-20 发布日期:2018-08-03
作者简介:张永刚(1975-),男,博士,副教授,CCF会员,主要研究方向为约束求解与优化,E-mail:410759804@qq.com;程竹元(1993-),女,硕士生,CCF会员,主要研究方向为约束求解与优化,E-mail:qing_luo_xiao_shan@163.com(通信作者)。
基金资助:
国家自然科学基金项目(61170314,61373052),吉林省科技发展计划项目(20170414004GH)资助

Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms

ZHANG Yong-gang,CHENG Zhu-yuan

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

Online:2018-06-20 Published:2018-08-03

摘要/Abstract

摘要： 约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。

关键词: 相容性技术, 优化算法, 约束求解, 最大受限路径相容算法

Abstract: Constrained propagation technology is critical to the performance of constraint satisfaction problems.Constrained propagation technology completely removes some local inconsistency values during a preprocessing process,or efficiently pruning the search tree during the search.The max restricted path consistency algorithm (maxRPC) is astrong consistency constraint propagation algorithm proposed recently,which can remove more inconsistent values,and achieves good results in solving complex problems.In this paper,some algorithms,such as AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3 and other related algorithms which are related to the arc consistency algorithm AC and max restricted path consistency algorithm maxRPC,were introduced respectively and compared with each other.The performance of the proposed algorithm is verified by the experimental results on the mistral solver.

Key words: Consistency technology, Constraint solving, Max restricted path consistency algorithm, Optimization algorithm

中图分类号:

TP181

张永刚, 程竹元. 最大受限路径相容约束传播算法的研究进展[J]. 计算机科学, 2018, 45(6A): 41-45. https://doi.org/

ZHANG Yong-gang, CHENG Zhu-yuan. Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms[J]. Computer Science, 2018, 45(6A): 41-45. https://doi.org/

参考文献

[1]FRANCESCA R.Handbook of constraint programming [M].Netherlands:Elsevier,2006:15-18.
[2]GENT I,WALSH T.CSPlib:A Benchmark Library for Constraints[C]∥Proceedings of CP-99.1999.
[3]BESSIERE C,REGIN J C,YAP R H C,et al.An Optimal Coarse-grained Arc Consistency Algorithm [J].Artificial Intelligence,2005,165(2):165-185.
[4]MACKWORTH A.Consistency in Networks of Relations .Artificial Intelligence,1981,8(1):69-78.
[5]LICOUTRE C,HEMERY F.A study of residual supports in arc consistency∥International Joint Conference on Artifical Intelligence.Morgan Kaufmann Publishers Inc.,2007:125-130.
[6]COHEN D,JEAVONS P,KOUBARAKIS M.Tractable disjunctive constraints∥International Conference on Principles and Practice of Constraint Programming.Springer Berlin Heidelberg,1997:478-490.
[7]刘春晖.基于约束传播的约束求解方法研究[D].长春:吉林大学,2008.
[8]BERLANDIER P.Improving domain filtering using restricted path consistency[C]∥Artificial Intelligence for Applications.Los Angeles:CA,1995:32.
[9]DEBRUYNE R,BESSIERE C.From restricted path consistency to max-restricted path consistency∥Principles and Practice of Constraint Programming－CP97.Springer Berlin Heidelberg,1997:312-326.
[10]STERGIOU K.Restricted Path Consistency Revisited∥Principles and Practice of Constraint Programming.Springer International Publishing,2015.
[11]STUCKEY P J,FEYDY T,SCHUTT A,et al.The MiniZinc Challenge 2008-2013 [J].AI Magazine,2014,35(2):55-60.
[12]SABIN D,FREUDER E C.Contradicting Conventional Wisdom in Constraint Satisfaction[C]∥Proceedings of CP-1994.1999:10-20.
[13]GRANDONI F,ITALIANO G F.Improved Algorithms for Max-restricted Path Consistency [C]∥Principles & Pratice of Constraint Programming-cp.Kinsale:Cp,2003:858-862.
[14]VION J,DEBRUYNE R.Light Algorithms for Maintaining Max-RPC During Search ∥Proceedings of SARA’09.2010:167-174.
[15]HARALICK R M,ELLIOTT G L. Increasing Tree Search Efficiency for Constraint Satisfaction Problems .Artificial Intelligence,1980,14(3):263-313.
[16]DECHTER R,MEIRI I.Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems[C]∥International Joint Conference on Artificial Intelligence (IJCAI-1989).1989:271-277.
[17]BALAFOUTIS T,PAPARRIZOU A,STERGIOU K,et al.New Algorithms for Max Restricted Path Consistency [J].Constraints,2011,16(4):372-406.
[18]Christophe Lecoutre.http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.
[19]崔佳旭.Mistral求解器扩展与应用研究[D].长春:吉林大学,2016.

相关文章 15

[1]	陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[2]	黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文. 利用粒子滤波方法求解数据包络分析问题 Solve Data Envelopment Analysis Problems with Particle Filter 计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110
[3]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
[4]	储安琪, 丁志军. 基于灰狼优化算法的信用评估样本均衡化与特征选择同步处理 Application of Gray Wolf Optimization Algorithm on Synchronous Processing of Sample Equalization and Feature Selection in Credit Evaluation 计算机科学, 2022, 49(4): 134-139. https://doi.org/10.11896/jsjkx.210300075
[5]	屈立成, 吕娇, 屈艺华, 王海飞. 基于模糊神经网络的运动目标智能分配定位算法 Intelligent Assignment and Positioning Algorithm of Moving Target Based on Fuzzy Neural Network 计算机科学, 2021, 48(8): 246-252. https://doi.org/10.11896/jsjkx.200600050
[6]	姚娟, 邢镔, 曾骏, 文俊浩. 云制造服务组合研究综述 Survey on Cloud Manufacturing Service Composition 计算机科学, 2021, 48(7): 245-255. https://doi.org/10.11896/jsjkx.200800173
[7]	杨林, 王永杰. 蚁群算法在动态网络持续性路径预测中的运用及仿真 Application and Simulation of Ant Colony Algorithm in Continuous Path Prediction of Dynamic Network 计算机科学, 2021, 48(6A): 485-490. https://doi.org/10.11896/jsjkx.200800132
[8]	章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究 Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm 计算机科学, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118
[9]	张蔷, 黄樟灿, 谈庆, 李华峰, 湛航. 基于动态近邻套索算子的金字塔演化策略 Pyramid Evolution Strategy Based on Dynamic Neighbor Lasso 计算机科学, 2021, 48(6): 215-221. https://doi.org/10.11896/jsjkx.200400115
[10]	刘奇, 陈红梅, 罗川. 基于改进的蝗虫优化算法的红细胞供应预测方法 Method for Prediction of Red Blood Cells Supply Based on Improved Grasshopper Optimization Algorithm 计算机科学, 2021, 48(2): 224-230. https://doi.org/10.11896/jsjkx.200600016
[11]	刘华玲, 皮常鹏, 刘梦瑶, 汤新. 一种新的优化机制:Rain New Optimization Mechanism:Rain 计算机科学, 2021, 48(11A): 63-70. https://doi.org/10.11896/jsjkx.201100032
[12]	魏昕, 冯锋. 基于高斯-柯西变异的帝国竞争算法优化 Optimization of Empire Competition Algorithm Based on Gauss-Cauchy Mutation 计算机科学, 2021, 48(11A): 142-146. https://doi.org/10.11896/jsjkx.201200071
[13]	崔国楠, 王立松, 康介祥, 高忠杰, 王辉, 尹伟. 结合多目标优化算法的模糊聚类有效性指标及应用 Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application 计算机科学, 2021, 48(10): 197-203. https://doi.org/10.11896/jsjkx.200900061
[14]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[15]	宋岩, 胡瑢华, 郭福民, 袁新亮, 熊睿洋. 基于sEMG的改进SVM+BP肌力预测分层算法 Improved SVM+BP Algorithm for Muscle Force Prediction Based on sEMG 计算机科学, 2020, 47(6A): 75-78. https://doi.org/10.11896/JsJkx.190900143

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed