0

我有一个问题,给定一个隐马尔可夫模型和状态 SI 需要找到一个算法,该算法在时间 O(|S|) 内返回通过隐马尔可夫模型的给定序列 X 的最可能路径。

我正在考虑开发一个图,其中我将在 X 的不同位置拥有所有不同的状态,并在该图上运行最短路径算法。但是我将有 n|S|^2 个边(其中 n 是 X 中的状态数)和 n|S| 顶点。

我发现的最佳算法是在时间 O(|E|+|V|) 中运行的非循环最短路径,在我的情况下为 O(|S|^2)。有没有我可以开发的算法让它在 O(|S|) 时间内运行?我需要的只是总体思路。

谢谢

4

1 回答 1

1

我认为,如果您想检索最有可能的确切序列,则无法在所有实例上以线性时间进行。但是,如果您的符号空间是离散的,则平均情况时间复杂度可能会降低。看看 Ukkonen 计算编辑距离的优化及其推广。还要看看基于压缩的技术,这也是基于 Ukkonen 的工作。

于 2010-10-31T01:10:04.947 回答