algorithmdynamic-programmingnotationviterbi

What does this line in the Viterbi algorithm specifically do?

Viterbi line

I am more concerned in understanding the assignment arrow to the left followed by max s'=1 to N. Disregard the semantics of the variables.

Thank you!

Solution

  • It is a recursive formula to determine the value of viterbi[s,t] for a given value of s and t.

    In fact, viterbi is a matrix of N rows, and s is a row number in that matrix, and t a column number.

    The value in the cell at s,t of the matrix is determined by taking all values in the previous column (column t-1, and row s' going from 1 to N), -- which are supposed to be already known -- and multiplying them by specific values from two other matrices (I ignore their role in this, but these matrices are a given, and the value of s, s' and t determine which value to pick from those matrices).

    From all these N products, the greatest is taken.

    When you start with known values for the first column (t = 1), you can find with this formula the values in the second column, and when you have those, the third, ...etc.