** Next:** LINEAR OPTIMIZATION
** Up:** NON-LINEAR OPTIMIZATION
** Previous:** Constrained optimization

The Viterbi algorithm is an optimized searching algorithm for finding the
shortest path. It has been used to decode the convolutional codes for
telecommunication. The key principle of this algorithm arises from
the observation that if the shortest path between point *A* and point *C*
passes a intermediate point *B*, then the segment of this path
between point *A* and point *B* is the shortest path between these two
points. The algorithm consists of two steps: forward shortest-path accumulation
and backward descending tracking. One can find the details of the algorithm in
an excellent reference (McEliece, 1977). I include a
subroutine of the Viterbi algorithm in Appendix A.
If the coherence measure in equations (5) or (6)
is chosen as the objective function, then the algorithm should search for
the longest-path, instead of shortest path. This can be easily done
by reversing the operations in the Viterbi algorithm.

At this point, I have not mentioned anything about the constraints imposed
by a model. In fact, simple models can be easily incorporated in the
Viterbi algorithm. For example, to obtain a smooth solution *p*(*t*), one can
eliminate all the transition branches that would cause abrupt changes
of the path. This procedure provides two benefits; not only does it
constrain the smoothness of the solution, but it also reduces the computation
time because the solution space to be searched is reduced.
Field data examples show that this procedure works well for
many applications.

** Next:** LINEAR OPTIMIZATION
** Up:** NON-LINEAR OPTIMIZATION
** Previous:** Constrained optimization
Stanford Exploration Project

12/18/1997