Journal of Jilin University Science Edition

Previous Articles     Next Articles

Optimizing the Dynamic Backtracking Based on MAC

XU Cangzhu1,2, HAO Shuang1,3, LI Boyu1,2, LIU Minghui1,2   

  1. 1. Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University,[JP]Changchun 130012, China; 2. College of Computer Science and Technology, Jilin University,Changchun 130012, China; 3. College of Software, Jilin University, Changchun 130012, China
  • Received:2014-05-12 Online:2015-03-26 Published:2015-03-24
  • Contact: XU Cangzhu E-mail:bamboo5431@163.com

Abstract:

On coping with constraint satisfaction problems by means of classical dynamic backtracking based on MAC, it costs much space to store eliminating explanation, and the backtracking mechanism is too complex. Thus we optimized the classic eliminating explanation and the backtracking mechanism of the dynamic backtracking algorithm. The optimized dynamic backtracking algorithm compresses the space of recording eliminating explanation, and returns to
 the key variable that may lead to confliction via only one backtrack operation. In the worst case, the space complexity of storing eliminating explanation declines from O(n2d) to O(nd+n2). The optimized dynamic backtracking algorithm combines with restart technology for further improvement to become a complete algorithm. Experimental results show that the efficiency of the complete optimized dynamic backtracking algorithm is prior to that of standard backtracking in solving most problems.

Key words: artificial intelligence, constraint satisfaction problems, dynamic backtracking, eliminating explanation

CLC Number: 

  • TP18