Informed search uses knowledge about a search space to prioritize promising states or paths. Unlike blind search, it guides exploration with domain-specific information such as distance to the target or incurred cost. section 4.0 section 4.1
Use informed search for two broad classes of graph problems:
- Minimum spanning trees: Borůvka’s, Jarník–Prim’s, and Kruskal’s algorithms seek a least-weight spanning structure. section 4.1 section 4.5
- Shortest paths: hill climbing, beam search, best-first search, A*, and contraction hierarchies use heuristics to reduce the search. section 4.3 section 4.5
A heuristic estimates how far a state is from the goal. In the 8-puzzle, the number of misplaced tiles provides one such estimate. Best-first search uses the heuristic alone; A* combines it with the actual cost already incurred. Beam search limits expansion to a chosen beam width, while contraction hierarchies preprocess a graph with shortcuts before applying bidirectional Dijkstra’s algorithm. section 4.1 section 4.5
Routing a large graph
A routing problem can use domain knowledge to estimate distance to the destination and prune unlikely paths. When repeated queries justify preprocessing, contraction hierarchies add shortcuts while preserving shortest paths, then search the augmented graph. section 4.0 section 4.5
Figure 4.1 Examples of informed search algorithms. Each algorithm has multiple variants based on improvements, specific use cases, and specialized domains.
Compare informed-search families and their variants by problem type and specialized use case. section 4.1
