Question

Explain how exhaustive search can be applied to the sorting problem and determine the efficiency class of such an algorithm.​

Answer 1

Answer:

Exhaustive search is simply a brute-force approach to combinatorial prob-lems. It suggests generating each and every element of the problem domain, se-lecting those of them that satisfy all the constraints, and then finding a desired element (e.g., the one that optimizes some objective function). Note that although the idea of exhaustive search is quite straightforward, its implementation typically requires an algorithm for generating certain combinatorial objects. We delay a dis-cussion of such algorithms until the next chapter and assume here that they exist.

We illustrate exhaustive search by applying it to three important problems: the traveling salesman problem, the knapsack problem, and the assignment problem.