Talk:Brute-force search

TSP is not a good example?

The traveling salesman problem is the classic example of this type of problem.

I don't like this example - the previous three show a problem which grows exponentially, while the TSP is one which grows factorially.

On the other hand, I don't know an alternative. Perhaps the wording could be changed to stop suggesting TSP is an exponential problem? r3m0t 23:11, 11 Mar 2004 (UTC)

D'oh, the time needed to solve TSP does grow exponentially. Remember that n! ~ sqrt(2*pi*n) * (n/e)^n Azotlichid 00:11, 25 February 2007 (UTC)

Moreover, the brute force method is not necessarily restricted to exponential-size search space only. One can use it with polynomial problems too, e.g. to find the fraction m/n with three-digit integers m and n that is nearest to π. The brute-force solution is enumerate all 999×999 possibilities. There are better methods, fortunately. --Jorge Stolfi (talk) 23:04, 21 December 2009 (UTC)

A much better way to find prime numbers

Just iterate up to the floor of the square root of the number n, and for every number m that fits also record n/m... INVERTED 11:38, 9 June 2006 (UTC)

It doesn't say it's efficient, does it? Brute-force search is usually not the most efficient way to do something, but it's simple. --Spoon! 11:00, 31 August 2006 (UTC)

On merging Brute-force with Backtracking

I strongly oppose to the merging. Backtracking is a method that can be used to perform a brute force search. Brute force search can be performed in other ways, the most common being a simple loop through the solution space. On the other hand, backtracking can be used in ways that are not brute-force, by using some specific method, a backtracking algorithm ca determine that a given branch of the search space cannot contain a solution, without examining all the space.Gfonsecabr 17:52, 4 February 2007 (UTC)

It is false. Backtracking is mostly the same as brute force except the cases you mentioned above and can be used interchangeably. Both articles contain mostly the same content.71.175.43.242 20:48, 28 February 2007 (UTC)

I hope it is clear now that "brute force" is very different from "backtracking". Brute force is the simplest and stupidest method that generates and tests *all* candidates. Bactracking is more intelligent in that it increases the candidate one step at a time and backtracks as soon as the step leads nowhere. Thus backtracking may be much faster than brute-force (or maynot be, depending on the problem). --Jorge Stolfi (talk) 22:58, 21 December 2009 (UTC)

Generate and test is not the same as brute force

A genetic algorithm is a kind of generate and test algorithm but is not brute force Housecarl (talk) 20:27, 13 August 2008 (UTC)

Merge with Linear search?

This article subject looks awfully like another article linear search, although the latter is much better explained. Suggest merging unless anyone can think of a reason not to?

The two aree similar in a very abstrat sense, but in practice are different topics. Linear search is specifically about searching items in a table. Brute force search is used when searching a large set that is not stored but generated on the fly; it is meant to contrast with other combinatorial optimization methods, such as backtracking, branch-and-bound, etc.. I will try to clarify this point in the article. --Jorge Stolfi (talk) 22:54, 21 December 2009 (UTC)

You can't brute-force a one-time pad

You can't brute-force a one-time pad encrypted cypher text. The best you can do is generate all possible clear texts of the same length. I added a parenthetical note to that effect, but if someone with better writing ability than me wants to tidy it up, feel free. 87.157.198.158 (talk) 21:51, 24 June 2013 (UTC)