Difference between revisions of "Brute forcing"
| Line 4: | Line 4: | ||
Given the problem "How many outfits can you create with thirteen hats and seven shoes?", a method involving brute force would be to list all 91 possibilities. | Given the problem "How many outfits can you create with thirteen hats and seven shoes?", a method involving brute force would be to list all 91 possibilities. | ||
| − | Another method of bruteforce 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_3\}</math> how can we maximize the sum of | + | Another method of bruteforce 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_3\}</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 [[Rearrangment Inequality]] for consequences of the example(and a more formal proof). | See the [[Rearrangment Inequality]] for consequences of the example(and a more formal proof). | ||
Revision as of 16:25, 18 June 2006
Brute forcing is generally accepted as the term for solving a problem in a roundabout, time-consuming, and inconvenient method.
Given the problem "How many outfits can you create with thirteen hats and seven shoes?", a method involving brute force would be to list all 91 possibilities.
Another method of bruteforce 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 Rearrangment Inequality for consequences of the example(and a more formal proof).
