Jump to content

Talk:Brute-force search

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

TSP is not a good example?

[edit]

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)[reply]

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)[reply]

A much better way to find prime numbers

[edit]

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)[reply]

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)[reply]

On merging Brute-force with Backtracking

[edit]

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)[reply]

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)[reply]

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)[reply]

Generate and test is not the same as brute force

[edit]

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

Merge with Linear search?

[edit]

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)[reply]

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

[edit]

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)[reply]