Speeding up Dynamic Programming Algorithms for Finding Optimal Lattice Paths
John L. Spouge · SIAM Journal on Applied Mathematics · 1989
Many problems can be reduced to finding an optimal lattice path. For example, minimum path integrals can be computed by discretizing to a lattice graph and then using the optimal lattice path to approximate the minimum continuous path. Finding an optimal alignment between two sequences can also be reduced to finding an optimal lattice path. Dynamic programming algorithms are generally, well-suited to such problems, but can be slow and require too much storage if the lattice is too large, for example, if the lattice dimension is too high. Faster algorithms requiring less computer storage can often be constructed by restricting calculations to a “computational volume” known to contain the optimal path. Upper and lower bounds on path distances from the problem domain can often help to produce small computational volumes.