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(n²d) to O(nd+n²). 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