# 第 26 章 维特比和他的维特比算法

维特比算法是一个特殊的但应用最广泛的动态规划算法，**维特比算法主要解决篱笆网络的有向图的最短路径问题**。它之所以重要，是因为**凡是使用隐含马尔可夫模型描述的问题都可以用它来解码**。

## 维特比算法

假设在隐含马尔可夫链中，总共有![N](https://www.zhihu.com/equation?tex=N)个节点，节点最多的状态有![D](https://www.zhihu.com/equation?tex=D)个节点，也就是整个网格的宽度为![D](https://www.zhihu.com/equation?tex=D)，那么找出任何相邻两个状态节点的最短路径的复杂度不超过 ![D^2](https://www.zhihu.com/equation?tex=D%5E2)。由于网格的长度是![N](https://www.zhihu.com/equation?tex=N)，所以整个维特比的复杂度是![O\left( N\cdot D^2 \right) ](https://www.zhihu.com/equation?tex=O%5Cleft\(%20N%5Ccdot%20D%5E2%20%5Cright\)%20)。

### 题目背景

从前有个村儿，村里的人的身体情况只有两种可能：健康或者发烧。\
唯一判断他身体情况的途径就是到村头李飞飞的小诊所询问。\
飞飞通过询问村民的感觉，判断她的病情，再假设村民只会回答正常、头晕或冷。\
有一天村里吴恩达就去飞飞那去询问了。\
第一天他告诉飞飞他感觉正常。\
第二天他告诉飞飞感觉有点冷。\
第三天他告诉飞飞感觉有点头晕。\
那么问题来了，飞飞如何根据阿达的描述的情况，推断出这三天中阿达的一个身体状态呢?\
为此飞飞上百度搜 google ，一番狂搜，发现维特比算法正好能解决这个问题。飞飞乐了。

### 已知情况

隐含的身体状态 = { 健康 , 发烧 }

可观察的感觉状态 = { 正常 , 冷 , 头晕 }

飞飞预判的阿达身体状态的概率分布 = { 健康：0.6 , 发烧： 0.4 }

 **这就是初始状态序列。**

飞飞认为的阿达身体健康状态的转换概率分布 = {\
        健康 -> 健康： 0.7 ,\
        健康 -> 发烧： 0.3 ,\
        发烧 -> 健康： 0.4 ,\
        发烧 -> 发烧： 0.6\
}

**这样就可以列出相应的状态转移矩阵。**

飞飞认为的在相应健康状况条件下，阿达的感觉的概率分布 = {\
        (健康，正常)：0.5 ，(健康，冷)：0.4 ，(健康，头晕)：0.1 ,\
        (发烧，正常)：0.1 ，(发烧，冷)：0.3 ，(发烧，头晕)：0.6 \
}

**这样就可以列出相应的观测矩阵。**

由上面我们可以发现，HMM的三要素都齐备了，下面就是解决问题了。

阿达连续三天的身体感觉依次是： 正常、冷、头晕 。

### 题目

已知如上，求：阿达这三天的身体健康状态变化的过程是怎么样的？**即已知观测序列和HMM模型的情况下，求状态序列。**

### 过程

#### 初始化

$$
P(健康) = 0.6；P(发烧)=0.4
$$

#### 第一天

第一天的时候，对每一个状态（健康或者发烧），分别求出第一天身体感觉正常的概率：

P(第一天健康) = P(正常|健康)\*P(健康|初始情况) = 0.5 \* 0.6 = **0.3** 

P(第一天发烧) = P(正常|发烧)\*P(发烧|初始情况) = 0.1 \* 0.4 = **0.04**

#### 第二天

计算在阿达感觉冷的情况下最可能的身体状态。那么第二天有四种情况，由于第一天的发烧或者健康转换到第二天的发烧或者健康。

* P(前一天发烧，今天发烧) = P(前一天发烧)\*P(发烧->发烧)\*P(冷|发烧) = 0.04 \* 0.6 \* 0.3 = 0.0072
* P(前一天发烧，今天健康) = P(前一天发烧)\*P(发烧->健康)\*P(冷|健康) = 0.04 \* 0.4 \* 0.4 = 0.0064
* P(前一天健康，今天健康) = P(前一天健康)\*P(健康->健康)\*P(冷|健康) = 0.3 \* 0.7 \* 0.4 = **0.084**
* P(前一天健康，今天发烧) = P(前一天健康)\*P(健康->发烧)\*P(冷|发烧) = 0.3 \* 0.3 \*.03 = **0.027**

第二天的时候，对每个状态，分别求在第一天状态为健康或者发烧情况下观察到冷的最大概率。在维特比算法中，我们先要求得路径的单个路径的最大概率，然后再乘上观测概率。P(第二天健康) = max{0.3\*0.7, 0.04\*0.4}\*0.4=0.3\*0.7\*0.4 = 0.084 

此时我们需要记录概率最大的**路径的前一个状态**，即 0.084 路径的前一个状态，我们在小本本上记下，第一天健康。 P(第二天发烧)=max{0.3\*0.3, 0.04\*0.6}\*0.3 = 0.027 , 同样的在 0.027 这个路径上，第一天也是健康的。

#### 第三天

计算在阿达感觉头晕的情况下最可能的身体状态。

* P(前一天发烧，今天发烧) = P(前一天发烧)\*P(发烧->发烧)\*P(头晕|发烧) = 0.027 \* 0.6 \* 0.6 = 0.00972
* P(前一天发烧，今天健康) = P(前一天发烧)\*P(发烧->健康)\*P(头晕|健康) = 0.027 \* 0.4 \* 0.1 = 0.00108
* P(前一天健康，今天健康) = P(前一天健康)\*P(健康->健康)\*P(头晕|健康) = 0.084 \* 0.7 \* 0.1 = 0.00588
* P(前一天健康，今天发烧) = P(前一天健康)\*P(健康->发烧)\*P(头晕|发烧) = 0.084 \* 0.3 \*0.6 = **0.01512**

第三天的时候，跟第二天一样。P(第三天健康)=max{0.084\*0.7, 0.027\*0.4}\*0.1 = 0.00588，在这条路径上，第二天是健康的。P(第三天发烧)=max{0.084\*0.3, 0.027\*0.6}\*0.6 = 0.01512，在这条路径上，第二天是健康的。

最后一天的状态概率分布即为最优路径的概率，即P(最优)=0.01512，这样我们可以得到最优路径的终点，是发烧。

#### **回溯**

请看我们的小本本，在求得第三天发烧概率的时候，我们的小本本上面写的是第二天健康，好了，第二天就应该是健康的状态，然后在第二天健康的情况下，我们记录的第一天是健康的。这样，我们的状态序列逆推出来了。即为：**健康，健康，发烧**。

![](/files/-LG5Yg_OGsq9SOfHqgCN)

这儿的箭头指向就是一个回溯查询小本本的过程，我们在编写算法的时候，其实也得注意，每一个概率最大的**单条路径**上都要把前一个状态记录下来。

## 小结

在维特比算法中，对于每一个给定的起始点、终止点，如果列出所有可能的路径，从中找出最短路径，计算复杂度呈指数增长。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chenjunren.gitbook.io/read-the-beauty-of-mathematics/di-26-zhang-wei-te-bi-he-ta-de-wei-te-bi-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.