ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (5): 1091-1097.doi: 10.7544/issn1000-1239.2015.20131588

Previous Articles     Next Articles

Constraint Solving Based on the Number of Instantiation

Li Zhanshan, Zhang Qian, Zhang Liang   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
  • Online:2015-05-01

Abstract: Heuristics is an important topic in the domain of constraint satisfaction problems. Effective heuristics can improve the efficiency of the search algorithms quite a lot. As a result, lots of heuristics to solve the constraint satisfaction problems are presented. Heuristics are divided into many types depending on the acquisition and application of heuristic information, and the main heuristics include variable ordering heuristics and value ordering heuristics. When solving the constraint satisfaction problems, we find that the failed numbers of instantiating a variable reflect the conflict between this variable and the instantiated set, and that the successful numbers of assigning a value reflect the possibility for this value of composing a local solution with the instantiated set. Both numbers have a great influence upon the efficiency of solving constraint satisfaction problems. Based on the above research conclusions, this paper proposes a method of counting the weight number of instantiation and a heuristic of instantiation number combined with the existing mainstream heuristics, and then presents a new corresponding constraint solving algorithm called MAC_Try. We prove that the worst-case time complexity is O(ned3) on a branch. A large number of experimental results show that our proposed algorithm MAC_Try is more effective than the popular constraint solving method MAC3rm.

Key words: artificial intelligence, constraint satisfaction problem(CSP), heuristic, failed number of variable instantiation, successful number of value assigning

CLC Number: