Research On The Singleton Arc Consistency Based On Greedy Approach

Constraint satisfaction problem is an important branch in artificial intelligence, its representation can modeling the question in the real world, which will be abstracted as constraint satisfaction problems and solving the model has been widely applied in the configuration, scheduling, planning, network, bioinformatics and many other fields. The goal of solving a constraint satisfaction problem is to find a solution or prove it has no solution. To solve a constraint satisfaction problem often combine search and reasoning methods. Searching technology used to traverse all the variables in the current domain to find the solution. Reasoning technology using the variable elimination, tree decomposition technology and compatibility technology, so the problem can be converted to an equivalent problem that it easier to be solved.Compatibility technology has two main functions: in the preprocessing stage, take resonable and effective compatibility technology can remove those values who will not exist in the scope of the solution; In the searching stage, using the compatibility technology to strengthen the network, helping determine whether the current extension node of the search tree is correct or not. The research of compatibility technology has always been a hot issue in the field of constraint solving.The compatibility of common technology includes: AC, PC, max RPC, SAC, etc.The main problem of heuristics in solving constraint satisfaction problem is how to use the current information in the network to guide the instantiation order of variables and values. How to select the following compatibility check of a variable’s value in constraint propagation directly affects the solution efficiency of the algorithm. Deleting the values do not meet the compatibility at the beginning of the solving could avoid redundant compatibility check in the following constraint propagation, so as to improve the solution efficiency of the algorithm.This paper first introduces the relevant background knowledge about constraint satisfaction problem including the common compatibility algorithms, MAC(Maintaining Arc Consistency) and heuristic method in the process of solving to guide the search process. Due to the compatibility technology and heuristic methods are the key factors in the constraint satisfaction problem solving. In this paper, we study singleton arc consistency in the compatiblitity technology, joining the heuristic assignment strategy on the basis of the existing SAC3 algorithm, putting forward the improved SAC3_avg Sup algorithm, specific work is as follows:The main idea of SAC3_avg Sup algorithm is: adopting dynamic heuristic strategy in the process of constraint check based on the depth-first search, treating the values in the transmission queue Qsac by the number of average support variable in ascending order(the support number of variable/the size of variable domain). Giving prority to assignment the value which has the smallest average number of support. If a variable has the smaller average number of support, the possibility of expansion for the solution is lower, the higher the possibility of becoming a dead nodes. The purpose is to determine the dead nodes in advance, thereby reducing the inspections and the execution time of the algorithm.The experimental result is rendered by SAC3 algorithm and SAC3_avg Sup algorithm proposed in this paper respectively solving the problem of benchmark and random test cases. The Evaluation standard is the CPU time in solving, the number of generated nodes in the instantiation process and the number of constraint checking.The experimental results show that, in most problems, SAC3_avg Sup has a better performance than SAC3 algorithm in timing properties, the number of generated node and the number of constraint checking has also decreased significantly.Generally speaking, SAC3_avg Sup algorithm has a better performance.