Research On Optimized Strategies Of Conflict-based Heuristics

Constraint satisfaction problems (CSPs)is an important branch of artificialintelligence and with the deepening of research work, more and more problems, suchas scheduling and vehicle routing, are abstracted into CSPs for solving efficiency.Study on CSPs involving works on different areas like modeling, problem solving,programming and so on. Among all the areas constraint solving techniques based onlocal consistency algorithms has been one of the most active ones. In practice CSPsare always have exponentially sized solution space, traditional algorithms usuallyperform poorly on such problems, which may cost too much time. Development ofconstraint solving techniques greatly improves the efficiency of solving suchproblems and boost the usability of a variety of related technologies.Backtracking algorithm is one kind of general search methods which was formallystated very early, and the application of consistency algorithms during the process ofbacktrack search shows more possible ways to improve present methods. During thesearch process consistency algorithms can record some information related the statusof constraint network and to use the information more efficiently is the main aim ofdesigning different kinds of heuristics. According to the ways how the heuristics workthe heuristics can be classified into variable ordering heuristics, value orderingheuristics, adaptive branching heuristics and so on. The paper focus on a variety ofheuristics and based on the heuristic, dom/wdeg, which is recognized one of the mostefficient general heuristics, we proposed one heuristic utilizes the structure of oneclass of problems, then we analyze the the effect of one kind of special variables onthe efficiency of the heuristic dom/wdeg and give one optimization approach. Themain contributions are listed as follows(1) We give a brief introduction of present heuristics and show the way how theywork. Among all the heuristics variable ordering heuristics and value orderingheuristics are proposed early and much work has been done on them. In practice weneed to make choices among different heuristics, so based on the way they work we compare the different methods. For other kinds of heuristics like adaptive branchingheuristics and constraint propagation heuristics, for the shorter development timeworks on them are still less and we show the problems need to be resolved on them.(2)Based on the structural properties of Composed problems we proposed one newvariable ordering heuristics which is named as boundary heuristic. Different from therandomly generated problems in our research work, constraint networkscorresponding to practical problems are always have some special structural featuresand problems belong to one class are always similar on their constraint networks.Composed problems are one kind of such problems which are randomly generated.Because one Composed problem can be divided into different parts, we proposed theconcept of boundary variables with which we can take advantage of the properties ofarc consistency. Based on boundary variables we proposed boundary heuristics andexperiments show that our new methods outperform the old ones. Further we applyour methods on one kind of problems, driverLog problems, which come from realapplications and show the experiment results.(3)We redefined single valued variables during backtrack search process and basedon the properties of arc consistency algorithms we show the changes of the efficiencyof dom/wdeg which caused by single valued variables. Then we proposed an stableversion of dom/wdeg heuristic which performs well on most problems and can avoidthe effects of single valued variables.