Systematic Search Algorithms

Most algorithms for solving CSPs search systematically through the possible assignments of values to variables. Such algorithms are guaranteed to find a solution, if one exists, or to prove that the problem is insoluble. The disadvantage of these algorithms is that they take a very long time to do so.

Generate and Test (GT)

Generate-and-test method originates from the mathematical approach to solving combinatorial problems. First, the GT algorithm guesses the solution and, then, it tests whether this solution is correct, i.e., whether the solution satisfies the original constraints. In this paradigm, each possible combination of the variable assignments is systematically generated and tested to see if it satisfies all the constraints. The first combination that satisfies all the constraints is the solution. The number of combinations considered by this method is the size of the Cartesian product of all the variable domains.
Algorithm GT:
gt(Variables,Constraints,Solution):-
    generate(Variables,Solution),
    test(Constraints,Solution).
               
generate([V::D|RemainingVariables],[V-X|PartialSolution]):-
    select_value(X,D),
    generate(RemainingVariables,PartialSolution).
generate([],[]).
               
test([C|RemainingConstraints],Solution):-
    test_constraint(C,Solution),
    test(RemainingConstraints,Solution).
test([],_).
V::D denotes variable V and its domain D
Disadvantages: The generate-and-test approach is not very efficient because it generates many wrong assignments of values to variables which are rejected in the testing phase. In addition, the generator leaves out the conflicting instantiations and it generates other assignments independently of the conflict. Visibly, one can get far better efficiency, if the validity of the constraint is tested as soon as its respective variables are instantiated. In fact, this method is used by the backtracking approach.

Backtracking (BT)

The most common algorithm for performing systematic search is backtracking. Backtracking incrementally attempts to extend a partial solution that specifies consistent values for some of the variables, toward a complete solution, by repeatedly choosing a value for another variable consistent with the values in the current partial solution.

Backtracking can be seen as a merge of generate and test phases from the GT approach. In the BT method, variables are instantiated sequentially and as soon as all the variables relevant to a constraint are instantiated, the validity of the constraint is checked. If a partial solution violates any of the constraints, backtracking is performed to the most recently instantiated variable that still has alternatives available. Clearly, whenever a partial instantiation violates a constraint, backtracking is able to eliminate a subspace from the Cartesian product of all variable domains. Consequently, backtracking is strictly better than generate-and-test, however, its running complexity for most nontrivial problems is still exponential.
Algorithm BT:
bt([V::D|RemainingVariables],Constraints,PartialSolution,Solution):-
    select_value(X,D),
    NewPartialSolution=[V-X|PartialSolution],
    test(Constraints,NewPartialSolution,RemainingConstraints),
    bt(RemainingVariables,RemainingConstraints,NewPartialSolution,Solution).
bt([],[],Solution,Solution).
               
test([C|RemainingConstraints],PartialSolution,NonTestedConstraints):-
    (can_be_tested(C,PartialSolution)
       ->  test_constraint(C,PartialSolution),NonTestedConstraints=Constraints
        ;  NonTestedConstraints=[C|Constraints]),
    test(RemainingConstraints,PartialSolution,Constraints).
test([],_,[]).
               
can_be_tested(Constraint,PartialSolution):-
    variables(Constraint,Variables),
    are_instantiated(Variables,PartialSolution).
Disadvantages: There are three major drawbacks of the standard backtracking scheme. One is thrashing, i.e., repeated failure due to the same reason. Thrashing occurs because the standard backtracking algorithm does not identify the real reason of the conflict, i.e., the conflicting variables. Therefore, search in different parts of the space keeps failing for the same reason. Thrashing can be avoided by intelligent backtracking, i.e., by a scheme on which backtracking is done directly to the variable that caused the failure.
The other drawback of backtracking is having to perform redundant work. Even if the conflicting values of variables is identified during the intelligent backtracking, they are not remembered for immediate detection of the same conflict in a subsequent computation. There is a backtracking based method that eliminates both of the above drawbacks of backtracking. This method is traditionally called dependency-directed backtracking and is used in truth maintenance systems. It should be noted that using advanced techniques adds other expenses to the algorithm that has to be balanced with the overall advantage of using them.
Finally, the basic backtracking algorithm still detects the conflict too late as it is not able to detect the conflict before the conflict really occurs, i.e., after assigning the values to the all variables of the conflicting constraint. This drawback can be avoided by applying consistency techniques to forward check the possible conflicts.

[generate & test] [backtracking]

Further reading:

Backtracking algorithms for constraint satisfaction problems; a survey
R. Dechter, D. Frost, in Constraints, International Journal, 1998.

Dynamic Backtracking
M.L. Ginsberg, in Journal of Artificial Intelligence Research 1, pages 25-46, 1993.

Iterative Broadening
M.L. Ginsberg, W.D. Harvey, In AAAI Proceedings, 1990.

Limited Discrepancy Search
W.D. Harvey and M.L. Ginsberg, in Proceedings of IJCAI95, pages 607-613, 1995.

Contents
Prev

Up
Next

Designed and maintained by Roman Barták

Guide to Constraint Programming	© Roman Barták, 1998
Contents	Prev	Up	Next