# ViterbiAlgorithm

Version 1 (modified by llogan, 6 years ago) (diff)

make initial page from "doc/viterbi.txt"

This is a quick description of the Viterbi algorithm, aka dynamic programming algorithm.

Assume we have a 2D table:

```    O   O   O   O   O   O   O

O   O   O   O   O   O   O

O   O   O   O   O   O   O

O   O   O   O   O   O   O
```

That table has edges connecting points from each column to the next column and each edge has a score (only some edge and scores shown to keep it readable):

```    O--5--O-----O-----O-----O-----O
2   / 7   / \   / \   / \   /
\ /   \ /   \ /   \ /   \ /
O7-/--O--/--O--/--O--/--O--/--O
\/ \/ 1/ \/ \/ \/ \/ \/ \/ \/
/\ /\ 2\ /\ /\ /\ /\ /\ /\ /\
O3-/--O--/--O--/--O--/--O--/--O
/ \   / \   / \   / \   / \
1   \ 9   \ /   \ /   \ /   \
O--2--O--1--O--5--O--3--O--8--O
```

Our goal is to find a path from left to right through it which minimizes the sum of the score of all edges. Of course left/right is just a convention here as it could be top/down too. Similarly the minimum could be the maximum by just flipping the sign.

Example of a path with scores:

```    O   O   O   O   O   O   O

>---O.  O   O  .O-2-O   O   O
5.     .7      .
O   O-1-O   O   O 8 O   O
.
O   O   O   O   O   O-1-O---> (sum here is 24)
```

The Viterbi algorithm simply solves column by column. For the previous column each point has a best path and a associated score:

```    O-----5     O
\
\
O  \  1     O
\/
/\
O  /  2     O
/
/
O-----2     O
```