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: | Yannakakis M., Papadimitriou C.H. |
Keywords: | heuristics |
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.