Research On CSP Solving Methods Based On The Number Of Instantiation

As an abstract model, Constraint Satisfaction Problem(CSP) could be used tomodeling lots of real world problems. It has been widely applied to many domains,such as scheduling, planning, network and bioinformatics. CSP has attracted more andmore attentions. CSP mainly consists of three parts: a limited set of variables, alimited set of domains associated with variables and a limited set of constraintsamong variables. Solving a constraint satisfaction problem is either finding a solutionthat could satisfy all of the constraints or proving that the problem has no solution.Finding a solution of a CSP or proving it has no solution is NP-hard. To solve CSPs,techniques of inference and intelligent search could be used. Inference could prunethe problem by using consistencies so that the problem could be solved easily.Intelligent search could guide the solving order of CSP so that the problem could besolved earlier. Currently, MAC which is the most widely used algorithm for solvingCSP is a combination of AC and backtracking search methods and has amazingversatility and effectiveness.Among the procedure of solving a CSP, variables and values need continuouslybe selected to instantiate. Experiments show that the instantiation order of variablesand values is a key factor in determining the efficiency of solving CSP. Effectivemethods can greatly improve the efficiency of constraint network. Variable orderingheuristic follows the principle of fail-first that firstly instantiates a variable that maylead to inconsistency of the network, thus avoiding redundant operations in invalidbranches. Value ordering heuristic follows the principle of success-first that firstlyinstantiates a value that may form a local solution with the instantiated set, as a resultof solving the problem as soon as possible. The key to a good heuristic is the way toobtain and use the derived information. According to the different stages of obtaining the heuristic information, the heuristics may be divided into static and dynamicheuristic methods. The dynamic heuristic method has been mainstream because itcould obtain the real time information during the solving procedure. Among popularheuristics such as dom, dom/deg, dom/ddeg and dom/wdeg, dom/wdeg is the mostefficient one for most CSPs and is still state-of-the-art that has been widely applied.This article tries to combine the heuristic information from the conflicts with theexisting heuristics on the basis of analyzing the reasons of the conflicts so that it couldbe better to guide the instantiation order of variables and values.Details are as follows:(1)By analyzing the causes of the conflicts, we find that the fail reason of variableinstantiation is due to the contradiction between the variable needed to be selected andthe set of the variables that have been instantiated. The greater the ratio of the failurenumbers and its domain size, the more possibility that this variable is inconsistentwith the instantiated variables. According to the fail-first principle, we select firstlythe variable that has the greatest radio. It’s same to the value. Accordingly, wepropose the MAC_Try algorithm that is increased the heuristic of instantiation number.Experimental results show that MAC_Try is more effective than MAC.(2)By analyzing the reasoning from last conflict, we find the cause of thetechnology is that it destroys the inconsistent set and avoids redundant operations oninvalid branches. According to the principle of fail-first, we select firstly variablewhich backtracks successfully so that we can reconstruct the inconsistent set whichhas great possibilities to backtrack. Accordingly, we propose the MAC_BTSalgorithm and experimental results show that the new algorithm has furtherimprovement than the LC algorithm.