MODIFIED BACKJUMPING ALGORITHMS FOR SOLVING CONSTRAINT SATISFACTION PROBLEMS

摘要

The backtracking algorithm is a prominent search technique in AI, particularly due to its use in Constraints Satisfaction Problems (CSPs), Truth maintenance Systems (TMS), and PROLOG. In the context of CSPs, Dehter~5 and Gashning~10 proposed two variants of the backtracking algorithm known as backjumping algorithms. One is graph-based and the other is failure-based backjumping algorithm. These algorithms attempt to backjump to the source of failure in case of a dead-end situation. This improves the backtracking performance. However, these algorithms are not consistent in the selection of the variable to backjump. In the paper, the modifications of both types of backjumping algorithms are proposed. Theses algorithms adopt a technique to select the variable to backjump in a consistent manner. This further increases the search efficiency in them. The merits of these modified algorithms are investigated theoretically. Experimental results on the zebra problem and random problems show that the modified algorithms give better results on most occasions.