Exhaustive search: definition
A brute force solution to a problem involving
search for an element with a special property,
usually among combinatorial objects such as a
permutations, combinations, or subsets of a set.
Design and Analysis of Algorithms Chapter 3 1
Exhaustive search: method
Construct a way of listing all potential solutions to
the problem in a systematic manner
all solutions are eventually listed
no solution is repeated
Evaluate solutions one by one, perhaps
disqualifying infeasible ones and keeping track of
the best one found so far
When search ends, announce the winner
Design and Analysis of Algorithms Chapter 3 2
Example 1: Traveling salesman problem
Given n cities with known distances between each
pair, find the shortest tour that passes through all
the cities exactly once before returning to the
starting city.
Alternatively: Find shortest Hamiltonian circuit in
a weighted connected graph.
Example: 2
a b
5 3
8 4
c 7
d
Design and Analysis of Algorithms Chapter 3 3
Traveling salesman by exhaustive search
Tour Cost .
abcda 2+3+7+5 = 17
abdca 2+4+7+8 = 21
acbda 8+3+4+5 = 20
acdba 8+7+4+2 = 21
adbca 5+4+3+8 = 20
adcba 5+7+3+2 = 17
Efficiency:
Design and Analysis of Algorithms Chapter 3 4
Traveling salesman by exhaustive search
Tour Cost .
abcda 2+3+7+5 = 17
abdca 2+4+7+8 = 21
acbda 8+3+4+5 = 20
acdba 8+7+4+2 = 21
adbca 5+4+3+8 = 20
adcba 5+7+3+2 = 17
Efficiency: (n-1)!/2
Design and Analysis of Algorithms Chapter 3 5
0-1 Knapsack problem
Given a knapsack with maximum capacity W, and
a set S consisting of n items
Each item i has some weight wi and benefit value vi
Problem: How to pack the knapsack to achieve
maximum total value of packed items?
Design and Analysis of Algorithms Chapter 3 6
0-1 Knapsack problem: a picture
Weight Benefit value
Items
wi vi
2 3
This is a knapsack 3 4
Max weight: W = 20 4 5
5 8
W = 20
9 10
Design and Analysis of Algorithms Chapter 3 7
0-1 Knapsack problem
Problem, in other words, is to find
max vi subject to w i W
iT iT
The problem is called a 0-1 problem,
because each item must be entirely accepted or
rejected.
In the Fractional Knapsack Problem, we can
take fractions of items.
Design and Analysis of Algorithms Chapter 3 8
0-1 Knapsack problem: brute-force approach
Lets first solve this problem with a
straightforward algorithm
We go through all combinations (subsets) and
find the one with maximum value and with
total weight less or equal to W
Design and Analysis of Algorithms Chapter 3 9
Example 2: Knapsack Problem
Given n items:
weights: w1 w2 wn
values: v1 v2 vn
a knapsack of capacity W
Find the most valuable subset of the items that fit into the
knapsack
Example:
item weight value Knapsack capacity W=16
1 2 $20
2 5 $30
3 10 $50
4 5 $10
Design and Analysis of Algorithms Chapter 3 10
Knapsack by exhaustive search
Subset Total weight Total value
0 $0
{1} 2 $20
{2} 5 $30 Most valuable subset?
{3} 10 $50
{4} 5 $10
{1,2} 7 $50
{1,3} 12 $70 Efficiency:
{1,4} 7 $30
{2,3} 15 $80
{2,4} 10 $40
{3,4} 15 $60
{1,2,3} 17 not feasible
{1,2,4} 12 $60
{1,3,4} 17 not feasible
{2,3,4} 20 not feasible
{1,2,3,4} 22 not feasible
Design and Analysis of Algorithms Chapter 3 11
0-1 Knapsack problem: brute-force approach
Algorithm:
We go through all combinations and find the one
with maximum value and with total weight less or
equal to W
Efficiency:
Since there are n items, there are 2n possible
combinations of items.
Thus, the running time will be O(2n)
Design and Analysis of Algorithms Chapter 3 12
Brute force strengths and weaknesses
Strengths:
wide applicability
simplicity
yields reasonable algorithms for some important problems
sorting; matrix multiplication; closest-pair; convex-hull
yields standard algorithms for simple computational tasks
and graph traversal problems
Design and Analysis of Algorithms Chapter 3 13
Brute force strengths and weaknesses
Weaknesses:
rarely yields efficient algorithms
some brute force algorithms unacceptably slow
e.g., the recursive algorithm for computing Fibonacci numbers
not as constructive/creative as some other design techniques
Design and Analysis of Algorithms Chapter 3 14
