Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Differences between backtracking and brute-force search

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 eachother (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.

like image 752
AptenodytesForsteri Avatar asked May 22 '17 18:05

AptenodytesForsteri


People also ask

What are the advantages of backtracking as against brute force algorithms?

Pros. Backtracking can almost solve any problems, due to its brute-force nature. Can be used to find all the existing solutions if there exists for any problem. It is a step-by-step representation of a solution to a given problem, which is very easy to understand.

What is the difference between backtracking and recursion?

Difference between Recursion and Backtracking: In recursion, the function calls itself until it reaches a base case. In backtracking, we use recursion to explore all the possibilities until we get the best result for the problem.

What is difference between backtracking and branch and bound method?

Branch-and-Bound is used for solving Optimisation Problem. In backtracking, the state space tree is searched until the solution is obtained. In Branch-and-Bound as the optimum solution may be present any where in the state space tree, so the tree need to be searched completely. Backtracking is more efficient.

What is difference between backtracking and dynamic programming?

What are the differences between dynamic programming and backtracking? Dynamic programming emphasizes on overlapping subproblems, while backtracking focus on all or some solutions. Dynamic programming relies on the principle of optimality, while backtracking uses a brute force approach.


1 Answers

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 xi∈Si. Note that Si does not have to be stated as a collection. You could for instance state that S0 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(x1,x2,...,xn). For instance x2<x3. 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 Si to a variable xi 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 x1=2 and 5 to x2=5, and the implicit constraint x1 > x2 fails, then it will not assign values to x3,x4,... 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.

like image 111
Willem Van Onsem Avatar answered Oct 27 '22 08:10

Willem Van Onsem