Research On Heuristic Methods Based On Singleton-Domain Variables

Constraint satisfaction problem(CSP)[1]is a Non-deterministic Polynomial problem and became an important branch in the field of artificial intelligence since the beginning of the constraint program in 1965 and a research hotspot in the field of artificial intelligence since 1985.Many practical problems can be modeled by constraint satisfied problem,such as the N-queens,Temporal reasoning,Resource allocation,Scheduling and so on.At the same time,constraint programming has been widely used in the fields of Bioinformatics,Vision and Operation research.With the increasing scale of the problem of constraint satisfaction problem,the requirement of solving efficiency is improved.Backtracking algorithm used constraint propagation technique is applied widely at present[2].Constraint propagation in the process of backtracking can reduce the search space and improve the efficiency.Because of the larger scale of problems and the need to constantly instantiate the variables and values in the process of,"Combination Explosion" phenomenon[2]often appears which makes the problem difficult to get effective solution within the effective time.Therefore,not only the size of the search space but also variable instantiation order is an important factor affecting the efficiency of a backtracking algorithm to solve a CSP[2].A good variable instantiation order can greatly reduce the number of nodes in the search process and the problem will be solved more quickly.The purpose of the heuristic algorithm is to get a better variables instantiation order.According to whether the instantiation order of the variables can be changed in the solving process,the heuristic algorithm is divided into two types.One is that the instantiation order of variables is determined before the start of search and cannot be changed in the solving process,which is called static heuristic.The other is that the instantiation order of variables is determined or constantly changing in the process of the search,which is called dynamic heuristic.At present,dynamic heuristic is the most widely used in the practical application.Many successful variable ordering heuristics have been proposed,such as DOM[3]heuristic based on variable domain size,dom/ddeg[4]heuristic which combines the number of constraints related to the variables with the variable domain size,dom/wdeg[5]heuristic which associates a weight for each constraint and adds up the weights of the constraints involving this variable as a score and combines this score with the variable domain size.And for the heuristic value,there is no general heuristic method.In this paper,we introduce and analyze classical heuristics and combine the useful information in the process of constraint propagation with the classical heuristic to improve the solving efficiency.The details are listed as follows:(1)Introduce and analyze the existing classical heuristics.At present,dynamic heuristic is the most widely used in the practical application,so this paper mainly introduces and analyzes various kinds of classical dynamic heuristics.This paper introduces the application of various heuristic algorithms in the backtracking and analyzes the different types of application of different heuristic methods.(2)Put forward the concept and method of Singleton-domain variables and weight statistic method.Combine the effective information produced in the backtracking with the existing heuristics,reasonably deal with the Singleton-domain variables and then propose the new heuristic method and the method reducing the records of the variables.We performed a number of experiments on a series of benchmark instances.The results show that the new heuristics are more efficient than classical ones especially for large data size,complex structure problems.