viterbi算法：利用动态规划寻找最短路径 - 简书
viterbi算法：利用动态规划寻找最短路径
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法，通常情况下应用于最优化问题，这类问题一般有很多个可行的解，每个解有一个值，而我们希望从中找到最优的答案。在计算机科学领域，应用动态规划的思想解决的最基本的一个问题就是：寻找有向无环图（篱笆网络）当中两个点之间的最短路径（实际应用于地图导航、语音识别、分词、机器翻译等等）。
下面举一个比较简单的例子做说明：求S到E的最短路径。如下图（各点之间距离不相同）：
我们知道，要找到S到E之间最短路径，最容易想到的方法就是穷举法。也就是把所有可能的路径都例举出来。从S走向A层共有4种走法，从A层走向B层又有4种走法，从B层走向C层又有4种走法，然后C层走向E点只有一种选择。所以最终我们穷举出了4X4X4=64种可能。显然，这种方法必定可行。但在实际的应用当中，对于数量极其庞大的结点数和边数的图，其计算复杂度也将会变得非常大，而计算效率也会随之降低。
因此，这里选择使用一种基于动态规划的方式来寻找最佳路径。所谓动态规划。其核心就是“动态”的概念，把大的问题细分为多个小的问题，基于每一步的结果再去寻找下一步的策略，通过每一步走过之后的局部最优去寻找全局最优。这样解释比较抽象，下面直接用回刚刚的例子说明。如下图：
首先，我们假设S到E之间存在一条最短路径（红色），且这条路径经过C2点，那么我们便一定能够确定从S到C2的64条（4X4X4=64）子路径当中，该子路径一定最短。（证明：反证法。如果S到C2之间存在一条更短的子路径，那么便可以用它来代替原先的路径，而原先的路径显然就不是最短了，这与原假设自相矛盾）。同理，我们也可以得出从S到B2点为两点间最短子路径的结论。这时候，真相便慢慢浮出水面：既然如此，我们计算从S点出发到点C2的最短路径，是不是只要考虑从S出发到B层所有节点的最短路径就可以了？答案是肯定的！因为，从S到E的“全局最短”路径必定经过在这些“局部最短”子路径。没错！这就是上面提及到的通过局部最优的最优去寻找全局最优，问题的规模被不断缩小！
接下来，要揭晓答案了！继续看下图：
回顾之前的分析：我们计算从S起到C2点的最短路径时候只需要考虑从S出发到B层所有节点的最短路径，B层也如是。对B2来说，一共有4条路线可以到达，分别是A1→B2，A2→B2，A3→B2，A4→B2。我们需要做的就是把A2→B2这条最短路线保留，而其他3条删除掉（因为根据以上的分析，它们不可能构成全程的最短路线）。OK，来到这里，我们会发现一个小“漏洞”，这段S→A2→B2→C2→E的路线只是我一厢情愿的假设，最短路径不一定是经过以上这些点。所以，我们要把每层的每个节点都考虑进来。
以下是具体的做法：step1：从点S出发。对于第一层的3个节点，算出它们的距离d（S,A1）,d（S,A2）,d（S,A3）,d（S,A4），因为只有一步，所以这些距离都是S到它们各自的最短距离。
step2：对于B层的所有节点（B1,B2,B3,B4），要计算出S到它们的最短距离。我们知道，对于特定的节点B2，从S到它的路径可以经过A层的任何一个节点（A1,A2,A3,A4）。对应的路径长就是d（S,B2）=d（S,Ai）+d（Ai,B2）（其中i=1,2,3,4）。由于A层有4个节点（即i有4个取值），我们要一一计算，然后找到最小值。这样，对于B层的每个节点，都需要进行4次运算，而B层有4个节点，所以共有4X4=16次运算。
step3：这一步是该算法的核心。我们从step2计算得出的结果只保留4个最短路径值（每个节点保留一个）。那么，若从B层走向C层来说，该步骤的基数已经不再是4X4，而是变成了4！也就是说，从B层到C层的最短路径只需要基于B层得出的4个结果来计算。这种方法一直持续到最后一个状态，每一步计算的复杂度为相邻两层的计算复杂度为4X4乘积的正比！再通俗点说，连接这两两相邻层的计算符合变成了“+”号，取代了原先的“X”号。用这种方法，只需进行4X4X2=32次计算！
其实上述的算法就是著名的维特比算法，事实上非常简单！若假设整个网格的宽度为D，网格长度为N，那么若使用穷举法整个最短路径的算法复杂度为O（D^N），而使用这种算法的计算复杂度为O（ND^2）。试想一下，若D与N都非常大，使用维特比算法的效率将会提高几个数量级！
代码实现（C语言版）：
同样是实现从S到E的最短路径。不过这次把刚刚的情况简化了一下，原理是相同的。
#include&stdlib.h&
#include&stdio.h&
#define x 9999
#define max 9999
int data[10][10];
int dist[10];//记录最短路径为多少
int path[10];//记录最短路径
int kmin(int,int);
void fpath(int a[][10]);
int froute(int a[][10]);
void main()
int a[10][10]=
{x,4,2,3,x,x,x,x,x,x},
{x,x,x,x,10,9,x,x,x,x},
{x,x,x,x,6,7,10,x,x,x},
{x,x,x,x,x,3,8,x,x,x},
{x,x,x,x,x,x,x,4,8,x},
{x,x,x,x,x,x,x,9,6,x},
{x,x,x,x,x,x,x,5,4,x},
{x,x,x,x,x,x,x,x,x,8},
{x,x,x,x,x,x,x,x,x,4},
{x,x,x,x,x,x,x,x,x,x}
/*for (i=0;i&10;i++)
for(j=0;j&10;j++)
printf("%d ",a[i][j]);
printf("\n");
printf("最短路径大小为: %d\n",dist[9]);
m=froute(a);
for(i=m-1;i&=0;i--)
printf("最短路径经过: %d\n",path[i]);
void fpath(int a[][10])
int i,j,k;42 dist[0]=0;
for(i=1;i&10;i++)
for(j=0;j&i;j++)
if(a[j][i]!=x)
if((dist[j]+a[j][i])&k)
k=dist[j]+a[j][i];
dist[i]=k;
int froute(int a[][10])
int j,b,k=1,i=9;
path[0]=10;
while(i&0)
for(j=i-1;j&=0;j--)
if(a[j][i]!=x)
b=dist[i]-a[j][i];
if(b==dist[j])
path[k++]=j+1;
一只热爱数据的新闻狗
专注于机器学习与数据可视化隐马尔可夫模型——Viterbi算法
参考博客：
先用一句话来简单描述一下：给出一个观测序列o1,o2,o3 …，我们希望找到观测序列背后的隐藏状态序列s1, s2, s3,
…；Viterbi以它的发明者名字命名，正是这样一种由动态规划的方法来寻找出现概率最大的隐藏状态序列（被称为Viterbi路径）的算法。
Markov随机过程具有如下的性质：在任意时刻，从当前状态转移到下一个状态的概率与当前状态之前的那些状态没有关系，即只与“现在”有关，而与“过去”无关。所以，我们可以用一个状态转移概率矩阵来描述它。假设我们有n个离散状态S1,
S2,…Sn，我们可以构造一个矩阵A，矩阵中的元素aij表示从当前状态Si下一时刻迁移到Sj状态的概率。
但是在很多情况下，Markov模型中的状态是我们观察不到的。例如，容器与彩球的模型：有若干个容器，每个容器中按已知比例放入各色的彩球（这样，选择了容器后，我们可以用概率来预测取出各种彩球的可能性）；我们做这样的实验，实验者从容器中取彩球——先选择一个容器，再从中抓出某一个球，只给观察者看球的颜色；这样，每次取取出的球的颜色是可以观测到的，即o1,
o2,…，但是每次选择哪个容器是不暴露给观察者的，容器的序列就组成了隐藏状态序列S1,
S2,…Sn。这是一个典型的可以用HMM描述的实验。
HMM有几个重要的任务，其中之一就是期望通过观察序列来猜测背后最有可能的隐藏序列。在上面的例子中，就是找到我们在实验中最有可能选择到的容器序列。Viterbi正是用来解决这个问题的算法。HMM另外两个任务是：a)
给定一个HMM，计算一个观测序列出现的可能性；b)已知一个观测序列，HMM参数不定，如何优化这些参数使得观测序列的出现概率最大。解决前一个问题可以用与Viberbi结构非常类似的Forward算法来解决（实际上在下面合二为一），而后者可以用Baum-Welch/EM算法来迭代逼近。
用一个例子来说明Viterbi算法。
假设你有一个朋友在外地，每天你可以通过电话来了解他每天的活动。他每天只会做三种活动之一——Walk, Shop,
Clean。你的朋友从事哪一种活动的概率与当地的气候有关，这里，我们只考虑两种天气——Rainy,
Sunny。我们知道，天气与运动的关系如下：
P(o|state)
例如，在下雨天出去散步的可能性是0.1。
而天气之前互相转换的关系如下，（从行到列）
p(state—&next_state)
例如，从今天是晴天而明天就开始下雨的可能性是0.4 。
同时为了求解问题我们假设初始情况：通话开始的第一天的天气有0.6的概率是Rainy，有0.4概率是Sunny。OK，现在的问题是，如果连续三天，你发现你的朋友的活动是：Walk-&Shop-&Clean(观测序列)；那么，如何判断你朋友那里这几天的天气(隐藏状态序列)是怎样的？
解决这个问题的python伪代码如下：
def forward_viterbi(y, X, sp, tp, ep):
for state in X:
## prob. V. path V. prob.
T[state] = (sp[state], [state], sp[state])
for output in y:
for next_state in X:
&&& total =
&&& argmax =
&&& valmax =
source_state in X:
(prob, v_path, v_prob) = T[source_state]
p = ep[source_state][output] * tp[source_state][next_state]
v_prob *= p
total += prob
if v_prob & valmax:
&&&&&&&&&&&
argmax = v_path + [next_state]
&&&&&&&&&&&
valmax = v_prob
U[next_state] = (total, argmax, valmax)
## apply sum/max to the final states:
argmax = None
valmax = 0
for state in X:
(prob, v_path, v_prob) = T[state]
total += prob
if v_prob & valmax:
&&& argmax =
&&& valmax =
return (total, argmax, valmax)几点说明：
算法对于每一个状态要记录一个三元组：(prob, v_path,
v_prob)，其中，prob是从开始状态到当前状态所有路径（不仅仅
是最有可能的viterbi路径）的概率加在一起的结果（作为算法附产品，它可以输出一个观察序列在给定HMM下总的出现概率，即forward算法的输出），v_path是从开始状态一直到当前状态的viterbi路径，v_prob则是该路径的概率。
算法开始，初始化T （T是一个Map，将每一种可能状态映射到上面所说的三元组上）
三重循环，对每个一活动y，考虑下一步每一个可能的状态next_state，并重新计算若从T中的当前状态state跃迁到next_state概率会有怎样的变化。跃迁主要考虑天气转移（tp[source_state][next_state]）与该天气下从事某种活动（ep[source_state][output]）的联合概率。所有下一步状态考虑完后，要从T中找出最优的选择viterbi路径——即概率最大的viterbi路径，即上面更新Map
U的代码U[next_state] = (total, argmax, valmax)。
算法最后还要对T中的各种情况总结，对total求和，选择其中一条作为最优的viterbi路径。
算法输出四个天气状态，这是因为，计算第三天的概率时，要考虑天气转变到下一天的情况。
通过程序的输出可以帮助理解这一过程：{p=p(observation|state)*p(state—&next_state)}
observation=Walk
next_state=Sunny
state=Sunny
triple=(0.144,Sunny-&,0.144)
state=Rainy
triple=(0.018,Rainy-&,0.018)
U[Sunny]=(0.162,Sunny-&Sunny-&,0.144)
next_state=Rainy
state=Sunny
triple=(0.096,Sunny-&,0.096)
state=Rainy
triple=(0.042,Rainy-&,0.042)
U[Rainy]=(0.138,Sunny-&Rainy-&,0.096)
observation=Shop
next_state=Sunny
state=Sunny
triple=(0.02916,Sunny-&Sunny-&,0.02592)
state=Rainy
triple=(0.01656,Sunny-&Rainy-&,0.01152)
U[Sunny]=(0.04572,Sunny-&Sunny-&Sunny-&,0.02592)
next_state=Rainy
state=Sunny
triple=(0.01944,Sunny-&Sunny-&,0.01728)
state=Rainy
triple=(0.03864,Sunny-&Rainy-&,0.02688)
U[Rainy]=(0.05808,Sunny-&Rainy-&Rainy-&,0.02688)
observation=Clean
next_state=Sunny
state=Sunny
triple=(0.0027432,Sunny-&Sunny-&Sunny-&,0.0015552)
state=Rainy
triple=(0.008712,Sunny-&Rainy-&Rainy-&,0.004032)
U[Sunny]=(0.0114552,Sunny-&Rainy-&Rainy-&Sunny-&,0.004032)
next_state=Rainy
state=Sunny
triple=(0.0018288,Sunny-&Sunny-&Sunny-&,0.0010368)
state=Rainy
triple=(0.020328,Sunny-&Rainy-&Rainy-&,0.009408)
U[Rainy]=(0.0221568,Sunny-&Rainy-&Rainy-&Rainy-&,0.009408)
triple=(0.033612,Sunny-&Rainy-&Rainy-&Rainy-&,0.009408)所以，最终的结果是，朋友那边这几天最可能的天气情况是Sunny-&Rainy-&Rainy-&Rainy，它有0.009408的概率出现。而我们算法的另一个附带的结论是，我们所观察到的朋友这几天的活动序列：Walk-&Shop-&Clean在我们的隐马可夫模型之下出现的总概率是0.033612。
附：c++主要代码片断
void forward_viterbi(const
vector&string& & ob,
viterbi_triple_t & vtriple)
map&string,
double&& sp =
map&string, map&string,
double& & & tp =
transition_
map&string, map&string,
double& & & ep =
// initialization
InitParameters();
map&string, viterbi_triple_t&
for (vector&string&::iterator it
= states.begin();
it != states.end();
viterbi_triple_
foo.prob = sp[*it];
foo.vpath.push_back(*it);
foo.vprob = sp[*it];
map&string, viterbi_triple_t&
double total = 0;
vector&string&
double valmax = 0;
double p = 0;
(vector&string&::const_iterator itob
= ob.begin(); itob != ob.end(); ++itob)
cout && “observation=”
U.clear();
for (vector&string&::iterator
itNextState = states.begin();
itNextState != states.end();
++itNextState)
cout && “\tnext_state=”
&& *itNextState
total = 0;
argmax.clear();
valmax = 0;
for (vector&string&::iterator
itSrcState = states.begin();
itSrcState != states.end();
++itSrcState)
cout && “\t\tstate=”
&& *itSrcState
viterbi_triple_t foo = T[*itSrcState];
p = ep[*itSrcState][*itob] *
tp[*itSrcState][*itNextState];
cout && “\t\t\tp=”
foo.prob *=
foo.vprob *=
cout && “\t\t\ttriple=”
total += foo.
if (foo.vprob & valmax)
foo.vpath.push_back(*itNextState);
argmax = foo.
valmax = foo.
U[*itNextState] = viterbi_triple_t(total, argmax,
cout && “\tUpdate U["
&& *itNextState
&& U[*itNextState]
T.swap(U);
total = 0;
argmax.clear();
valmax = 0;
for (vector&string&::iterator
itState = states.begin();
itState != states.end();
++itState)
viterbi_triple_t foo = T[*itState];
total += foo.
if (foo.vprob & valmax)
argmax.swap(foo.vpath);
valmax = foo.
vtriple.prob =
vtriple.vpath =
vtriple.vprob =
cout && “final triple=”
&& vtriple
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。谁能通俗的讲解下viterbi算法？ - 知乎494被浏览67241分享邀请回答/qqiang00/Machine-Learning-Samples/blob/master/mynltk/cn_viterbi.py 。这里展示一下优化的显示结果以 观测结果为：正常 发冷 发晕 为例，显示为：可以自己下载代码尝试不同的观测序列得到的结果是什么，也可以修改各种初始概率值尝试不同的情况。有一个问题值得思考：以最后的观测对应的最大概率往上追溯的最优路径所经过的状态是否总是在每次观测上具有最大概率的状态？===================== 完整代码 ====================='''
这是一个应用在动态规划领域的维特比算法及一个例子。具体网址可见：
https://zh.wikipedia.org/wiki/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95
本代码对原网址的代码进行了适当修改，主要目的是为了更好的显示运算逻辑及结果，其原理与原作完全一致
test函数提供您多次输入observation给出status的示例
修改者：叶强
修改日期：
import math
# 状态的样本空间
states = ('健康', '发热')
# 观测的样本空间
observations = ('正常', '发冷', '发晕')
# 起始个状态概率
start_probability = {'健康': 0.6, '发热': 0.4}
# 状态转移概率
transition_probability = {
'健康': {'健康': 0.7, '发热': 0.3},
'发热': {'健康': 0.4, '发热': 0.6},
# 状态-&观测的发散概率
emission_probability = {
'健康': {'正常': 0.5, '发冷': 0.4, '发晕': 0.1},
'发热': {'正常': 0.1, '发冷': 0.3, '发晕': 0.6},
# 计算以E为底的幂
#return math.pow(math.e,x)
def display_result(observations,result_m):
较为友好清晰的显示结果
:param result_m:
# 从结果中找出最佳路径
infered_states = []
final = len(result_m) - 1
(p, pre_state), final_state = max(zip(result_m[final].values(), result_m[final].keys()))
infered_states.insert(0, final_state)
infered_states.insert(0, pre_state)
for t in range(final - 1, 0, -1):
_, pre_state = result_m[t][pre_state]
infered_states.insert(0, pre_state)
print(format("Viterbi Result", "=^59s"))
head = format("obs", " ^10s")
head += format("Infered state", " ^18s")
for s in states:
head += format(s, " ^15s")
print(head)
print(format("", "-^59s"))
for obs,result,infered_state in zip(observations,result_m,infered_states):
item = format(obs," ^10s")
item += format(infered_state," ^18s")
for s in states:
item += format(result[s][0]," &12.8f")
if infered_state == s:
item += "(*)"
print(item)
print(format("", "=^59s"))
def viterbi(obs, states, start_p, trans_p, emit_p):
result_m = [{}] # 存放结果,每一个元素是一个字典，每一个字典的形式是 state:(p,pre_state)
# 其中state,p分别是当前状态下的概率值，pre_state表示该值由上一次的那个状态计算得到
for s in states:
# 对于每一个状态
result_m[0][s] = (E(start_p[s]*emit_p[s][obs[0]]),None) # 把第一个观测节点对应的各状态值计算出来
for t in range(1,len(obs)):
result_m.append({})
# 准备t时刻的结果存放字典，形式同上
for s in states: # 对于每一个t时刻状态s,获取t-1时刻每个状态s0的p,结合由s0转化为s的转移概率和s状态至obs的发散概率
# 计算t时刻s状态的最大概率，并记录该概率的来源状态s0
# max()内部比较的是一个tuple:(p,s0),max比较tuple内的第一个元素值
result_m[t][s] = max([(E(result_m[t-1][s0][0]*trans_p[s0][s]*emit_p[s][obs[t]]),s0) for s0 in states])
return result_m
# 所有结果（包括最佳路径）都在这里，但直观的最佳路径还需要依此结果单独生成，在显示的时候生成
def example():
一个可以交互的示例
result_m = viterbi(observations,
start_probability,
transition_probability,
emission_probability)
display_result(observations,result_m)
while True:
user_obs = input("轮到你来输入观测,计算机来推断可能状态\n"
"使用 'N' 代表'正常', 'C' 代表'发冷','D'代表'发晕'\n"
"您输入：('q'将退出):")
if len(user_obs) ==0 or 'q' in user_obs or 'Q' in user_obs:
for o in user_obs:
if o.upper() == 'N':
obs.append("正常")
elif o.upper() == 'C':
obs.append("发冷")
elif o.upper() == 'D':
obs.append("发晕")
result_m = viterbi(obs,
start_probability,
transition_probability,
emission_probability)
display_result(obs,result_m)
if __name__ == "__main__":
7添加评论分享收藏感谢收起PID控制算法通俗理解 - LOVE EE - 中国电子顶级开发网(EETOP)-电子设计论坛、博客、超人气的电子工程师资料分享平台
- Powered by X-Space
LEARN AND SHARE , TOGETHER ACHIEVE MORE !
PID控制算法通俗理解
& 13:20:39
/ 个人分类：
今天开始学PID电机控制，这个作者写得很不错，和大家分享一下～～～
PID控制算法通俗理解谁能通俗的讲解下viterbi算法？ - 知乎494被浏览67241分享邀请回答52 条评论分享收藏感谢收起