Exhaustive search, also known as brute force search or generate and test search, is a problem-solving technique that involves systematically enumerating all possible candidates for a solution and then checking each candidate to see if it satisfies the problem's constraints. This method is straightforward but can be computationally expensive, especially for large problem spaces, as it requires evaluating every possible option.
Key Characteristics of Exhaustive Search:
Enumeration of Candidates: The algorithm generates all possible solutions or configurations for the problem.
Testing Each Candidate: Each generated candidate is tested to determine if it meets the problem's requirements.
High Computational Cost: Due to the need to explore all possible solutions, exhaustive search often has exponential or factorial time complexity, making it impractical for large-scale problems.
Example:
A classic example of exhaustive search is solving the Travelling Salesman Problem (TSP), where the goal is to find the shortest possible route that visits a set of cities exactly once and returns to the origin city. An exhaustive search would involve generating all possible permutations of the cities and then checking each permutation to find the shortest route[6].
Applications:
Puzzle Solving: Sudoku, crossword puzzles, and other combinatorial puzzles.
