我们可以小心地解决这个问题。通过查看 hmm 的网格结构最容易看出：
在此示例中，隐藏状态为 00、01、10、11，将这四个状态的集合表示为 S。观察结果未显示，但假设它们为 0,1。
假设我们有正确的转移矩阵：
transition[4][4]
发射概率：
emissions[4][2]
和初始概率：
p[2]
因此，每一列都代表隐藏状态，维特比的目标是计算给定观察结果的最可能的隐藏状态序列。现在让 alpha(i, t) = 隐藏状态序列在时间 t 处于状态 i（i 是 00、01、10、11 之一）的最大概率，其中时间 t 的观测值是 o_t（o_t 是 1） 0, 1)。将第一个观察值表示为 o_1。它可以有效地计算为：
alpha(i, 1) = p[i] * emissions[i][o_1]
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i])
为了找到最佳路径，我们在 alpha(i, t) 步骤中保持指针向后，指向上面最大化 max 函数的状态。最后，我们只检查状态中的所有 alpha(i, T) 和 for i，并找到哪一个最大，然后跟踪它以获得最可能的状态序列。
现在我们需要扩展它来存储顶级 k 路径。目前，在每个 alpha(i,t) 中，我们仅存储一个父级。然而，假设我们存储了前 k 个前辈。因此，每个 alpha(i, t) 不仅对应于最可能的值及其转换的节点，还对应于它可能转换的前 k 个节点的列表及其按排序顺序排列的值。
这很容易做到，因为我们不是执行 max 操作，而是只取一个前面的节点，而是取前 k 个前面的节点并存储它们。现在，对于基本情况，没有前面的节点，因此 alpha(i, 1) 仍然只是一个值。当我们到达任意列（例如 t）并想要找到以该列中的节点 (i) 结束的前 k 条路径时，我们必须找到来自前 k 条前驱路径以及从它们出发的前 k 条路径。
这就好像我们有以下问题，一个大小为 4 x k 的矩阵 m，其中一行表示先前的状态，m[state] 表示结束于该位置的路径的前 k 个概率。这样m的每一行都按照从大到小排序，现在的问题就变成了find：
Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i])
现在这看起来令人畏惧，但需要一些时间来理解它，我们通常可以使用 O(4 log k) 或 O(numStates log k) 的堆来解决排序矩阵问题中的 top k。
看看这个细微的变化排序矩阵中第 K 个最小元素 https://stackoverflow.com/questions/15179536/kth-smallest-element-in-sorted-matrix，请注意，在我们的例子中，列没有排序，但其中的想法仍然适用。
如果您仍在阅读，请注意此方法的总体复杂度为 O((numStates log k) * numStates * t) = O(numStates^2 * t * log k) （我相信这是正确的复杂度）。
这可能很难理解，但如果您有任何疑问，或者我做错了什么，请告诉我。
