Informed search uses knowledge about a problem to guide exploration toward promising solutions instead of searching blindly. That knowledge is expressed through heuristics: rules of thumb that evaluate how promising a state appears. A heuristic is an educated guess, not a guaranteed truth. section 3.1 section 3.2
A guided search typically works by:
- Representing possible situations as states or branches that can be explored. section 3.1
- Scoring or ranking states with a heuristic based on problem-specific knowledge. section 3.1
- Choosing an informed search algorithm suited to the problem, such as greedy search or A*. section 3.2
Choosing a useful route heuristic
For GPS routing, a useful heuristic might favor shorter travel time, less traffic, lower tolls, or better road conditions. Straight-line distance alone can be misleading because roads rarely follow a direct line between destinations. section 3.1
From exhaustive comparison to guided matching
Checking whether an uploaded audio clip appears in a copyrighted library could compare every time slice with every stored clip. Frequency-based comparisons provide problem-specific information that can guide a more focused search. section 3.1
Common applications include:
- Finding paths for autonomous game characters. section 3.5
- Generating and decoding text by looking ahead across multiple possible word sequences. section 3.5
- Routing traffic through telecommunications networks represented as graphs. section 3.5
- Solving single-player games and puzzles by exploring decision trees. section 3.5
Figure 3.1 Comparison of two audio clips using frequency distribution
Compare audio clips through their frequency distributions when considering guided audio matching. section 3.1
