An enhancement scheme for constraint satisfaction problems (CSPs)

Abstract

Backtracking algorithm is extensively used in Artificial Intelligence (AI), particularly in solving Constraint Satisfaction Problems (CSPs). In recent years, a great emphasis has been made in enhancing the performance of this algorithm. The graph-based backtracking is one such enhanced scheme in which whenever a dead-end occurs, the algorithm backs up to several levels rather than going back to most recent variable among those variables that are both connected to it and from which it can continue forward. A modification of this algorithm is proposed to get further improvement of its efficiency. The modification is obtained by incorporating an advice procedure which considers the set of consistent values of the retreated variable and order these values according to the estimates of the number of possible solutions stemming from them. Thus, the additional computation at each consistency check is eliminated at the cost of less refined information about the potential cause of the dead-end and the algorithm solves the CSP with minimum or non backjumping. The advice procedure is called only when backjumping occurs.

Keywords:

• Backtracking
• Backjumping
• Analysis of Algorithms
• Graph theory

C.R.Categories:

• G 2.1 Combinational algorithms
• G2.2 Graph Theory