Mark: 1 revision(s)

2008-03-08T22:35:28Z

1 revision(s)

← Older revision		Revision as of 22:35, 8 March 2008
(No difference)

Mark at 05:37, 23 July 2006

2006-07-23T05:37:11Z

New page

In computer science, '''brute-force search''' is a trivial but very general problem-solving technique, that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

For example, a brute-force algorithm to find the divisors of a natural number ''n'' is to enumerate all integers from 1 to ''n'', and check whether each of them divides ''n'' without remainder. For another example, consider the popular eight queens problem, that asks to place eight queen's on a standard chessboard so that no queen attacks any other. A brute-force algorithm for this problem is to generate all possible arrangements of eight queens on the board, and, for each arrangement, check whether there are any two queens on the same row, column, or diagonal.

Brute-force search is simple to implement, and will always find a solution if it exists. However, its cost is proportional to the number of candidate solutions, which, in many practical problems, tends to grow very quickly as the size of the problem increases. Therefore, brute-force search is typically used when the problem size is limited (as in the eight queens above), or when there are problem-specific 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 speed. This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences; or when using a computer to prove a mathematical theorem. Brute-force search is also useful as "baseline" method when benchmarking other algorithms or metaheuristics. Indeed, brute-force search can be viewed as the simplest metaheuristic.

==Implementing the brute-force search==

===Basic algorithm===
In order to apply brute-force search to a specific class of problems, one must implement four [[procedures]], ''first'', ''next'', ''valid'', and ''output''. These procedures should take as a parameter the data ''P'' for the particular instance of the problem that is to be solved, and should do the following:
# ''first'' (''P''): generate a first candidate solution for ''P''.
# ''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''): use the solution ''c'' of ''P'' as appropriate to the application

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 \gets first(P)
while c \neq Λ do
if valid(P,c) then output(P, c)
c \gets next(P,c)

For example, when looking for the divisors of an integer ''n'', the instance data ''P'' is the number ''n''. The call ''first'' (''n'') should returns the integer 1 if ''n'' <math>\geq</math> 1, or Λ otherwise; the call ''next'' (''n'',''c'') should return ''c'' + 1 if ''c'' <math><</math> ''n'', and Λ otherwise; and ''valid'' (''n'',''c'') should return '''true''' if and only if ''c'' is a divisor of ''n''. (In fact, if we choose Λ to be ''n'' + 1, the tests are unnecessary, and the algorithm simplifies considerably.)

===Common variations===
The brute-force search algorithm above will call ''output'' for every candidate that is a solution to the given instance ''P''. The algorithm is easily modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of candidates, or after spending a given amount of [[central processing unit|CPU]] time.

==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]]. 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, occur in all sorts of problems. For instance, if we are seeking a particular rearrangement of 10 letters, then we have [[factorial|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 — which is only a 10% increase in the data size — 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 [[quadrillion]]; and the search will take about 10,000 years. This unwelcome phenomenon is commonly called the [[combinatorial explosion]].

== 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, consider the popular [[eight queens problem]], which asks to place eight [[queen (chess)|queen]]s on a standard [[chessboard]] so that no queen attacks any other. If we consider only that the queens are all alike, and that no two queens can be placed on the same square, we conclude that the candidates are [[combinations|all possible ways of choosing]] of a set of 8 squares from the set all 64 squares; which means 64!/56!/8! = 4,426,165,368 candidate solutions.

However, a little more thought tells us that no arrangement with two queens on the same row or the same column can be a solution. Therefore, we can further restrict the set of candidates to those arrangements where queen 1 is on row 1, queen 2 is in row 2, and so on; all in different columns. We can describe such an arrangement by an array of eight numbers ''c''[1] through ''c''[8], each of them between 1 and 8, where ''c''[1] is the column of queen 1, ''c''[2] is the column of queen 2, and so on. Since these numbers must be all different, the number of candidates to search is the number of [[permutation]]s of the integers 1 through 8, namely 8! = 40,320 — about 1/100,000 of the original number.

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. This example also shows that the candidate enumeration procedures (''first'' and ''next'') for the restricted set may be just as simple as those of the original set, or even simpler.

In some cases, the analysis may reduce the candidates to the set of all valid solutions; that is, it may result in an algorithm that directly enumerates all the solutions (or finds one solution, as appropriate), without wasting time with tests and the generation of invalid candidates. For example, consider the problem of checking whether two words are [[anagram]]s of each other. A naive implementation of the brute-force method would generate all possible [[permutation|rearrangement]]s of the letters of the first word, and compare each one to the second word. However, that problem can be solved much more efficiently by sorting or counting the letters of each word separately, and comparing the results.

==Reordering the search space==
In applications that require only one solution, rather than all solutions, the 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. For example, when searching for a proper divisor of a random number ''n'', it is better to enumerate the candidate divisors in increasing order, from 2 to ''n'' - 1, than the other way around — because the probability that ''n'' is divisible by ''c'' is 1/''c''.

Moreover, the probability of a candidate being valid is often affected by the previous failed trials. For example, consider the problem of finding a '''1''' bit in a given 1000-bit string ''P''. In this case, the candidate solutions are the indices 1 to 1000, and a candidate ''c'' is valid if ''P''[''c''] = '''1'''. Now, suppose that the first bit of ''P'' is equally likely to be '''0''' or '''1''', but each bit thereafter is equal to the previous one with 90% probability. If the candidates are enumerated in increasing order, 1 to 1000, the number ''t'' of candidates examined before success will be about 6, on the average. On the other hand, if the candidates are enumerated in the order 1,11,21,31...991,2,12,22,32 etc., the expected value of ''t'' will be only a little more than 2.

More generally, the search space should be enumerated in such a way that the next candidate is most likely to be valid, ''given that the previous trials were not''. So if the valid solutions are likely to be "clustered" in some sense, then each new candidate should be as far as possible from the previous ones, in that same sense. The converse holds, of course, if the solutions are likely to be spread out more uniformly than expected by chance.

==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. This 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.

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]].

211L1SolutionBruteForce - Revision history

Mark: 1 revision(s)

Mark at 05:37, 23 July 2006