Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2017-10-29 01:18:11

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 392

what is Brute-force search in numerical analysis,

hi what is Brute-force search?

I study numercial analysis and I need to understand Brute-force search
and to write it on MATLAB software,

is there a book for it? or is there a website that explain it, help me please,


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#2 2017-10-29 18:52:06

alter ego
Member
Registered: 2012-03-30
Posts: 28

Re: what is Brute-force search in numerical analysis,

Say you have an equation in n, where n is a positive integer less than 10000.

A brute force method would be to try every possible value for n, and see which values work.

A

Offline

#3 2017-10-29 23:19:52

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 392

Re: what is Brute-force search in numerical analysis,

I can't understand this,
can you please give me a textbook to read or a website ..


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#4 2017-10-29 23:51:02

Jai Ganesh
Administrator
Registered: 2005-06-28
Posts: 45,954

Re: what is Brute-force search in numerical analysis,

Hi,

In computer science, brute-force search or exhaustive search, also known as generate and test, is a 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.

A brute-force algorithm to find the divisors 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.

While a brute-force search is simple to implement, and will always find a solution if it exists, 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, or when there are problem-specific heuristics 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 a baseline method when benchmarking other algorithms or metaheuristics. 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 - namely, check all entries of the latter, sequentially - is called linear search.

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 heuristics specific to the problem class. For example, in the eight queens problem the challenge is to place eight queens on a standard chessboard so that no queen attacks any other. Since each queen can be placed in any of the 64 squares, in principle there are

possibilities to consider. However, because the queens are all alike, and that no two queens can be placed on the same square, the candidates are all possible ways of choosing of a set of 8 squares from the set all 64 squares; which means 64 choose 8 = 64!/56!/8! = 4,426,165,368 candidate solutions - about 1/60,000 of the previous estimate. Further, 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.

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.

In some cases, the analysis may reduce the candidates to the set of all valid solutions; that is, it may yield an algorithm that directly enumerates all the desired solutions (or finds one solution, as appropriate), without wasting time with tests and the generation of invalid candidates. For example, for the problem "find all integers between 1 and 1,000,000 that are evenly divisible by 417" a naive brute-force solution would generate all integers in the range, testing each of them for divisibility. However, that problem can be solved much more efficiently by starting with 417 and repeatedly adding 417 until the number exceeds 1,000,000 - which takes only 2398 (= 1,000,000 ÷ 417) steps, and no tests.

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. Heuristics 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 Problems, 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 static evaluation function.


It appears to me that if one wants to make progress in mathematics, one should study the masters and not the pupils. - Niels Henrik Abel.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.

Offline

#5 2017-10-30 20:33:53

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: what is Brute-force search in numerical analysis,

Hannibal lecter wrote:

I can't understand this,
can you please give me a textbook to read or a website ..

Imagine that you were given an equation like
, and you wanted to find the positive integer solutions. One way would be to try every possible combination of a and b until you got the required answer of 1000000. This is an example of a brute force search.

Offline

#6 2017-11-07 09:07:28

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 392

Re: what is Brute-force search in numerical analysis,

can you give me a simple question equation with it's answer, maybe I will understand ..
because I read a lot about it but all what I read is different from this

for example f(x) = cos(x)-x
how to apply brute-search for this equation?


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#7 2017-11-07 19:37:36

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: what is Brute-force search in numerical analysis,

hi Hannibal lecter

Both cos(x) and x have continuous* graphs so cos(x) - x would too.  You haven't said what value you want to achieve so I'll assume you want to solve cos(x) - x = 0

You could try a value of x and see what the function evaluates to.  Then try a close by value of x.  Do you get closer to zero or further away.  Depending on the answer to that, continue trying values for x so you 'home in' on a solution.  This is usually called trial and improvement but it is certainly also brute force because you are just trying lots and lots of values.

Because cos is a periodic function I thought there might be more than one solution but there isn't.  It is close to 0.739...  But you'll not get an exact solution for this one so you'd have to decide on the accuracy level you want.

Bob 

If a function isn't continuous you might not be able to 'home in' like this.


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#8 2017-11-08 10:15:13

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 392

Re: what is Brute-force search in numerical analysis,

is all functions easy to solve like that one? or there is a difficulties with other types ,
please give me a textbook to read it
I search a lot I didn't find ,


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#9 2017-11-08 19:52:23

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: what is Brute-force search in numerical analysis,

hi Hannibal lecter

I don't know of a book just on this.  I expect the book's title (if it exists) would be on a more general topic with, perhaps, a chapter on this.  But I used 'google' to search for "brute force search" and got loads of useful hits, I suggest you try the same.

This link http://intelligence.worldofcomputing.ne … gQJpeSDPIV looks particularly detailed.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#10 2017-11-09 08:21:56

Hannibal lecter
Member
Registered: 2016-02-11
Posts: 392

Re: what is Brute-force search in numerical analysis,

thank you,

but how to write this on MATLAB software?


Wisdom is a tree which grows in the heart and fruits on the tongue

Offline

#11 2017-11-10 06:58:22

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: what is Brute-force search in numerical analysis,

I am not familiar with MATLAB but a quick google search gave me this:

http://hplgit.github.io/prog4comp/doc/p … ab025.html

Obviously, exact code will depend on what you're trying to solve.

B


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

Board footer

Powered by FluxBB