30-06-2012, 12:00 PM
Brute Force
brute force.ppt (Size: 4.02 MB / Downloads: 266)
A straightforward approach, usually based directly on the problem’s statement and definitions of the concepts involved
Examples:
Computing an (a > 0, n a nonnegative integer)
Computing n!
Multiplying two matrices
Brute-Force Sorting Algorithm
Selection Sort Scan the array to find its smallest element and swap it with the first element. Then, starting with the second element, scan the elements to the right of it to find the smallest among them and swap it with the second elements. Generally, on pass i (0 i n-2), find the smallest element in A[i..n-1] and swap it with A[i]:
Brute-Force String Matching
pattern: a string of m characters to search for
text: a (longer) string of n characters to search in
problem: find a substring in the text that matches the pattern
Brute-force algorithm
Step 1 Align pattern at beginning of text
Step 2 Moving from left to right, compare each character of pattern to the corresponding character in text until
all characters are found to match (successful search); or
a mismatch is detected
Step 3 While pattern is not found and the text is not yet exhausted, realign pattern one position to the right and repeat Step 2
Exhaustive Search
A brute force solution to a problem involving search for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set.
Method:
generate a list of all potential solutions to the problem in a systematic manner (see algorithms in Sec. 5.4)
evaluate potential solutions one by one, disqualifying infeasible ones and, for an optimization problem, keeping track of the best one found so far
when search ends, announce the solution(s) found