Difference between revisions of "Brute forcing"
m (Rephrasing what brute force is) |
|||
| (8 intermediate revisions by 7 users not shown) | |||
| Line 1: | Line 1: | ||
| − | Brute forcing is | + | Brute forcing is the method of completing a problem in the most straightforward way possible, through bashing calculations, and can actually sometimes be faster than a more creative approach, and is thus an important tool to have. |
| + | Given the problem "How many outfits can you create with thirteen hats and seven pairs of shoes?", a method involving brute force would be to list all 91 possibilities (although this would not be a smart time to use brute force). | ||
| − | + | Another method of brute force is the [[Greedy Algorithm]]. As an example, given two sets <math>\{{a}_1,{a}_2,\ldots,{a}_n\}</math> and <math>\{b_1,b_2,\ldots,b_n\}</math> how can we maximize the sum of <math>\sum_{i,j \in n} a_ib_j</math>? We sort the sets such that they are in increasing or decreasing order; then, the maximal sum is <math>a_1b_1 + a_2b_2 + a_3b_3 + \ldots a_nb_n</math>. The "greedy" part is when we maximize the sum each step by taking the largest possible term to add. | |
| − | + | See the [[Rearrangement Inequality]] for consequences of the example (and a more formal proof). | |
| − | See | + | == See also == |
| + | * [[Casework]] | ||
Latest revision as of 13:22, 5 May 2023
Brute forcing is the method of completing a problem in the most straightforward way possible, through bashing calculations, and can actually sometimes be faster than a more creative approach, and is thus an important tool to have.
Given the problem "How many outfits can you create with thirteen hats and seven pairs of shoes?", a method involving brute force would be to list all 91 possibilities (although this would not be a smart time to use brute force).
Another method of brute force is the Greedy Algorithm. As an example, given two sets 
and 
how can we maximize the sum of 
? We sort the sets such that they are in increasing or decreasing order; then, the maximal sum is 
. The "greedy" part is when we maximize the sum each step by taking the largest possible term to add.
See the Rearrangement Inequality for consequences of the example (and a more formal proof).
