維特比演算法：籬笆網格上的 DP#

很多問題的輸入不是一個靜態結構，而是一連串隨時間到來的觀測 (observation)：一段語音訊號、一串打字的拼音、一句待分析的句子。我們真正想要的，往往不是這些觀測本身，而是藏在它們背後、看不見的狀態序列 (state sequence)。維特比演算法 (Viterbi algorithm) 就是專門用來「從觀測倒推最可能狀態序列」的 DP 利器。

問題情境：從觀測推狀態#

考慮這幾個典型場景：

這些問題有共同的骨架：時間軸上有 $L$ 個位置，每個位置都觀測到一個東西，而每個位置背後的「真實狀態」有 $D$ 種可能。我們要在所有位置上，一次推出整條最可能的狀態序列。

關鍵字是「序列」。我們要的不是「每個位置各自最可能的狀態」，而是「整條路徑加起來最可能」。這兩者並不等價——某個位置單看最可能的狀態，放進整條序列裡未必最優，因為相鄰狀態之間還有「轉移」的可能性差異（例如「動詞後面接名詞」比「動詞後面接動詞」更常見）。

籬笆網格與暴力解的爆炸#

把問題畫出來，結構會立刻清晰。我們把每個時間點的所有可能狀態畫成一欄，時間軸從左到右展開，相鄰兩欄之間用線連起所有可能的轉移。這張圖叫做籬笆網格 (trellis)——一條從最左貫穿到最右的完整路徑，恰好對應一個狀態序列。

flowchart LR
    subgraph t1["t=1"]
        A1((狀態A))
        B1((狀態B))
        C1((狀態C))
    end
    subgraph t2["t=2"]
        A2((狀態A))
        B2((狀態B))
        C2((狀態C))
    end
    subgraph t3["t=3"]
        A3((狀態A))
        B3((狀態B))
        C3((狀態C))
    end
    A1 --> A2 & B2 & C2
    B1 --> A2 & B2 & C2
    C1 --> A2 & B2 & C2
    A2 --> A3 & B3 & C3
    B2 --> A3 & B3 & C3
    C2 --> A3 & B3 & C3

每一欄有 $D$ 個狀態，每一個狀態都能連到下一欄的 $D$ 個狀態。所以一條完整路徑要在 $L$ 欄各挑一個狀態，總共有：

$$ \underbrace{D \times D \times \cdots \times D}_{L \text{ 欄}} = D^L $$

條路徑。如果語音解碼有 $D = 1000$ 個候選字、句子長 $L = 20$，那就是 $1000^{20}$ 條——把每條路徑的分數都算一遍再取最大，是徹底的指數爆炸，不可行。

維特比：用 DP 在網格上找最佳路徑#

暴力解的浪費在哪裡？它把「到達某個狀態的所有歷史」當成各自獨立的路徑，重複計算了大量共用的前綴。維特比的突破來自一個觀察：

無後效性（馬可夫性）：到達第 $t$ 欄某個狀態 $s$ 的「最佳路徑分數」，只取決於「上一欄各狀態各自的最佳分數」加上「轉移到 $s$ 的代價」，與更早之前到底是怎麼一路走來的完全無關。

換句話說：一旦我知道「到上一欄每個狀態為止的最佳分數」，當前這一欄就能算出來，前面的細節可以全部丟掉。

這正是 DP 三要素裡的無後效性——子問題的依賴是單向的，當前狀態確定後不受後續決策影響。有了它，我們就能逐欄遞推，每一欄只保留 $D$ 個數字：「到此欄每個狀態為止的最佳路徑分數」。

設 $V_t(s)$ 為「到第 $t$ 欄、停在狀態 $s$ 的最佳路徑分數」，$\text{score}(s’ \to s, t)$ 為「上一欄狀態 $s’$ 轉移到本欄狀態 $s$、並對上第 $t$ 個觀測」的分數，則遞推式為：

$$ V_t(s) = \max_{s’} \Big[, V_{t-1}(s’) + \text{score}(s’ \to s,, t) ,\Big] $$

邊界為第一欄 $V_1(s) = \text{init}(s)$。每填一格 $V_t(s)$，順手記下「是從上一欄哪個 $s’$ 轉移過來的」（backpointer）。全部填完後，從最後一欄分數最高的狀態，沿著 backpointer 往回走，就還原出整條最佳序列。

// init[s]:      第一欄各狀態的起始分數
// score[t][sPrev][s]: 第 t 欄由 sPrev 轉移到 s（並對上第 t 個觀測）的分數
// 回傳分數最高的整條狀態序列（各欄的狀態索引）
fun viterbi(init: DoubleArray, score: Array<Array<DoubleArray>>): IntArray {
    val L = score.size + 1          // 欄數
    val D = init.size               // 每欄狀態數

    val v = Array(L) { DoubleArray(D) { Double.NEGATIVE_INFINITY } }
    val back = Array(L) { IntArray(D) { -1 } }
    v[0] = init.copyOf()            // 邊界：第一欄

    for (t in 1 until L) {
        for (s in 0 until D) {
            for (sPrev in 0 until D) {
                val cand = v[t - 1][sPrev] + score[t - 1][sPrev][s]
                if (cand > v[t][s]) {
                    v[t][s] = cand
                    back[t][s] = sPrev   // 記下從哪個狀態轉移而來
                }
            }
        }
    }

    // 從最後一欄分數最高的狀態，沿 backpointer 往回還原路徑
    var best = (0 until D).maxByOrNull { v[L - 1][it] }!!
    val path = IntArray(L)
    for (t in L - 1 downTo 0) {
        path[t] = best
        if (t > 0) best = back[t][best]
    }
    return path
}

複雜度怎麼算？網格有 $L \times D$ 格，每一格要在上一欄的 $D$ 個狀態裡取 max，所以是：

$$ O(L \cdot D^2) $$

從 $D^L$ 降到 $O(L \cdot D^2)$——指數變多項式。

換個角度看，這其實就是最短路徑問題的特例：把籬笆網格當成一張有向圖（節點是「欄 × 狀態」，邊權是轉移分數），維特比就是在這張分層的 DAG 上找一條最佳路徑。因為圖是按欄分層、邊只往右走，所以連 Dijkstra 的優先佇列都不需要，逐欄掃過去即可。

flowchart LR
    A[暴力枚舉 D^L 條路徑] --> B{每條路徑的前綴<br/>是否被重複計算？}
    B -->|是| C[只保留<br/>到每狀態為止的最佳分數]
    C --> D[逐欄遞推<br/>O of L·D²]
    style A fill:#ffebee
    style D fill:#e8f5e9

當網格還是太大：Beam Search 與置信度剪枝#

$O(L \cdot D^2)$ 已經很漂亮，但當狀態數 $D$ 非常大時（語音解碼動輒上萬個候選），每欄 $D^2$ 仍嫌沉重。這時可以再退一步：每一欄只保留分數最高的 $m$ 個狀態，其餘直接砍掉，不再往下擴展。這就是 Beam Search，$m$ 稱為 beam width（束寬）。

這樣一來，每欄只從 $m$ 個倖存狀態出發、擴展到 $D$ 個候選，複雜度降到：

$$ O(m \cdot D \cdot L) $$

代價是：被砍掉的狀態，理論上仍有可能是最優路徑的一環，所以 Beam Search 不保證最優。但實務上，真正的最佳路徑幾乎總是落在每一欄分數靠前的那一小撮狀態裡，因此在恰當的 $m$ 下，能以很高的置信度保住接近最優的解。這正是 剪枝技術的思路在序列 DP 上的體現——根據分數的「置信度」提早裁掉沒希望的分支。

這裡藏著一個重要的工程哲學：維特比在「精確最優」這個目標上已經是理論最優了（你不可能在更低的漸進複雜度下保證找到最佳序列），但這不代表優化到此為止。當問題規模大到連最優演算法都嫌慢時，仍可針對「實務上絕大多數情況」的特性，用一點點置信度去換取數量級的速度——從「保證最優」放寬到「以高機率接近最優」，往往是把演算法真正落地的關鍵一步。

小結#

維特比的核心，是把「在指數多條序列裡找最佳」這件事，靠無後效性壓縮成「逐欄保留每狀態最佳分數」的 DP。看懂了籬笆網格，你會發現它和最短路徑、和 DP 三要素講的是同一件事——這也再次印證：能把陌生問題翻譯成熟悉模型，正是演算法能力的最高層次。