Computer Science ›› 2018, Vol. 45 ›› Issue (6A): 41-45.

• Review • Previous Articles     Next Articles

Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms

ZHANG Yong-gang,CHENG Zhu-yuan   

  1. 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: 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

CLC Number: 

  • TP181
[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.
[1] CHEN Jun, HE Qing, LI Shou-yu. Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor [J]. Computer Science, 2022, 49(8): 237-246.
[2] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[3] HUANG Guo-xing, YANG Ze-ming, LU Wei-dang, PENG Hong, WANG Jing-wen. Solve Data Envelopment Analysis Problems with Particle Filter [J]. Computer Science, 2022, 49(6A): 159-164.
[4] LI Xiao-dong, YU Zhi-yong, HUANG Fang-wan, ZHU Wei-ping, TU Chun-yu, ZHENG Wei-nan. Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring [J]. Computer Science, 2022, 49(5): 371-379.
[5] CHU An-qi, DING Zhi-jun. Application of Gray Wolf Optimization Algorithm on Synchronous Processing of Sample Equalization and Feature Selection in Credit Evaluation [J]. Computer Science, 2022, 49(4): 134-139.
[6] YAO Juan, XING Bin, ZENG Jun, WEN Jun-hao. Survey on Cloud Manufacturing Service Composition [J]. Computer Science, 2021, 48(7): 245-255.
[7] YANG Lin, WANG Yong-jie. Application and Simulation of Ant Colony Algorithm in Continuous Path Prediction of Dynamic Network [J]. Computer Science, 2021, 48(6A): 485-490.
[8] ZHANG Ju, LI Xue-yun. Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm [J]. Computer Science, 2021, 48(6A): 668-672.
[9] LIU Qi, CHEN Hong-mei, LUO Chuan. Method for Prediction of Red Blood Cells Supply Based on Improved Grasshopper Optimization Algorithm [J]. Computer Science, 2021, 48(2): 224-230.
[10] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[11] LIU Hua-ling, PI Chang-peng, LIU Meng-yao, TANG Xin. New Optimization Mechanism:Rain [J]. Computer Science, 2021, 48(11A): 63-70.
[12] WEI Xin, FENG Feng. Optimization of Empire Competition Algorithm Based on Gauss-Cauchy Mutation [J]. Computer Science, 2021, 48(11A): 142-146.
[13] ZHANG Tian-rui, WEI Ming-qi, GAO Xiu-xiu. Prediction Model of Bubble Dissolution Time in Selective Laser Sintering Based on IPSO-WRF [J]. Computer Science, 2021, 48(11A): 638-643.
[14] CUI Guo-nan, WANG Li-song, KANG Jie-xiang, GAO Zhong-jie, WANG Hui, YIN Wei. Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application [J]. Computer Science, 2021, 48(10): 197-203.
[15] LI Yang, LI Wei-gang, ZHAO Yun-tao, LIU Ao. Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy [J]. Computer Science, 2020, 47(8): 291-296.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!