Query phase

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

The online phase of an algorithm that answers a specific search or shortest-path query using preprocessed structures.

The query phase answers a specific shortest-path request after a contraction hierarchy has been built. Preprocessing supplies an augmented graph and a node order; the query uses them to avoid searching many less important nodes. This trades preprocessing time for faster queries, including on large road networks. section 4.3.4

To answer a source-to-target query:

• Run bidirectional Dijkstra’s search on the preprocessed graph, following edges toward increasingly important nodes. section 4.3.4
• Use the resulting route’s shortcut edges where needed, then unpack them to recover the route through the original graph. section 4.3.4

Figure 4.46 The solution path after unpacking the contracted edges. The original route returned by bidirectional Dijkstra's passes through the contracted edge (8,5), which is then unpacked into (8,3) and (3,5).

The route uses shortcut edge (8,5); unpacking it restores the original segments (8,3) and (3,5). section 4.3.4

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

How deep it goes

Describes restricted bidirectional search and shows shortcut unpacking in a route example.

Examples

Shows a road-network query and a route whose shortcut edge is unpacked into two original edges.

What it assumes

Assumes a weighted directed graph and a precomputed node order, while motivating importance through road types.

What you can do after

Practice/perform it by searching a preprocessed graph and unpacking shortcuts to recover the original route.

How it connects

Connects contraction hierarchies, node importance, shortcut edges, and bidirectional Dijkstra’s search.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

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.