Wikipedia

Brute-force search: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Comma
→‎Combinatorial explosion: archiving Lomonosov Endgame
 
(13 intermediate revisions by 10 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)}}
{{More citations needed|date=February 2008}}
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 enumeratingchecking]] all possible candidates for thewhether solutionor and checking whethernot each candidate satisfies the problem's statement.
 
A brute-force algorithm tothat findfinds the [[divisor]]s of a [[natural number]] ''n'' would enumerate all integers from 1 to n, and check whether each of them divides ''n'' without remainder. A brute-force approach for the [[eight queens puzzle]] would examine all possible arrangements of 8 pieces on the 64-square chessboard, and, for each arrangement, check whether each (queen) piece can attack any other.<ref>{{Cite web|date=2020-01-06|title=Brute Force Algorithms Explained|url=https://www.freecodecamp.org/news/brute-force-algorithms-explained/|access-date=2021-04-11|website=freeCodeCamp.org|language=en}}</ref>
 
While a brute-force search is simple to [[Software|implement]], and will always find a solution if it exists, itsimplementation costcosts isare proportional to the number of candidate solutions{{snd}}which in many practical problems tends to grow very quickly as the size of the problem increases ([[#Combinatorial explosion|§Combinatorial explosion]]).<ref>{{cite web |title=Complexity of brute force search |url=https://www.coursera.org/learn/ml-clustering-and-retrieval/lecture/5R6q3/complexity-of-brute-force-search |website=coursera |accessdateaccess-date=14 June 2018}}</ref> Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific [[heuristic (computer science)|heuristic]]s that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than processing speed.
 
This is the case, for example, in critical applications where any errors in the [[algorithm]] would have very serious consequences; or when [[automated theorem proving|using a computer to prove a mathematical theorem]]. Brute-force search is also useful as a baseline method when [[benchmarking]] other algorithms or [[metaheuristic]]s. Indeed, brute-force search can be viewed as the simplest [[metaheuristic]]. Brute force search should not be confused with [[backtracking]], where large sets of solutions can be discarded without being explicitly enumerated (as in the textbook computer solution to the eight queens problem above). The brute-force method for finding an item in a table{{snd}}namely, check all entries of the latter, sequentially{{snd}}is called [[linear search]].
 
==Implementing the brute-force search==
Line 27 ⟶ 28:
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]]. If ''n'' is a random 64-[[binary digit|bit]] natural number, which has about 19 decimal digits on the average, the search will take about 10 years. This steep growth in the number of candidates, as the size of the data increases, occurs in all sorts of problems. For instance, if we are seeking a particular rearrangement of 10 letters, then we have 10! = 3,628,800 candidates to consider, which a typical PC can generate and test in less than one second. However, adding one more letter{{snd}}which is only a 10% increase in the data size{{snd}}will multiply the number of candidates by 11, a 1000% increase. For 20 letters, the number of candidates is 20!, which is about 2.4×10<sup>18</sup> or 2.4 [[quintillion]]; and the search will take about 10 years. This unwelcome phenomenon is commonly called the [[combinatorial explosion]], or the [[curse of dimensionality]].
 
One example of a case where combinatorial complexity leads to solvability limit is in [[solving chess]]. Chess is not a [[solved game]]. In 2005, all chess game endings with six pieces or less were solved, showing the result of each position if played perfectly. It took ten more years to complete the tablebase with one more chess piece added, thus completing a 7-piece tablebase. Adding one more piece to a chess ending (thus making an 8-piece tablebase) is considered intractable due to the added combinatorial complexity.<ref>{{cite web |title=Is there a freely available online 7 piece Endgame tablebase? |url=https://chess.stackexchange.com/questions/5253/is-there-a-freely-available-online-7-piece-endgame-tablebase |website=Stack Exchange}}</ref><ref>{{cite web |title=Lomonosov Endgame Tablebases |url=http://chessok.com/?page_id=27966 |website=ChessOK |archive-url= https://web.archive.org/web/20190406123519/http://chessok.com/?page_id=27966|archive-date=April 6, 2019}}</ref>
 
==Speeding up brute-force searches==
Line 57 ⟶ 58:
* [[Brute-force attack]]
* [[Big O notation]]
* [[Iteration#Computing]]
 
{{Algorithmic paradigms}}
 
{{DEFAULTSORT:Brute-Force Search}}
[[Category:Search algorithms]]
[[Category:Iteration in programming]]
Retrieved from "https://en.wikipedia.org/wiki/Brute-force_search"