A dynamic programming algorithm to find all solutions in a neighborhood of the optimum

Just after introducingdynamic programming, Richard Bellman with R. Kalaba in 1960 gave a method for finding Kth best policies. The method has been modified since then, but it is still not practical for many problems. This paper describes a new technique which modifies the usual backtracking procedure and lists all near-optimal policies. This practical algorithm is very much in the spirit of the original formulation of dynamic programming. An application to matching biological sequences is given.