answer solve(p)
candidates = generate-all-candidates(p)
for each candidate in candidates
if solution(p, candidate)
return candidate
return none
Example
files file-pack(files)
candidates = possible-packings(file)
max = 0
solution = nil
for each c in candidates
if c.size ≤ 700 and c.size > max
solution = c
max = c.size
return solution
Functions with exponential worst-case bounds are intractable.
Palliatives
Exhaustive search works well for small values of n.
N less than 35 for file packing.
Some problems may not have exponentially many candidate solutions.
There are only O(n2) lines through n planar points.
Remember This?
The maximum path-sum problem.
Given a number triangle, find a path with maximum sum.
The Algorithm
max-sum-path(triangle)
all-paths = all-paths(triangle)
max-path = pick(all-paths)
max-sum = path-sum(triangle, max-path)
for each path in all-paths
sum = path-sum(triangle, path)
if sum > max-sum
max-sum = sum
max-path = path
return [ max-sum, max-path ]
Generating All Paths
How do you generate all paths?
Each row requires a choice between two directions.
This is a disguised subset problem.
Subset Generation
Whenever a solution repeatedly picks one of two choices, think
“subsets.”
Subsets of { f1, f2, ..., fn }.
For each fi, is fi in the subset?
Paths through a number triangle.
At each level, go left or go right?
N binary choices is equivalent to a n-bit binary number.
Exhaustive Sorting
How would you implement sorting using exhaustive search?
sort(a[])
candidates = generate-all-candidates(a)
for each candidate in candidates
if sorted(candidate)
return candidate
return none
route file-route(cities)
candidates = possible-routes(cities)
solution = pick c in candidates
min = c.size
for each c in candidates
if c.size < min
solution = c
min = c.size
return solution
Generating Routes
How do you generate routes?
Subject to road constraints, any list of the cities is a route.
The first and last cities are connected.
That is, a route is a permutation of the city list.
And there are O(n!) such routes.
Implementation Details
The three most important details for exhaustive search are
The algorithm outline.
The candidate-generating code.
The candidate-checking code.
The candidate-checking code is closely related to the problem and
usually simple.
Decision problems have straightforward exhaustive searches:
answer bool solve(p)
candidates = generate-all-candidates(p)
for each candidate in candidates
if solution(p, candidate)
return candidate true
return none false
Optimization Problem Solutions
Optimization problems have slightly less straightforward exhaustive
searches:
answer solve(p)
candidates = generate-all-candidates(p)
best = pick a candidate
for each candidate in candidates
if candidate is better than best
best = candidate
return best
Generating Candidates
Generating candidates usually involves one of three techniques:
Candidate generation must be consistent and regular.
No duplicate candidates, no missed candidates.
Generating Subsets
Subsets have already been identified with n-bit numbers.
generate(problem)
candidates = { }
n = problem.size()
for i = 0 to 2n - 1
candidates.add(select(i, problem))
return candidates
select() makes subsets based on i's 1 bits.
Generating Permutations
Permutations can be lexicographically ordered.
generate(problem)
candidates = { }
p = first-permutation(problem)
do candidates.add(p)
p = next-permutation(p)
while p ≠ first-permutation(problem)
return candidates
