Differences Between Backtracking and Brute Force Search
I am currently taking a course on algorithms and am having difficulty understanding the exact definitions of brute force search and backtracking. As far as I understand, the following is true:
- Brute force search (BFS) is a type of algorithm that calculates all possible solutions to a problem and then selects the one that meets the requirements.
- Explicit constraints provide possible values for each choice (eg, choices 1-3 are limited
{1, 2}
, choices 4 are limited,{3, 4, 5}
and so on) that determines how the search tree is formed. - Implicit constraints refer to different choices to each other (for example, choice 2 must be greater than choice 1, and so on) that BFS uses to remove potential solutions.
- Backtracking is an extension to BFS in which implicit constraints are evaluated after each selection (as opposed to after all solutions have been created), which means that potential solutions can be discarded before they are "finished".
Basically, all I'm interested in is how accurate it is or not, and if it isn't, I'd really appreciate some clarification. Thanks in advance.
source to share
Short answer . If I read the question correctly , you are correct .
Ok, as you say, explicit constraints are constraints on the scope of each variable, so x i& in; S i... Note that S idoes not need to be specified as a collection. You can, for example, indicate that S 0 is the set of all primes less than 25.
Implicit constraints , on the other hand, are predicates that are defined over two or more variables P (x 1, x 2..., x <sub> psub>). For example x 2 <x 3... But it can also be defined for more variables (for example, three).
The brute force search only considers explicit constraints: it assigns all possible values from S i variable x iand this is for all variables. After building such a configuration, it checks that all implicit constraints are met.
Bactracking , on the other hand, aims to streamline this process. From the moment when all the variables on which the implicit constraint is set are assigned, it checks this constraint. If the constraint fails, then it immediately assigns the value of the variable to one of the variables. The advantage is that if, for example, brute force assigned 2 x 1= 2 and 5 to x 2= 5, and the implicit constraint x 1 > x 2then it will not assign values to x 3, x 4, ... just to find out that for all the configurations for these values don't work.
Of course, there are several accounts in the backtrace: you need to figure out what the "fire" limits are when given a certain value. But for many constraint programming problems (like SAT) there are efficient algorithms for doing this (with scanned literals, etc.). In addition, constraint programming libraries such as Gecode also have advanced queuing mechanisms so that fast constraints are executed first, etc.
source to share