what exactly is the brute force algorithm? (besides just the approach only)
when a problem can use brute-force approach, and when not to?
What characteristics are there in an algorithm, when the algorithm uses brute force approach?
1 Answer
1 and 3 : Brute force means that you will go through all possible solutions extensively. For example, in a chess game, if you know you can win in two moves, the brute force will go through all possible combination of moves, without taking anything in consideration. So the little pawn in the back that cannot influence the outcome will still be considered.
2 : As you consider everything, the problem quickly goes out of control. Brute force through 15 moves in chess is impossible because of combinatorial explosion (too many situations to consider). However, more clever algorithms that take into account "knowledge about the problem" can go much further (20-30 moves ahead)
Edit : To clarify, brute force is simplest (dumbest?) way to explore the space of solutions. If you have a problem is set in a countable space (chess moves are countable, passwords are countable, continuous stuff is uncountable) brute force will explore this space considering all solutions equally. In the chess example, you want to checkmate your opponent. This is done via a sequence of moves, which is countable. Brute force will go through all sequence of moves, however unlikely they may be. The word unlikely is important, because it means that if you have knowledge about your problem (you know what is unlikely to be the solution, like sacrificing your queen), you can do much better than brute force.
-
so that because of combinatorial explosion means brute-force can not be used in many problems? Nov 12, 2011 at 8:32
-
1This is generally correct. The rule of thumb to know if it's possible to use brute force is to consider two things, the branching factor, and the depth at which you guess the solution is. Compute (branching factor) ^ (depth) and that's the number of situation brute force will consider. Most computers will not be able to consider 10^12 situations. Nov 12, 2011 at 11:44
-
1Dynamic Programming can sometimes help with exponentially complex problems. Nov 12, 2011 at 14:05
-
1@Alex : Of course, DP is really nice! But so are a lot of other classes of algorithms. Basically, everything is nice when compared to brute force ;-) Nov 12, 2011 at 16:47
Brute force may refer to any of several problem-solving methods involving the evaluation of multiple (or every) possible answer(s) for fitness
. There are no standard 'brute force algorithms' because each problem is different. If you wanted to guess a password, brute force is literally generating every single possible password until you find the right one. If you wanted to guess a person's age, you could brute force by just starting from 1 and increasing by 1 every time, etc.