COSC 3100 Brute Force and Exhaustive Search: Instructor: Tanvir
COSC 3100 Brute Force and Exhaustive Search: Instructor: Tanvir
COSC 3100 Brute Force and Exhaustive Search: Instructor: Tanvir
Instructor: Tanvir
In RSA (Ron Rivest, Adi Shamir, and Leonard Adleman) encryption algorithm we need to compute an mod m for a > 1 and large n. First response: Multiply 1 by a n times which is the Brute Force approach.
3
It is the only general approach that always works Seldom gives efficient solution, but one can easily improve the brute force version. Usually can solve small sized instances of a problem
A yardstick to compare with more efficient ones
4
34 17 34 89 34 89 68 89
17 29 34 45 68 | 90 89 89 | 90
C(n) = = =
Sequential Search
ALGORITHM SequentialSearch(A[0..n-1], K)
//Output: index of the first element in A, whose //value is equal to K or -1 if no such element is found i <- 0 while i < n and A[i] K do Input size: n i <- i+1 Basic op: <, if i < n Cworst(n) = 2n+2 return i else return -1 Now we have brute-force, can you improve it?
10
If you knew A to be sorted in nondecreasing order, could you improve the search?
11
text
We shall learn more sophisticated and efficient ones in space-time trade-off chapter!
13
Closest-Pair by Brute-force
Find the two closest points in a set of n points Points can be airplanes (most probable collision candidates), database records, DNA sequences, etc. Cluster analysis: pick two points, if they are close enough they are in the same cluster, pick another point, and so on
14
Closest-Pair by Brute-force
For simplicity we consider 2-D case Euclidean distance, d(pi, pj) =
Brute-force: compute distance between each pair of disjoint points and find a pair with the smallest distance d(pi, pj) = d(pj, pi), so we consider only d(pi, pj) for i < j
15
))
Get rid of
16
17
Convex-hull (contd.)
DEFINITION: A set of points in the plane is called convex if for any two points p and q in the set, the entire line segment with the endpoints at p and q belongs to the set.
convex
Not convex
18
Convex-hull (contd.)
DEFINITION: The convex hull of a set S of points is the smallest convex set containing S.
The smallest requirement means that the convex hull of S must be a subset of any convex set containing S.
19
Convex-hull (contd.)
THEOREM: The convex hull of any set S of n > 2 points not all on the same line is a convex polygon with the vertices at some of the points of S. Vertices of the polygon are called extreme points. We need to know which pairs of points need to be connected.
20
pi
pj
ax+by=c
21
22
Exhaustive Search
Traveling Salesman Problem (TSP)
Find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started Can be conveniently modeled by a weighted graph; vertices are cities and edge weights are distances Same as finding Hamiltonian Circuit: find a cycle that passes through all vertices exactly once
23
24
b 3
permutations
optimal
optimal
(2n)
27
subset
weight
value $0
7
3 4 5 10 11 12 7 8 9 14 15 16 12 19
$42
$12 $40 $25 $54 !feasible !feasible $52 $37 $65 !feasible !feasible !feasible !feasible !feasible
28
knapsack
Item 3
W=50
w1 = 30 v1 = $120 Item 1
w2 = 20 v2 = $100 Item 2
w3 = 10 v3 = $60 Item 3
knapsack
{Item3, Item2} = $60+$100 = $160 {Item3, Item1} = $60+$120 = $180 {Item2, Item1} = $100+$120 = $220
Exhaustive Search
A brute force approach to combinatorial problems (which require generation of permutations, or subsets) Generate every element of problem domain Select feasible ones (the ones that satisfy constraints) Find the desired one (the one that optimizes some objective function)
30
31
32
Person 2 Person 3
Person 4
6 5
7
4 8
6
3 1
9
7 8
4
Cost matrix
Select one element in each row so that all selected elements are in different columns and total sum of the selected elements is the smallest.
<j1, j2, , jn> are feasible solution tuples i-th component indicates the column of the element selected in i-th row e.g., <2, 3, 4, 1> Generate all permutations of <1, 2, 3, 4> And compute total cost, find the smallest cost.
33
Complexity is (n!)
And so on
34
35
Graph Traversals
Problem domain can be a graph Exhaustive search needs to visit each vertex and do something at it Two important graph-traversal algorithms: depth-first search, breadth first search
36
Depth-first search
Start at a vertex, mark it as visited Go to one of unvisited neighbors, mark it visited, and so on. At dead end, backs up one edge to the vertex it came from and tries to visit unvisited vertices from there. Eventually halts after backing up to the starting vertex, by then one connected component has been traversed. If unvisited vertices remain, dfs starts at one of them.
37
38
39
Adjacency list
40
Breadth-first Search
Start at a vertex, mark it visited Go to each of its neighbors and put them in a list Delete the starting vertex. Start at one of the remaining in the list, mark it visited, and so on...
41
42
BFS (contd.)
ALGORITHM BFS(G) mark each vertex in V with 0 as a mark of being unvisited count <- 0 Time complexity is similar for each vertex v in V do to DFS if v is marked with 0 Gives shortest path between bfs(v) two vertices bfs(v) Count <- count+1; mark v with count and initialize a queue with v while the queue is not empty do for each vertex w in V adjacent to the front vertex do if w is marked with 0 count <- count+1; mark w with count add w to queue remove the front vertex from the queue
43
44