== Описание ==
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели ]] на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.
{{Определение
|id=def1.
Пусть задано пространство наблюдений <tex>O =\{o_1,o_2...o_N\}</tex>, пространство состояний <tex>S =\{s_1,s_2...s_K\}</tex>, последовательность наблюдений <tex>Y =\{y_1,y_2...y_T\}</tex>, матрица <tex>A</tex> переходов из <tex>i</tex>-того состояния в <tex>j</tex>-ое, размером <tex>K \times K</tex>, матрица эмиссии <tex> B </tex> размера <tex>K \times N</tex>, которая определяет вероятность наблюдения <tex>o_j</tex> из состояния <tex>s_i</tex>, массив начальных вероятностей <tex>\pi</tex> размером <tex>K</tex>, показывающий вероятность того, что начальное состояние <tex>s_i</tex>. Путь <tex>X =\{x_1,x_2...x_T\}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>Y</tex>.
'''Скрытая марковская модель.'''
Модель представляет из себя марковскую цепь, для которой нам известны начальная вероятность и матрица вероятностей переходов. Скрытой она называется потому, что мы не имеем информации о ее текущем состоянии. Мы получаем информацию на основе некоторого наблюдения, в рассмотренном ниже алгоритме мы будем использовать просто натуральное число от 1 до <tex>N</tex>, как индекс наблюдаемого события. Для каждого состояния скрытой марковской модели задан вектор вероятности эмиссии, который характеризует вероятность наблюдени каждого события, когда модель находится в этом состоянии. Совокупность таких векторов образует матрицу эмиссии.
'''Пример скрытой марковской модели.'''
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз пробирается в квартиру и тайком выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.
Дед Мороз с мешками {{---}} скрытая марковская модель. При этом 4 цвета {{---}} пространство из <tex>N</tex> наблюдений, 3 мешка {{---}} количество состояний <tex>K</tex>, 5 подарков {{---}} наши <tex>T</tex> наблюдений, каждое из которых представлено цифрой {{---}} номером цвета {{---}} от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером <tex>i</tex> {{---}} вектор <tex>\pi[i]</tex>. Мы также знаем матрицу переходов <tex>A</tex>, какова вероятность того, что от мешка с номером <tex>i</tex> Дед Мороз переходит к мешку с номером <tex>j</tex>. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в каждом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии <tex>B</tex>.
== Алгоритм ==
