Introduction
This lecture explores Exhaustive Search, a brute-force algorithm design technique that systematically enumerates all possible solutions and selects the one that best meets the objective.
Although computationally expensive, exhaustive search is fundamental in algorithm design — especially for NP-hard combinatorial problems like:
-
Traveling Salesman Problem (TSP)
-
Knapsack Problem
-
Assignment Problem
Table of Contents
-
What is Exhaustive Search?
-
When to Use Brute Force
-
Problem 1: Traveling Salesman Problem (TSP)
-
Algorithm and Example
-
Complexity and Observations
-
-
Problem 2: Knapsack Problem
-
Algorithm and Example
-
Complexity and Observations
-
-
Problem 3: Assignment Problem
-
Algorithm and Example
-
Efficient Alternative: Hungarian Method
-
-
Strengths and Weaknesses of Brute Force
-
Where Brute Force Is Still Useful
-
Conclusion
What is Exhaustive Search?
Exhaustive Search (Brute Force) is a straightforward problem-solving approach that:
-
Generates all possible solutions.
-
Filters out infeasible ones (that violate constraints).
-
Selects the optimal feasible solution according to an objective function.
Used in combinatorial optimization, exhaustive search guarantees an optimal answer, but often with exponential time complexity.
When to Use Brute Force
-
Combinatorial optimization problems with no efficient known solution.
-
When n is small (usually ≤ 10–15).
-
When correctness is more important than speed.
-
For verification or benchmarking of smarter algorithms (e.g., Greedy or Dynamic Programming).
Problem 1: Traveling Salesman Problem (TSP)
Problem Statement
Find the shortest tour through n cities that visits each city exactly once and returns to the starting point.
Model:
-
Cities → vertices
-
Distances → weighted edges
Equivalent to finding a Hamiltonian circuit of minimal cost.
Algorithm and Example
Brute Force TSP Algorithm:
Example:
4 cities → A, B, C, D
Number of tours = (n−1)! = 6
| Tour | Cost |
|---|---|
| A → B → C → D → A | 18 |
| A → C → B → D → A | 11 (Optimal) |
| A → D → B → C → A | 11 (Optimal) |
Time Complexity: O(n!)
Problem 2: Knapsack Problem
Problem Statement
Given n items with weights
and values
, and a knapsack of capacity W, find the most valuable subset of items that fits within the capacity.
Algorithm and Example
Brute Force Knapsack Algorithm:
Example:
W = 10, Items:
| Item | Weight | Value |
|---|---|---|
| 1 | 7 | $42 |
| 2 | 3 | $12 |
| 3 | 4 | $40 |
| 4 | 5 | $25 |
Feasible subsets:
| Subset | Total Weight | Value | Feasible? |
|---|---|---|---|
| {1,2} | 10 | $54 | |
| {3,4} | 9 | $65 | (Optimal) |
Optimal Solution: Items 3 and 4
Time Complexity: O(2ⁿ)
Problem 3: Assignment Problem
Problem Statement
Assign n people to n jobs such that each person is assigned exactly one job and total cost is minimized.
Given cost matrix
: cost if person i does job j.
Algorithm and Example
Brute Force Assignment Algorithm:
Example:
| Job | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Person 1 | 9 | 2 | 7 | 8 |
| Person 2 | 6 | 4 | 3 | 7 |
| Person 3 | 5 | 8 | 1 | 8 |
| Person 4 | 7 | 6 | 9 | 4 |
All permutations (n! = 24) tested →
Optimal assignment = <1, 2, 3, 4> with total cost = 18
Time Complexity: O(n!)
Efficient Alternative: Hungarian Method
The Hungarian Algorithm solves the assignment problem in O(n³) time — a huge improvement over brute force. It’s based on cost matrix reduction and zero-based matching.
Strengths and Weaknesses of Brute Force
| Strengths | Weaknesses |
|---|---|
| Simple and easy to implement. | Exponential time complexity (O(2ⁿ), O(n!)). |
| Guarantees correct (optimal) result. | Impractical for large input sizes. |
| Useful for testing and benchmarking. | Repetitive computations and redundancy. |
Where Brute Force Is Still Useful
-
Problems with small input size (n ≤ 10–15).
-
Testing or debugging optimized algorithms.
-
Cryptography (password cracking).
-
Teaching algorithm fundamentals.
Conclusion
Exhaustive search (brute force) is the most basic algorithm design technique, systematically testing every possible solution to ensure optimality. Though inefficient for large datasets, it remains invaluable for small problems, conceptual clarity, and validation. Lecture # 16_new
