A search space is the set of possible solutions an algorithm can explore. Each solution may be a sequence of decisions or actions leading toward a goal. Some paths overlap, cost more, or produce better results than others. section 1.8 section 2.3
The shape and size of the search space affect how a problem can be solved:
- Search problems look for a path to a goal, such as traveling between cities or moving through a maze. section 1.8 section 2.3
- Optimization problems contain many valid solutions and seek one that performs best under constraints, such as fitting luggage into a limited trunk. section 1.9
- A local best is strongest within one region of the space; a global best is strongest across the entire space. section 1.9
Finding a path through a maze
Imagine a 10-by-10 maze with barriers and a goal. The player can move north, south, east, or west, but not diagonally. Each possible route is part of the search space. Trial and error may find several valid paths: some take 17 or 23 actions, while another takes 15 and is currently the best found. A larger maze makes exhaustive exploration much harder, so the search algorithm and its configuration matter. section 2.3
Figure 2.4 An example of the maze problem
Use the maze diagram to visualize barriers, legal moves, goals, and the possible paths that make up a search space. section 2.3
