我有一个配置文件隐藏马尔可夫模型，我用它来识别一长串符号中用户定义的符号模式的所有实例。我使用维特比算法来找到生成长符号序列的最可能路径，并且这一切都很好地识别了用户的模式。但我现在有兴趣扩展它，并通过我的模型确定 k 最可能的路径，这些路径会生成一些长序列。是否有现有的算法可以做到这一点？我遇到了一种叫做“1-best”或“k-best”算法的东西，但我找不到任何描述它的东西。

我还考虑了我确定的启发式方法，即找到最可能的路径，然后返回它周围的邻域。这可以通过迭代最可能路径中状态之间的每个移动、将该特定步骤设置为 0 并使用 Viterbi 解决来找到。这显然会使运行时间增加（路径长度〜=模式长度）的一个因素，我怀疑这对我的目的来说是合理的。

有没有人遇到过这样的事情，或者有人能看出我的邻居想法有什么明显的错误吗？我会很感激任何反馈。作为说明，这已被交叉发布到理论计算机科学论坛。