Shortest paths without a map

Shortest paths without a map

0.00 Avg rating0 Votes
Article ID: iaor19981333
Country: United States
Volume: 84
Issue: 1
Start Page Number: 127
End Page Number: 150
Publication Date: Jan 1991
Journal: Theoretical Computer Science
Authors: ,
Keywords: heuristics
Abstract:

We study several versions of the shortest-path problem when the map is not known in advance, but is specified dynamically. We are seeking dynamic decision rules that optimize the worst-case ratio of the distance covered to the length of the (statically) optimal path. We describe optimal decision rules for two cases: layered graphs of width two, and two-dimensional scenes with unit square obstacles. The optimal rules turn out to be intuitive, common-sense heuristics. For slightly more general graphs and scenes, we show that no bounded ratio is possible. We also show that the computational problem of devising a strategy that achieves a given worst-case ratio to the optimum path in a graph with unknown parameters is a universal two-person game, and thus PSPACE-complete, whereas optimizing the expected ratio is NP-hard.

Reviews

Required fields are marked *. Your email address will not be published.