维特比算法小解

我理解

维特比算法可以算作一种优化技术，正是这些类优化技术的应用，加上算力的提升及数据量and分析方法的更新，构成了大数据&机器学习的核心。

所以，理解这类优化技术对于技术学习应当是很有必要的。

之前，读到这个算法的时候，对它的理解是是而非。
所以觉得有必要进行一下梳理及通俗理解，以便加强理解&灵活运用。

梳理

梳理之后的总结便是：

以层为中心，去筛选线(路径)
而不是以路径为中心，去筛选线(路径)

解释

解释一下就是：以层为中心，逐层筛选(V)；
而另外一种方法就是穷举遍历法(E)。
作两张图说明一下：

从上图寻找最优路径需要比较的次数是：

• E方法：$1*2*2*3=12$
• V方法：$0+1*2+2*2+2*3+3*0=12$

看起来两种方法的结果好像一样？
再看一图：

从上图寻找最优路径需要比较的次数是：

• E方法：$1*2*2*3*4*5=360$
• V方法：$0+1*2+2*2+2*3+3*4+4*5+5*0=44$

“以层为中心逐层筛选”再通俗一点：每一层的每一次筛选，总能将当前的最短路径定位到该层的某一点。然后下一次计算时，将只考虑：锁定的那一点*下一层数目*下下层数目，即:1*(n+1)*(n+2)，迭代之。

总结

算法的力量一目了然。显然真正的使用场景可能远比图二所示复杂，所以算法带来的提升将是若干几何级的。