The Research On Constraint Propagation Algorithm Based On Restricted Path Consistency

Constraint Programming(CP)is a classical method for solving combinatorial optimization problems,and has played an important role in the transportation,telecommunications,education and other fields.CP has now been successfully applied to many problems such as vehicle routing problems,scheduling problems,configuration problems and biological information.The core issue of CP research is the modeling and solving of Constraint Satisfaction Problem(CSP).Many complex problems in the field of artificial intelligence can be modeled as CSP.The modeling and solving methods based on CSP are the hot topics in current research.The method of backtracking search combined with constraint propagation is currently recognized as the best CSP solving method.The consistency algorithm is the main algorithm used in the constraint propagation process,the consistency algorithm is also an important factor influencing the efficiency of constraint solving.In general,CSP rely on a backtracking framework to search.During the search process,they continuously reduce the search space of the solving by removing the values that are not consistent,this greatly speeds up algorithm search efficiency.The classical consistency algorithms are Arc Consistency(AC)algorithm,Path Consistency(PC),Singleton Arc Consistency(SAC)algorithm,Restricted Path Consistency(RPC)algorithm and max-Restricted Path Consistency(maxRPC)algorithm.Among them,AC,RPC,and maxRPC are the three most popular and most effective consistency algorithms.The AC algorithm is simple and efficient,and is widely used.The maxRPC algorithm has strong pruning ability,especially for solving large and difficult problems,the lmaxRPC3rm(light-max RPC3-residues multidirectional)algorithm is a superior and efficient algorithm in the maxRPC algorithm.RPC algorithm does not require too much space and time overhead while maintaining a strong pruning capability.Its latest and best algorithm rRPC3 hasIV proved to be able to achieve the same effect as the AC in solving many problems,and even better than AC in some problems,so the rRPC3 algorithm is a very promising algorithms.Heuristic is a strategy that guides the assignment variables and values during algorithmic solving.A good heuristic for variable ordering heuristics(value ordering heuristic)can correctly guide the choice of variables(values),greatly reducing the searching time,speeding the search solution process,so heuristic strategy plays an important role in solving CSP.In this paper,we study the RPC and maxRPC,based on the very promising rRPC3 algorithm and the effect of the lmaxRPC3 rm algorithm to improve.The specific work is:(1)Improving to RPC Algorithms: The idea of bit manipulation combined with the consistency algorithms has proven to be very good in several important consistency algorithms.We use bit manipulation ideas to improve rRPC3 algorithm.Because searching AC support,PC support and PC witness are the most extensive and time consuming steps in algorithms,so it's important to speed up the process of searching for support and witnesses.According to the bit efficient and fast features,we improved the process of searching for AC support,PC support,and PC witness using a bit manipulation structure,make the algorithm search and access consistency support and PC witness process more convenient and efficient,so as to achieve the purpose of accelerating the search to the solution.(2)Improving to maxRPC algorithm: lmaxRPC3 rm algorithm has the strong pruning ability,but the large space-time overhead is large.We improve the lmaxRPC3 rm from two aspects of algorithm content and heuristics.First,two improved algorithms are proposed for lmaxRPC3 rm algorithm.The first improvement does not use the AC support LastAC and PC-support LastPC to store residues from original algorithm,making the algorithm efficient and easy to implement while reducing time and space consumption.The second improvement differs from the way that the lmaxRPC3 rm algorithm uses both AC residual support and PC residual support.The improved algorithm uses only one kind of residual support to storeconsistency support so as to storage and search for AC support,PC support and PC witnesses,which can reduce the access of many redundant residuals to support,thus making the algorithm more efficient while reducing the time and space overhead.In addition,we improved the lmaxRPC3 rm algorithm by applying improved variable ordering heuristics.An improved heuristic ADW(Activity+dom/wdeg)is proposed based on dom/wdeg(domain/weighted degree)and ABS heuristics,and improved heuristic ADW are applied in two improved algorithms to further improve algorithm efficiency.We improved the rRPC3 and lmaxRPC3 rm algorithms respectively and verified the improved algorithm effects through experiments.The rRPC3 algorithm uses a bit manipulation data structure to optimize the search support and storage support process so that the algorithm achieves better results.The lmaxRPC3 rm algorithm is improved by using the idea of reducing redundant residual support access,so that the algorithm can achieve a balance between pruning ability and overhead,thereby speeding up the algorithm search process and speeding up the efficiency.At the same time,we apply improved heuristics of variable ordering to improved lmaxRPC3 rm algorithm to make improved algorithms have better results.Experiments show that our improved algorithms have obvious results.In the future,we intend to use bit manipulation to improve the lmaxRPC3 rm algorithm and apply ADW to the improved rRPC3 algorithm.