（译码算法）我们可以在有向图G=(V,E)上使用动态规划方法来实现语音识别。对每条边（u,v）
E打上一个声音标签)
，该声音来自于有限声音集
。这样的标签图就成为一个特定人说限定语言的形式化模型。图中从特定顶点
开始的每条路径都对应模型产生一个可能的声音序列。对于一条有向路径，我们定义其标签为路径中边的标签的简单连接。
a.设计高效算法，对给定的带边标签的图G，给定顶点v0及上的声音序列s=<
>，返回G中从v0开始的一条路径，s为该路径的标签（如果存在这样的路径）。否则，算法应返回NO-SUCH-PATH。分析算法的时间复杂度。
现在假定每条边（u,v）E都关联一个非负概率p(u,v)，它表示从顶点u开始，经过边(u,v)产生对应的声音的概率。任何顶点的出射边的概率之和均为1。一条路径的概率定义为路径上边的概率之积。对于从v0开始的一条路径，我们可以将其概率看做从v0开始进行“随机游走”（random walk），最后恰巧经过这条路径的概率。所谓“随机游走”，是指当位于顶点u时，随机选择一条出射边前进，每条边被选中的概率就是它所关联的概率。
b.扩展（a）中的算法，使得返回的路径是从v0开始且标签为s的路径中概率最大者。分析算法的时间复杂性。
