Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming
Thomas H. Byers, Michael S. Waterman · 1984
This paper presents a new algorithm for finding all solutions with objective function values in the neighborhood of the optimum for certain dynamic pro-gramming models, including shortest path problems. The new algorithm com-bines the depth-first search with stacking techniques of theoretical computer science and principles from dynamic programming to modify the usual back-tracking routine and list all nearoptimal policies. The resulting procedure is the first practical algorithm for a variety of large problems that are of interest. HE ALGORITHM presented in this paper was motivated by a study T of the evolutionary distance problem in molecular biology. In this context, dynamic programming methods are used to investigate evolutionary relationships between two DNA sequences (Smith et al. [1981]). The specific sequences studied implied a network of approximately 2,200 nodes and 110,OOO arcs so that analysis by Kth shortest path methods was not practical. Details of this study have been published elsewhere (Waterman [1983]). Consider a directed acyclic network or, more generally, a network with no cycle whose length is nonpositive. A simple method is presented for finding all paths from node 1 to node N whose lengths are within a prescribed distance e(e 2 0) of the length of the shortest path(s) from node 1 to node N. The algorithm uses a push-down (last-in, first-out) stack and has modest memory requirements. This new method is easy to understand and to code, which, with the memory requirements, accords it a special advantage over Kth shortest path calculations. See Dreyfus [ 19691 for a review of shortest path algorithms. To describe the new method let t(x, y) denote the length of arc (x, y) in the network. With f(N) = 0, let f(x) denote the length of the shortest Subject clrrssificatbn: 111 near-optimal policies.