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.
Algorithms Every Programmer Should Know
Informed search is a search strategy that uses an estimate of remaining cost to guide which candidate to explore next.
- How it is used
- Guides graph search toward a goal by estimating remaining cost instead of exploring uniformly in every direction.
- How deep it goes
- Works through A* scores, queue updates, pseudocode, and complexity, including why the search continues after first finding the goal.
- Examples
- Uses road routing, grid movement, sliding-tile puzzles, and a six-intersection graph to illustrate heuristic choices and A*.
- What you can do after
- Build it from scratch by implementing A* with a priority queue, path costs, heuristic estimates, and parent pointers.
Read how Algorithms Every Programmer Should Know explains informed search →
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 →
What to know first
- brute-force searchBrute-force search is a search technique that systematically evaluates candidates in a defined search space, typically examining all possibilities without using selective shortcuts to narrow the search.
- shortest pathA shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
Related concepts
- A* 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 or decoding technique that repeatedly expands a limited set of the highest-scoring partial candidates.
- brute-force searchcontrasts with · Brute-force search is a search technique that systematically evaluates candidates in a defined search space, typically examining all possibilities without using selective shortcuts to narrow the search.
- heuristic functionuses · A heuristic function estimates the remaining distance or cost from a search state to a goal state.
- hill climbingincludes · Hill climbing is an iterative local-search optimization method that repeatedly moves from a candidate solution to a better neighboring solution.
Questions about informed search
What is informed search?
Informed search is a search strategy that uses problem-specific knowledge or heuristic estimates to prioritize promising states or paths.
Which Manning books explain informed search?
Optimization Algorithms: AI techniques for design, planning, and control problems, Algorithms Every Programmer Should Know and Grokking AI Algorithms, Second Edition.
What should I know before learning informed search?
Manning books that teach informed search usually introduce brute-force search and shortest path first.
What is the difference between informed search and brute-force search?
Informed search is a search strategy that uses problem-specific knowledge or heuristic estimates to prioritize promising states or paths. Brute-force search is a search technique that systematically evaluates candidates in a defined search space, typically examining all possibilities without using selective shortcuts to narrow the search.
What kinds of informed search are there?
Kinds of informed search include A* algorithm, beam search and hill climbing.
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.


