维特比算法

动态规划

这是个递归问题 递归思想就是:把问题分解成规模更小,但和原问题有着相同解法的问题。 但是递归低效 递归:1-T的最优,依赖2-T最优,...依赖T-1到T的最优。但是T-1到T的最优是无法

HMM 示例

模型

最优路径 - 维特比算法

全局最优:line0 贪心算法会找到 line1

全连接 - 指数级

复杂度 ( N^T )

维特比算法

剪枝前,

维特比是少计算了?剪枝了?还是并未少计算,只是复用了前面的计算结果?