liveBook · Manning

Graph hierarchical search

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A search algorithm that organizes states or graph elements into levels and uses that hierarchy to reduce the amount of search required.

Graph hierarchical search reduces the nodes explored in large routing problems by using levels of importance. On a road network, local streets lead to major roads; highways carry the long-distance portion; smaller roads return near the destination. This matters when a navigation app needs faster answers than basic Dijkstra search can provide. section 4.3.4

Two ways to use a hierarchy are:

  • Assign road levels and use them, along with distance to the destination, to guide which nodes a modified search expands. section 4.3.4

A long drive

For a New York–Miami trip, search can emphasize local roads near departure, highways across the middle, and smaller roads near arrival instead of exploring millions of road nodes. section 4.3.4

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Explains road-level search guidance and illustrates contraction preprocessing, queries, and shortcut unpacking without formal proofs.
Examples
Uses a New York–Miami drive, node-contraction figures, and a NetworkX listing with predetermined node order.
What it assumes
Assumes familiarity with Dijkstra search and graph nodes while introducing road hierarchy through a driving example.
What you can do after
Evaluate/understand how road levels or contraction shortcuts can limit exploration while producing a route.
How it connects
Links road network graphs, admissible heuristics, A*, bidirectional Dijkstra search, and contraction hierarchies.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.