我有一个问题,给定一个隐马尔可夫模型和状态 SI 需要找到一个算法,该算法在时间 O(|S|) 内返回通过隐马尔可夫模型的给定序列 X 的最可能路径。
我正在考虑开发一个图,其中我将在 X 的不同位置拥有所有不同的状态,并在该图上运行最短路径算法。但是我将有 n|S|^2 个边(其中 n 是 X 中的状态数)和 n|S| 顶点。
我发现的最佳算法是在时间 O(|E|+|V|) 中运行的非循环最短路径,在我的情况下为 O(|S|^2)。有没有我可以开发的算法让它在 O(|S|) 时间内运行?我需要的只是总体思路。
谢谢