The Viterbi Algorithm

The Viterbi algorithm can find the most likely sequence using on the order of T*N² steps.

For fruit flies like flowers: on the order of 4*4² = 64 steps, a considerable saving on the naive approach

The Markov assumptions:

1.

probability of next state depends only on current state;

2.

probability of generating current output symbol depends only on current state.

Together, these assumptions mean that you don't need to enumerate all paths.

Sweep through network one word at a time recording the single best sequence ending in each state. For a good diagrammatic illustration of this process, see Chapter 7 of Allen.