greedy algorithm

[Jiahn K]

Are the Viterbi algorithm and a greedy algorithm different?
It seems Viterbi algorithms differs from a greedy algorithm in that it finds the best path in HMM, but both algorithms are basically to solve optimisation problems?

[Simon King]

The Viterbi algorithm is not a greedy algorithm. It performs a global optimisation and guarantees to find the most likely state sequence, by exploring all possible state sequences.

An example of a greedy algorithm is the one for training a CART. Unlike the Viterbi algorithm, this algorithm does not explore all possibilities: it takes a sequence of local, hard decisions (about the best question to split the data) and does not backtrack. It does not guarantee to find the globally-optimal tree.

[Author]

Posts