What is the difference between the Viterbi algorithm and beam search? I'm just confused because I'm having trouble wrapping my head around the difference. If we were to set the beam size to be equal to the number of possible states, wouldn't that mean the beam search algorithm is equivalent to the Viterbi algorithm?
The only true difference I can think of between the two is that beam search is not guaranteed to find the optimal solution whereas the Viterbi algorithm is. However, and assuming computing power isn't an issue, if we set the beam size to be equivalent to the output space, then wouldn't we also eventually find an optimal solution?


If we were to set the beam size to be equal to the number of possible states, wouldn't that mean the beam search algorithm is equivalent to the Viterbi algorithm?


Source: NLP Programming Tutorial 13 - Beam and A* Search by professor Graham Neubig
Then the reverse is the process of converting beam search into Viterbi.

if we set the beam size to be equivalent to the output space, then wouldn't we also eventually find an optimal solution?

The optimal path guarantee is due to the Generalized Distributive Law(or refer to this).
Because in Beam Search some unpromising parts of search space are pruned, and then we cannot apply the Generalized Distributive Law, and hence it can not guarantee an optimal path. Along the same line, if all the search space is considered the optimal path can be led to.
