The Research Of The Dom/wdeg Heuristic And DBT Of Solving CSP

Constraint Satisfaction Problem is a important part of the artificial intelligence. Itcan abstract kinds of practical problems such as scheduling, configuration andbioinformatics, to the model consisted of variables, domains and constraints. Then itfigure out a result satisfied all the constraint conditions. It fulfills a solving way thattransform practical problem to abstract symbols problem, and handle it.Constraint Satisfaction Problem is usually solved by Backtracking Algorithms. Italways contains consistency technology, heuristic and backtracking mechanism.Consistency technology is the central technology of solving Constraint SatisfactionProblem for now, it can reduce the scale of the problem by checking the consistencyof the problem. Heuristic is a effective way of improving the efficiency of solvingproblem, it mainly depends on deciding the order of the instantiation of the variablesand the values of the assignments of the variables. Backtracking mechanism ensuresthe solving algorithm is complete, it supplies the way how to handle the conflictionduring the solving process.This paper mainly contains: firstly, study about the background of the ConstraintSatisfaction Problem such as consistency technologies, solving algorithms andheuristics; secondly, base on the research, partly complete the dynamicheuristic—dom/wdeg in MAC algorithm, and improve the dynamic backtrackingalgorithm—DBT. The specific work as follows:(1) By studying the solving process of the dom/wdeg heuristic in MAC algorithm,and compare the different efficiency by choosing from the variables which has thesame ratio of the dom/wdeg, and consider that the more earlier instantiation variableshould be picked more strickly. Therefore, when begin to solving problem and beforeencounter the confliction, choose and apply a suitable static heuristic to pick theinstantiation variable according to the structure of the problem(this paper gives ageneral static heuristic, which chooses by the rate of the global support of the value invariable domain), then start to use dom/wdeg heuristic after encounter the confliction.The improved heuristic called separation heuristic. In this way, it avoids lots ofvariables are the same ratio of dom/wdeg when problem initializing, which leads tounable to pick a variable while using dom/wdeg heuristic. Meanwhile, it also aspossible as it can ensures the stability of the first few instantiation variables.(2) By studying the classic dynamic backtracking algorithms, improve the classiceliminating explanation and the backtracking mechanism of the dynamic backtracking algorithm, which makes only use one step of backtracking operation to back to thekey variable that may most possible to lead to the confliction. At worst, timecomplexity of the domain recovery declines from O(nd) to O(1), and the spacecomplexity of storing eliminating explanation declines from O(n2d) to O(nd), where nrepresents the number of the variables in problem and d represents the number of thevalues in maximum domain. However, as the improved dynamic backtrackingalgorithm is incomplete, hence combine it with restart technology for furtherimprovement to become a complete algorithm.