This chapter covers
- Classifying optimization problems based on different criteria
- Classifying search and optimization algorithms based on the way the search space is explored and how deterministic the algorithm is
- Introducing heuristics, metaheuristics, and heuristic search strategies
- A first look at nature-inspired search and optimization algorithms
Before we dive into the problems and algorithms that I hinted at in chapter 1, it will be useful to be clear about how we talk about these problems and algorithms. Classifying problems allows us to group similar problems together and potentially exploit existing solutions. For example, a traveling salesman problem involving geographic values (i.e., cities and roads) may be used as a model to find the minimum length of wires connecting pins in a very large-scale integration (VLSI) design. The same can be said for classifying the algorithms themselves, as grouping algorithms with similar properties can allow us to easily identify the right algorithm to solve a problem and meet expectations, such as the quality of the solution and the permissible search time.