5 Searching and Optimization
This chapter covers
- Recognizing search problems in the context of USACO.
- Solving search problems using an exhaustive search algorithm.
- Choosing a domain for performing the search.
- Enumerating the chosen domain.
- Accelerating an exhaustive search algorithm.
- Solving search problems using a greedy algorithm.
In search problems, as the name implies, we are searching for something. Search problems are a wide and intensive field of research and algorithms development in computer science. You are probably familiar with many of the applications of search algorithms: searching for a word in a document you are typing; searching for phrases on the web; searching for the shortest path to get from point A to point B. But searching problems have even broader applications, many of which involve searching in overt ways. For example, your autocorrect identifies the word closest to the one you tried to spell. Behind the scenes, it searches over all the possible words in its dictionary, refers to its knowledge of which words are used more frequently, and suggests a new word.