Overview
4 Informed Search Algorithms
This chapter introduces informed search, where algorithms exploit knowledge of the problem space—such as estimated distance to a goal or accrued costs—to guide exploration more efficiently than blind search. It frames the landscape around two major objectives: connecting all nodes at minimum total cost via minimum spanning trees (MSTs) and finding the shortest path between specific nodes. The survey spans classic MST methods (Borůvka, Jarník–Prim, Kruskal) and shortest-path strategies ranging from local and heuristic-driven searches (Hill Climbing, Beam Search, A*) to large-scale speed-up techniques based on hierarchy and pruning (e.g., Contraction Hierarchies). Throughout, the chapter emphasizes how heuristics shape performance, optimality, and scalability.
The MST section formalizes spanning trees and minimum-weight spanning trees, then demonstrates how to construct them, focusing on Kruskal’s algorithm: sort edges by weight, add the cheapest non-cycling edge, and continue until all vertices are connected. Through examples that include a “Muddy City” budgeted road-repair scenario and a real urban network, it shows how MSTs minimize total connection cost but do not guarantee shortest pairwise routes in the resulting network. Practical implementations illustrate how to detect cycles, ensure connectivity, and apply MSTs to real maps, while noting broad applications in network design, clustering, image segmentation, and facility location.
The shortest-path section contrasts algorithms by their search behavior and trade-offs. Hill Climbing greedily improves locally and can stall on plateaus or local optima; Beam Search limits breadth via a beam width, reducing memory yet risking incompleteness; A* integrates actual cost and heuristic estimates f(n)=g(n)+h(n), relying on admissible heuristics (and possibly weights) for speed and near- or full optimality. For continent-scale routing, hierarchical methods (especially Contraction Hierarchies) preprocess the graph by contracting less important nodes and adding shortcuts, then answer queries quickly with a constrained bidirectional search and shortcut “unpacking.” A routing case study shows that while Hill Climbing and Beam Search may find good solutions at higher time/space cost and A* can be very fast with a suitable heuristic, Contraction Hierarchies deliver optimal routes with dramatically fewer explored nodes after an upfront preprocessing investment. The chapter closes by stressing that algorithm choice should match problem constraints, data availability, and performance needs.
Examples of Informed Search Algorithms. Each algorithm has multiple variants based on improvements, specific use cases, and specialized domains.
Muddy City Problem. The roads in this town are badly damaged, but there isn’t enough money to repair them all.
Examples of Spanning Trees. The middle and right trees reach every node of graph G with no loops or cycles.
Solving the Muddy City problem using Kruskal’s algorithm – Original graph.
Solving the Muddy City problem using Kruskal’s algorithm – Step 1.
Solving the Muddy City problem using Kruskal’s algorithm – Step 2.
Solving the Muddy City problem using Kruskal’s algorithm – Step 3.
Solving the Muddy City problem using Kruskal’s algorithm – Step 4.
Solving Muddy City Problem using Kruskal’s Algorithm. The algorithm adds edges to the final tree by ascending weight order, ignoring edges that will form a cycle.
Muddy City Problem solved using Kruskal’s algorithm. The highlighted edges are part of the minimum spanning tree.
MST generated by Kruskal algorithm. All the edges included in the MST are highlighted. There are no cycles in the MST, and the total weight of the tree is minimized.
Depending on the initial state, hill-climbing may get stuck into local optima. Once it reaches a peak, the algorithm will stop since any new successor will be down the hill.
Variants of the Hill Climbing Algorithm.
An 8 Points of Interest (POIs) Road Network in the form of a graph.
An 8 Point of Interest (POIs) Road Network in the form of a tree.
Shortest path between S and G using hill climbing algorithm.
Using hill climbing algorithm to solve the 8-puzzle problem. At each iteration, the algorithm explored neighboring states, looking for the minimum heuristic value.
States of the hill climbing solution to 8-Puzzle. Each subsequent state is selected by minimizing its cost, compared to its neighbors. As the 8-Puzzle problem has not only a well-defined but also achievable goal state, the termination condition of the algorithm (goal is reached) coincides with the “peak” of the hill (in this case the “valley”, as it is a minimization problem).
Shortest path between S and G using a beam search algorithm. With a beam width w=2, two states are kept in the beam at each iteration. After generating the neighbors of each element in the beam, only the best w beams are kept.
Solution using a beam width of w=2. The highlighted line represents the solution path.
An 8 Point of Interest (POIs) Road Network in the form of a graph with heuristic information (straight line distance to the goal) shown above each vertex.
A* steps to find the shortest path between source node S and destination/goal node G in 8 Point of Interest (POIs) Road Network. The sum of the already incurred costs and the distance to the goal is used as the heuristic value to determine whether to expand a certain node.
Node contraction operation. The number in brackets denotes the cost of the added shortcut.
Witness Path. There exists another path from u to w that is shorter, so no shortcut is needed when contracting v.
Example of CH Preprocessing Phase
Example of edge difference in case of edge node A.
Example of edge difference in case of hub node. The numbers in brackets denote the cost of the added shortcuts.
Query Phase
CH example
Graph Contraction using an arbitrary node ranking - Contracting node 1
Graph Contraction using an arbitrary node ranking - Contracting node 2
Graph Contraction using an arbitrary node ranking - Contracting node 3
Graph Contraction using an arbitrary node ranking - Contracting node 4
Graph Contraction using an arbitrary node ranking - Contracting node 5
Graph Contraction using an arbitrary node ranking - Contracting node 6
Graph Contraction using an arbitrary node ranking - Contracting node 7
Graph Contraction using an arbitrary node ranking - Contracting node 8
Graph Contraction using an arbitrary node ranking - Contracting node 9
Graph Contraction using an arbitrary node ranking - Contracting node 10
Graph Contraction using an arbitrary node ranking - Contracting node 11
Graph Contraction using an arbitrary node ranking - Contracting node 12
Solving a road network problem using Contraction Hierarchies (CH) algorithm – Upward Graph
Solving a road network problem using Contraction Hierarchies (CH) algorithm – Downward Graph
Solving a road network problem using Contraction Hierarchies (CH) algorithm – Meeting Point
Solving a road network problem using Contraction Hierarchies (CH) algorithm – Shortest Path
Solution path after unpacking contracted edges. The original route returned by Bidirectional Dijkstra passes through the contracted edge (8,5), which was then unpacked into (8,3) and (3,5).
Shortest path solution generated using hill climbing. The solution shown here uses a n-value of 100, which increases the total processing time but returns better and more consistent results.
Shortest path using a beam search algorithm. This solution was generated using k=10 and n=20, which means that 20 routes were generated for each route in the beam, and the top 10 routes were kept for each new beam. Lower k and n values will improve processing time but reduce the likelihood of generating a near-optimal or optimal solution.
Shortest path using A* algorithm. Better heuristic functions that closely approach the actual costs from any node to the goal will return better results.
Summary
- Informed search algorithms use domain-specific knowledge or heuristic information to reduce the search effort without sacrificing optimality or sub-optimality if optimal solutions cannot be reached.
- Informed search algorithms can be used to solve minimum spanning tree (MST) problems and to find the shortest path between two nodes in a graph.
- Borůvka algorithm, Jarník-Prim algorithm, and Kruskal algorithm are informed search algorithms to solve MST problems. An MST is a tree that contains the least weight among all the other spanning trees of a connected weighted graph. Kruskal's algorithm is a greedy algorithm that computes the MST for an undirected connected weighted graph by repeatedly adding the next shortest edge that doesn't produce a cycle.
- Hill climbing (HC), Beam Search, Best-first Search, A* algorithm, and Contraction hierarchies (CH) are examples of informed search algorithms that can be used to find the shortest path between two nodes.
- HC algorithm is a local greedy search algorithm that tries to improve the efficiency of depth-first by incorporating domain-specific knowledge or heuristic information.
- Beam Search expands the most promising node within a limited predefined set defined by the beam width.
- Best-first search is a greedy algorithm that always expands the node that is closest to the goal node based on heuristic information only.
- A* algorithm is a special case of best-first algorithm that incorporates both the actual cost and a heuristic estimate of the cost to get the goal from a given state.
- CH is a speed-up technique to improve the performance of pathfinding. During the preprocessing phase, each node is contracted in order of importance (from least important to most important) and shortcuts are added to preserve the shortest paths. Then bidirectional Dijkstra's algorithm is applied to the resultant augmented graph to compute shortest paths between the source node and the target node.
FAQ
What is an informed search algorithm, and how does it differ from blind search?
Informed search uses domain knowledge gathered during the search (heuristics like estimated distance-to-go or costs) to guide expansion toward promising states. Blind search (e.g., BFS, DFS, Dijkstra in its pure form) follows fixed rules without such guidance and only recognizes the goal when found.What is a Minimum Spanning Tree (MST) and when should I use it?
An MST connects all vertices of a connected, undirected, edge-weighted graph with no cycles and with the minimum possible total edge weight. Use MSTs when you must connect all nodes at minimal total cost (e.g., network design, Muddy City road repair), not when you need the shortest path between a specific pair of nodes.How does Kruskal’s algorithm construct an MST?
Kruskal’s algorithm sorts edges by increasing weight and adds them one by one, skipping any edge that would form a cycle, until all vertices are connected. In practice, cycle checks can use a union–find structure (or library helpers like networkx’s find_cycle), and the process stops when the graph becomes connected.What are the informed shortest-path algorithms covered, and what are their typical uses?
- Hill Climbing: Greedy local improvement; low memory, can get stuck in local optima/plateaus.- Beam Search: Keeps the best w candidates per level; prunes aggressively, incomplete but memory-efficient vs BFS.
- A*: Expands nodes minimizing f(n)=g(n)+h(n); optimal with admissible h(n), often fastest with good heuristics.
- Hierarchical approaches (e.g., Contraction Hierarchies): Heavy preprocessing to prune search space and enable very fast queries at scale.
How does A* work, and what makes a heuristic “admissible”?
A* selects nodes minimizing f(n)=g(n)+h(n) where g(n) is cost from the start and h(n) estimates the cost to the goal. A heuristic is admissible if it never overestimates the true remaining cost, which guarantees optimality. Special cases: h(n)=0 reduces to uniform-cost search; weighted A* uses f(n)=g(n)+w·h(n) (w>1) to prioritize the heuristic.Why can Hill Climbing and Beam Search miss the optimal path, and how can variants help?
Both are local/incomplete: they may get trapped at local optima or discard promising states. Mitigations include steepest-ascent, stochastic choices, and random-restart (for Hill Climbing), and tuning beam width w or thresholds (for Beam Search). However, neither guarantees optimality.What are Contraction Hierarchies (CH), and how do they speed up routing?
CH precomputes a hierarchy by contracting less important nodes and adding “shortcut” edges that preserve shortest paths. At query time, a bidirectional search runs on the contracted graph (upward/downward graphs), exploring far fewer nodes, then “unpacks” shortcuts to recover the original path. This yields large speedups with minimal loss of optimality (when paired with Dijkstra).How are real-world road networks handled in the chapter’s examples?
- Data: OpenStreetMap via OSMnx (graph_from_point, nearest_nodes).- MST tip: Convert directed to undirected (to_undirected) when needed.
- Costs: Use edge attributes (e.g., length).
- Heuristics: Straight-line estimates; for geo accuracy, use haversine distance for non-local searches.
- Libraries: optalgotools for search utilities; Pandana (CH-based backend) for fast accessibility queries.
What are the practical trade-offs among A*, CH, Hill Climbing, and Beam Search?
- Hill Climbing/Beam: Simple and flexible but can be slow on large graphs and may return suboptimal routes.- A*: Very fast with good heuristics; optimal with admissible h(n); may need memory to store heuristic values.
- CH: Requires expensive preprocessing but enables extremely fast, scalable, and (with Dijkstra) optimal queries.
Optimization Algorithms ebook for free
