Exhaustive Search
- Exhaustive search is a brute-force technique used to solve combinatorial and optimization problems.
- It involves generating all possible solutions, checking which satisfy the problem’s constraints, and selecting the best one based on the objective.
- These problems usually involve structures like permutations, combinations, or subsets.
- Though simple in concept, exhaustive search becomes inefficient for large inputs due to exponential growth in possibilities.
Traveling Salesman Problem (TSP)
Objective: Find the shortest possible tour that visits each city exactly once and returns to the starting city.
Represented using a weighted graph where vertices are cities and edge weights are distances.
Exhaustive search:
- Fix a starting city.
- Generate all (n − 1)! permutations of the remaining cities.
- Calculate the total tour length for each.
- Select the shortest one.
To reduce computation, reverse duplicates can be ignored, reducing the number of tours to (n − 1)! / 2.
Still, the approach is impractical for large n due to exponential time complexity.
Knapsack Problem
Instance of the knapsack problem.
- Given: n items with weights and values, and a knapsack with capacity W.
- Objective: Find the most valuable subset of items with total weight ≤ W.
- Exhaustive search:
- Generate all 2ⁿ subsets.
- For each, calculate total weight and value.
- Select the highest value subset that meets the weight constraint.
- This leads to exponential time complexity, making it inefficient for large n.
Solution by exhaustive search. The information about the optimal selection is in bold