之前提到HMM有三类问题，这里主要针对第二类问题：根据观测序列分析隐藏状态序列，算法主要是维特比算法。
比如还是以hmm中的天气和活动作为例子，现在我们观察到一系列活动，需要分析每个活动对应的天气，这时候，每个活动都对应着三种可能的天气，假设观测序列长度为n，那么天气状态序列就有3^n种可能性，我们就需要从中找出答案。
这类问题可以认为是最优路径问题，最简单的方法就是穷举法，把所有可能都计算一遍，看看谁最优，可是这样就要计算3^n次，明显不现实，另一方面也可以采取贪心算法，每次只选择最优的路径，也就是每次都选择活动对应概率最大的天气，虽然效果更好但是往往还是和真实情况有所不同，所以就有了beam search，每次只选择最好的前n条路径。
beam search和贪心算法的区别，一个是前n个最优一个是当前最优，举个例子，现在我们通过贪心算法，分析出第一个状态是雨天，对应的概率是0.6，第二个概率是0.5，那么这段序列发生的概率就是0.3，如果我们采用维特比算法，同时分析两个状态，可能发现第一个状态选择晴天（0.5），第二个选择晴天（0.7），得到的结果比贪心算法更优，主要的原因就是贪心算法只考虑当前最优而舍弃了其他可能性，没办法从整体上进行考虑，当然贪心算法的计算效率是非常好的。而beam search随着beam width（前n条路径的n）变大，计算复杂度也会变大，而beam width小了分析得到的模型又可能出问题，所以这个算法也并不是完美的。
最后就是这次要重点介绍的维特比算法，它的思路是从开始状态后的每一步，都记录下到该状态的所有路径的概率最大值，以此作为基准继续向后推进，这样说还是比较抽象，还是结合例子说明，比如现在有三个盒子装了红球白球，观测的是球的颜色，状态集合是盒子的号码：
$$Q = {box_1, box_2, box_3}$$
初始状态分布：
$$\prod = (0.2, 0.4, 0.4)^T$$
状态转移概率：
$$
\begin{matrix}
0.5 & 0.2 & 0.3 \\
0.3 & 0.5 & 0.2 \\
0.2 & 0.3 & 0.5 \\
\end{matrix}
$$
观测状态概率分布矩阵为：
$$
\begin{matrix}
0.5 & 0.5 \\
0.4 & 0.6 \\
0.7 & 0.3 \\
\end{matrix}
$$
观测序列为：
$$O = {red, white, white}$$
首先我们需要计算第一个时刻三个隐藏状态各自的概率：
$$\delta_1(1) = \pi_1 b_1(o_1) = 0.2*0.5 = 0.1$$
$$\delta_1(2) = \pi_2 b_2(o_1) = 0.4*0.4 = 0.16$$
$$\delta_1(3) = \pi_3 b_3(o_1) = 0.4*0.7 = 0.28$$
这里的意思就是根据初始概率以及每个箱子抽到红球的概率计算的，然后就是计算第二时刻的概率：
$$\delta_2(1) = max_{1\leq j\leq 3}[\delta_1(j)a_{j1}] b_1(o_2) = max[0.1*0.5, 0.16*0.3, 0.28*0.2]*0.5 = 0.028 $$
$$\delta_2(2) = max_{1\leq j\leq 3}[\delta_1(j)a_{j2}] b_2(o_2) = max[0.1*0.2, 0.16*0.5, 0.28*0.3]*0.5 = 0.0504 $$
$$\delta_2(3) = max_{1\leq j\leq 3}[\delta_1(j)a_{j3}] b_3(o_2) = max[0.1*0.3, 0.16*0.2, 0.28*0.5]*0.5 = 0.042 $$
上面的计算就是主要的迭代过程了，仔细看一下，简单来说就是根究上一个时刻计算出来的各个状态的概率，再乘以转移概率，记得该时刻下各个状态的最大概率，这样一致计算下去，最终就可以得到结果。