47
  1. what exactly is the brute force algorithm? (besides just the approach only)

  2. when a problem can use brute-force approach, and when not to?

  3. What characteristics are there in an algorithm, when the algorithm uses brute force approach?

5
  • From wikipedia: 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.
    – wkl
    Nov 12, 2011 at 6:53
  • example : "If we wanted to guess a person's age, we could brute force by just starting from 1 and increasing by 1 every time, etc" by adding 1 if not found the solution, whether it is a brute-force measures?
    – nehemkris
    Nov 12, 2011 at 7:42
  • It's brute force because you'd eventually reach the person's age, but you didn't do anything but try every possibility until one worked. An algorithm is not brute force if it exploits some advantage or approaches a problem such that you could arrive at a solution without having to try every possibility, ever. For example if a person was an adult, and you knew he was born in the 1970s, your 'guessing' algorithm would limit you to only 10 or so age possibilities, because you have some knowledge you can exploit to limit how many solutions you have to try.
    – wkl
    Nov 12, 2011 at 7:48
  • so, whether it can be concluded if brute-force algorithm is as a human reasoning?
    – nehemkris
    Nov 12, 2011 at 8:29
  • 2
    You can determine if it's brute force, if the approach would eventually hit every possible solution to a problem given any arbitrary situation.
    – wkl
    Nov 12, 2011 at 8:35

1 Answer 1

53

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.

4
  • so that because of combinatorial explosion means brute-force can not be used in many problems?
    – nehemkris
    Nov 12, 2011 at 8:32
  • 1
    This 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
  • 1
    Dynamic 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.