Differences between backtracking and brute-force search

Question

I'm currently taking a course in algorithms, and I'm having some difficulty understanding the exact definitions of brute-force search and backtracking. As I understand it, the following is true:

• Brute-force search (BFS) is a type of algorithm which computes every possible solution to a problem and then selects one that fulfills the requirements.
• Explicit constraints give the possible values for each choice (e.g., choices 1-3 are limited to {1, 2}, choice 4 is limited to {3, 4, 5}, etc.), which determines how the search's "execution tree" is shaped.
• Implicit constraints relate the different choices to each other (e.g., choice 2 must be greater than choice 1, etc.), which is used in BFS to remove potential solutions.
• Backtracking is an extension to BFS in which the implicit constraints are evaluated after every choice (as opposed to after all solutions have been generated), which means that potential solutions can be discarded before they have been 'finished'.

Basically, all I'm wondering is whether this is accurate or not, and, if it isn't, I'd really appreciate some clarification. Thanks in advance.

Answer 1

Short answer: If I read the question correctly, you are correct.

Well like you say explicit constraints are constraints on the domain of each variable so x_i∈S_i. Note that S_i does not have to be stated as a collection. You could for instance state that S₀ is the set of all prime numbers less than 25.

Implicit constraints on the other hand, are predicates that are defined over two or more variables P(x₁,x₂,...,x_n). For instance x₂<x₃. But it can also be defined over more variables (for example three).

Brute force search only takes the explicit constraints into account: it assigns all possible values from S_i to a variable x_i and this for all variables. After it has constructed such a configuration, it verifies that all implicit constraints are satisfied.

Backtracking on the other hand aims to optimize this process. From the moment that all variables over which an implicit constraint is defined are assigned, it verifies that constraint. If the constraint fails, then it immediately assigns a different value to one of the variables. The advantage is that if for instance brute force has assigned 2 to x₁=2 and 5 to x₂=5, and the implicit constraint x₁ > x₂ fails, then it will not assign values to x₃,x₄,... only to find out that for all configurations for these values it fail.

Of course there is some bookkeeping involved in backtracking: you need to find out which constraints "fire" when a certain value is set. But for a lot of constraint programming problems (like for instance SAT), there exists efficient algorithms to do that (with watched literals, etc.). Furthermore constraint programming libraries like Gecode also have advanced queuing mechanisms such that fast constraints are evaluated first, etc.