In this case We want to find the most likely state sequence for a
given sequence of observations, 
and a model, 
The solution to this problem depends upon the way ``most likely state
sequence'' is defined. One approach is to find the most likely state
at t=t and to concatenate all such ' 's. But some times
this method does not give a physically meaningful state sequence.
Therefore we would go for another method which has no such problems.
In this method, commonly known as Viterbi algorithm, the whole
state sequence with the maximum likelihood is found. In order to
facilitate the computation we define an auxiliary variable,
which gives the highest probability that partial observation sequence
and state sequence
up to t=t can have, when the current state is i.
It is easy to observe that the following recursive relationship holds.
where,
So the procedure to find the most likely state sequence starts from
calculation of 
using recursion in 1.8, while always keeping a pointer to the
``winning state'' in the maximum finding operation. Finally
the state 
, is found where
and starting from this state, the sequence of states
is back-tracked as the pointer in each state indicates.This gives the
required set of states.
This whole algorithm can be interpreted as a search in a graph whose
nodes are formed by the states of the HMM in each of the time instant
.
