Graduiertenkolleg 1194 "Selbstorganisierende Sensor-Aktor-Netzwerke"

Heuristic Contraction Hierarchies with Approximation Guarantee

  • Tagung:

    Symposium on Combinatorial Search (SoCS 2010)

  • Tagungsort:

    Stone Mountain, Atlanta, Georgia, USA

  • Datum:

    Juli 2010

  • Autoren:

    R. Geisberger, D. Schieferdecker

  • Referent:

    Robert Geisberger

  • Abstract

    We present a new heuristic point-to-point shortest paths algorithm based on contraction hierarchies (CH). Given an epsilon > 0, we can prove that the length of the path computed by our algorithm is at most (1 + epsilon) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid shortcuts even when a replacement path is epsilon times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.