The Research Of Constraint Satisfaction Problems Based On Heuristic

Constraint satisfaction problem is an important study direction of artificial intelligence. Its study achievements have extensive applications in symbolic analogy, system diagnosis, resource schedulers and production configuration. To solve it better, we lead arc consistency to constraint satisfaction problems, and use arc consistency in the BT frame. That is the actual CSP solving algorithm MAC. Heuristics play a very important role in the solving progress of the CSPs. Usual heuristics include variable heuristics and value heuristics. Applying the heuristic to the CSPs could improve the efficiency. Now most of the studies are about the variable heuristics and static value heuristics, not the dynamic value heuristics. So we put emphasis on studying the effect of the dynamic value heuristics. The primary work of this thesis is to study and improve the CSPs based on heuristics. It is divided into 2 parts as follows:To increase the efficiency of solving constraint satisfaction problems, an algorithm of solving constraint satisfaction problems based on dynamic value ordering called BT-DVH was proposed. In the progress of the solving the problems, this algorithm absorbs the advantages of the previous heuristics, and makes use of the information made by preprocess and consistency checking. To achieve dynamic value ordering heuristic, variable ordering is used, and the priorities of the values to instantiate the variables are analysed dynamically. The efficiencies of the static and dynamic value ordering heuristics were compared, and the merits and drawbacks of the BT-DVH were analyzed. BT-DVH's time complexity and Space Complexity are analyzed, and the Correctness is demonstrated. Tested by random problems and benchmark, the result shows that BT-DVH based on dynamic value ordering has a higher efficiency than classic mainstream algorithm BT+MAC.By the way of studying the arc consistency algorithm. AC-4, we present dynamic value ordering heuristic algorithm MAC-DMSV for solving constraint satisfaction problems based on AC-4. This algorithm uses the counter's information created in the initialization of the AC-4. and chooses the value whose counter is the biggest. Then adding this value ordering heuristic to MAC. we can update the values of the counters when consistency checking, so we realize dynamic value ordering heuristic. After demonstrate the correctness of the algorithm, we analyze its time complexity and space complexity. Tested by random problems and benchmark, the result shows that MAC-DMSV has a higher efficiency than MAC and BT+MPAC...