Informed search
Informed search is a search strategy that uses problem-specific knowledge or heuristic estimates to prioritize promising states or paths.
Optimization Algorithms: AI techniques for design, planning, and control problems
A graph-search strategy that uses problem-specific heuristic information to prioritize promising states or paths.
- How it is used
- Guides graph exploration for minimum spanning trees, shortest paths, and routing problems by exploiting problem-specific information.
- How deep it goes
- Defines heuristic guidance, classifies algorithms, and distinguishes key methods, but does not provide implementation code or formal guarantees.
- Examples
- Uses the 8-puzzle, minimum spanning trees, shortest-path graphs, and real-world routing to illustrate heuristic search.
- What you can do after
- Apply informed search to select heuristic graph algorithms for spanning-tree, shortest-path, and routing problems.
Grokking AI Algorithms, Second Edition
Informed search is a search technique that uses domain knowledge or heuristic guidance to direct exploration toward promising solutions.
- How it is used
- Directs search through problem-specific knowledge when blind breadth-first or depth-first exploration is inefficient.
- How deep it goes
- Defines heuristics and names greedy search and A*, but stops short of detailed algorithm mechanics or proofs.
- Examples
- Uses pizza preferences, GPS routing, audio matching, game characters, language generation, networks, and puzzles.
- What you can do after
- Evaluate when domain knowledge can guide search and select a suitable heuristic-search approach.
Read how Grokking AI Algorithms, Second Edition explains informed search →
Related concepts
- A-star algorithmincludes · A* is an informed graph-search algorithm that prioritizes paths or states by combining the cost incurred so far with a heuristic estimate of the remaining cost to a goal.
- heuristicuses · A heuristic is a practical rule or approximate method for guiding judgment, search, or problem solving without guaranteeing an exact or optimal result.
- beam searchincludes · Beam search is a heuristic search and decoding technique that iteratively expands a limited set of the highest-scoring partial candidates.
- brute-force searchcontrasts with · Brute-force search systematically tests many or all candidates in a defined search space, without relying on selective shortcuts to narrow it.
- heuristic functionuses · A heuristic function estimates the remaining distance or cost from a search state to a goal state.
- shortest pathaddresses · A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.