What is exhaustive search?
Exhaustive search, also known as brute-force search, is a problem-solving technique that involves systematically checking every possible solution to a problem until the optimal solution is found. It guarantees finding the best solution, but it can be computationally expensive, especially for problems with a large number of possible solutions.
How it works?
Here's how exhaustive search works:
Define the problem space: This involves identifying all possible solutions to the problem.For example, if you're trying to find the shortest path between two cities, the problem space would be all possible routes between those cities.
Enumerate all possible solutions: This involves systematically listing every single solutionin the problem space. This can be done using various techniques, such as recursion oriteration.
Evaluate each solution: Each solution is evaluated based on a predefined criteria to determine its quality. For example, in the shortest path problem, the criteria would be the totaldistance of each route.
Select the best solution: After evaluating all solutions, the one that best meets the criteriais chosen as the optimal solution.
While exhaustive search guarantees finding the best solution, it has some drawbacks:
Computational complexity: As the number of possible solutions increases, the time andresources required to perform an exhaustive search grow exponentially. This can make itimpractical for problems with a very large search space.
Inefficiency: In many cases, there might be more efficient algorithms or heuristics that canfind a good solution without having to explore every possibility.
Despite its limitations, exhaustive search is still a valuable technique in several situations:
When the problem space is relatively small: If the number of possible solutions ismanageable, exhaustive search can be a straightforward way to find the optimal solution.
When finding the absolute best solution is critical: In some cases, finding the bestpossible solution is essential, even if it requires significant computational resources.
As a baseline for comparison: The performance of other search algorithms can be compared against exhaustive search to assess their efficiency and accuracy.
How to solve knapsack problem with it?
Let's solve the knapsack problem with the given items and a knapsack capacity of 10 usingexhaustive search.
Items: [(3, 12), (5, 23), (1, 5), (6, 30)]
Knapsack Capacity: 10
Steps:
Generate all possible combinations:
We have 4 items, so there are 2^4 = 16 possible combinations (including the emptycombination).
Evaluate each combination:
For each combination, calculate the total weight and total value.
Discard combinations that exceed the capacity (10).
Select the best combination:
Choose the valid combination with the highest total value.
Let's solve the knapsack problem with the given items and a knapsack capacity of 10 usingexhaustive search.
Items: [(3, 12), (5, 23), (1, 5), (6, 30)]
Knapsack Capacity: 10
Steps:
Generate all possible combinations:
We have 4 items, so there are 2^4 = 16 possible combinations (including the emptycombination).
Evaluate each combination:
For each combination, calculate the total weight and total value.
Discard combinations that exceed the capacity (10).
Select the best combination:
Choose the valid combination with the highest total value.
Evaluating Combinations:
Here's a table summarizing the evaluation of each combination:
CombinationIncluded Items(Indices)TotalWeightTotalValueValid?
Combination Indices Total Weight Total Value Valid?
0 {} 0 0 Yes
1 {0} 3 12 Yes
2 {1} 5 23 Yes
3 {0, 1} 8 35 Yes
4 {2} 1 5 Yes
5 {0, 2} 4 17 Yes
6 {1, 2} 6 28 Yes
7 {0, 1, 2} 9 40 Yes
8 {3} 6 30 Yes
9 {0, 3} 9 42 Yes
10 {1, 3} 11 53 No
11 {0, 1, 3} 14 65 No
12 {2, 3} 7 35 Yes
13 {0, 2, 3} 10 47 Yes
14 {1, 2, 3} 12 58 No
15 {0, 1, 2, 3} 15 67 NoOptimal Solution:
From the table, we can see that the valid combination with the highest total value is combination11, which includes items 0, 1, and 3. This combination has a total weight of 9 and a total value of47.
Therefore, the optimal solution for this knapsack problem is to select items with indices 0, 1, and 3,resulting in a maximum value of 47.
Overall, exhaustive search is a powerful but computationally expensive technique for finding the optimal solution to a problem. While it guarantees finding the best answer, its practicality depends on the size and complexity of the problem space.