Content deleted Content added
No edit summary |
→Combinatorial explosion: archiving Lomonosov Endgame |
||
(31 intermediate revisions by 28 users not shown) | |||
Line 1:
{{Short description|Problem-solving technique and algorithmic paradigm}}
{{about|the problem-solving technique in computer science|similarly named methods in other disciplines|Brute force (disambiguation)}}
{{
In [[computer science]], '''brute-force search''' or '''exhaustive search''', also known as '''generate and test''', is a very general [[problem-solving]] technique and [[algorithmic paradigm]] that consists of [[Iteration#Computing|systematically
A brute-force algorithm
While a brute-force search is simple to [[Software|implement]]
This is the case, for example, in critical applications where any errors in the [[algorithm]] would have very serious consequences
==Implementing the brute-force search==
===Basic algorithm===
▲# ''next'' (''P'', ''c''): generate the next candidate for ''P'' after the current one ''c''.
# ''valid'' (''P'', ''c''): check whether candidate ''c'' is a solution for ''P''.
# ''output'' (''P'', ''c''):
The ''next'' procedure must also tell when there are no more candidates for the instance ''P'', after the current one ''c''. A convenient way to do that is to return a "null candidate", some conventional data value Λ that is distinct from any real candidate. Likewise the ''first'' procedure should return Λ if there are no candidates at all for the instance ''P''. The brute-force method is then expressed by the algorithm
''c''
'''while''' ''c''
'''if''' ''valid''(''P'',''c'') '''then'''
''output''(''P'', ''c'') ''c''
'''end while'''
For example, when looking for the divisors of an integer ''n'',
==Combinatorial explosion==
The main disadvantage of the brute-force method is that, for many real-world problems, the number of natural candidates is prohibitively large. For instance, if we look for the divisors of a number as described above, the number of candidates tested will be the given number ''n''. So if ''n'' has sixteen decimal digits, say, the search will require executing at least 10<sup>15</sup> computer instructions, which will take several days on a typical [[personal computer|PC]].
One example of a case where combinatorial complexity leads to solvability limit is in [[
==Speeding up brute-force searches==
One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using [[heuristic]]s specific to the problem class. For example, in the [[eight queens puzzle|eight queens problem]] the challenge is to place eight queens on a standard [[chessboard]] so that no queen attacks any other.
As this example shows, a little bit of analysis will often lead to dramatic reductions in the number of candidate solutions, and may turn an intractable problem into a trivial one.
Line 38:
==Reordering the search space==
In applications that require only one solution, rather than all solutions, the [[expected value|expected]] running time of a brute force search will often depend on the order in which the candidates are tested. As a general rule, one should test the most promising candidates first.
==Alternatives to brute-force search==
There are many other search methods, or metaheuristics, which are designed to take advantage of various kinds of partial knowledge one may have about the solution. [[Heuristic]]s can also be used to make an early cutoff of parts of the search. One example of this is the [[minimax]] principle for searching game trees, that eliminates many subtrees at an early stage in the search. In certain fields, such as language parsing, techniques such as [[chart parsing]] can exploit constraints in the problem to reduce an exponential complexity problem into a polynomial complexity problem. In many cases, such as in [[Constraint Satisfaction Problem]]s, one can dramatically reduce the search space by means of [[Constraint propagation]], that is efficiently implemented in [[Constraint programming]] languages. The search space for problems can also be reduced by replacing the full problem with a simplified version. For example, in [[computer chess]], rather than computing the full [[minimax]] tree of all possible moves for the remainder of the game, a more limited tree of minimax possibilities is computed, with the tree being pruned at a certain number of moves, and the remainder of the tree being approximated by a [[evaluation function|static evaluation function]].
==In cryptography==
{{main|Brute-force attack}}
In [[cryptography]], a ''brute-force attack'' involves systematically checking all possible [[key (cryptography)|keys]] until the correct key is found.<ref>Mark Burnett, [http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php "Blocking Brute Force Attacks"] {{Webarchive|url=https://web.archive.org/web/20161203020306/http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php |date=2016-12-03 }}, ''UVA Computer Science'', 2007</ref> This [[strategy]] can in theory be used against any encrypted data<ref>{{cite book|url=http://www.crypto-textbook.com|page=7|title=Understanding Cryptography: A Textbook for Students and Practitioners|author1=Christof Paar |author2=Jan Pelzl |author3=Bart Preneel |publisher=Springer|year=2010|isbn=3-642-04100-0}}</ref> (except a [[one-time pad]]) by an attacker who is unable to take advantage of any weakness in an encryption system that would otherwise make his or her task easier.
The [[key length]] used in the encryption determines the practical feasibility of performing a brute force attack, with longer keys exponentially more difficult to crack than shorter ones.
==References==
Line 54:
==See also==
* [[Sudoku solving algorithms#Sudoku brute force|A brute-force algorithm to solve Sudoku puzzles.]]
* [[Brute-force attack]]
* [[Big O notation]]
* [[Iteration#Computing]]
{{Algorithmic paradigms}}
{{DEFAULTSORT:Brute-Force Search}}
[[Category:Search algorithms]]
[[Category:Iteration in programming]]
|