狀態抽象與狀態圖 (State Abstraction)#

很多看起來千奇百怪的難題，剝開外殼後其實是同一件事：把問題拆成一組「狀態」，在狀態之間找出依賴或轉移關係，這些關係把狀態連成一張圖，剩下的就交給圖論工具去解。這一節談的就是這套幾乎萬用的方法論。

核心方法論：先有狀態，後有圖#

解決複雜問題的本質，往往是三步：

1. 抽象出狀態——找出能完整描述「當前局面」的最小資訊，每一種局面就是一個狀態（節點）。
2. 連出轉移——在「一步可達」或「彼此依賴」的狀態之間連邊，整組狀態就成了一張圖。
3. 套用圖論——問題於是退化成圖上的標準操作：能不能到達某狀態？（走訪）最少幾步？（最短路徑）有沒有環？（拓撲排序）

這套方法最大的威力來自抽象時的等價合併。現實中「不同」的具體情況可能多到天文數字，但只要它們對「往後怎麼走」沒有影響，就能被合併成同一個狀態。把指數級的具體情況壓成多項式級的狀態數，常常一口氣省下好幾個數量級。

抽象狀態的判準只有一句話：兩個局面若對未來的所有走法完全等效，它們就是同一個狀態。

抓住這條，你就知道哪些細節該丟、哪些該留。

這正是演算法思維總綱裡「把問題抽象成已知模型」的具體落實——一旦狀態圖成形，整套圖論工具立刻可用；而當狀態之間存在重疊的子結構時，它又自然接上動態規劃。

範例：益智題變狀態圖#

經典的「農夫過河」最能展示這套流程。農夫要把狼、羊、菜用一艘只能載一樣東西的小船運過河，但：狼和羊不能單獨同岸，羊和菜不能單獨同岸（農夫不在就會出事）。

第一步，定義狀態。 一個狀態就是「四樣東西各在哪一岸」。用 (農, 狼, 羊, 菜) 記錄，每個元素取「左 / 右」，總共 2⁴ = 16 種組合——這就是全部候選狀態。

第二步，濾掉非法狀態。 凡是「農夫不在、卻有狼羊同岸或羊菜同岸」的局面都不合法，直接刪除。剩下的才是合法狀態。

第三步，連邊。 兩個合法狀態之間，若能靠「農夫划一趟船（最多帶一樣東西）」互相轉換，就連一條邊。注意每次轉移農夫一定換岸。

第四步，變成圖論問題。 起點是全在左岸 (左,左,左,左)，終點是全在右岸 (右,右,右,右)。問題就變成：在這張圖上，從起點到終點的最短路徑——用 BFS 一掃即得最少渡河次數。

下圖擷取其中一條合法路徑（L 代表左岸、R 代表右岸，順序為農狼羊菜）：

flowchart LR
    S["LLLL<br/>(起點)"] -->|帶羊| A["RLRL"]
    A -->|農夫獨返| B["LLRL"]
    B -->|帶狼| C["RRRL"]
    C -->|帶羊回| D["LRLL"]
    D -->|帶菜| E["RRLR"]
    E -->|農夫獨返| F["LRLR"]
    F -->|帶羊| G["RRRR<br/>(終點)"]
    style S fill:#e3f2fd
    style G fill:#e8f5e9

原本需要「動腦試」的益智題，被翻譯成一張小圖之後，就成了再標準不過的最短路徑問題。

延伸洞見：test 與 debug 的精確定義#

把系統看成一台在狀態之間轉移的機器，許多工程行為立刻有了乾淨的定義。

test = 想辦法讓系統暴露出它進入了某個「非法狀態」（不該出現的局面）。

debug = 從那個非法狀態出發，沿著「導致它的因果轉移鏈」逆向回溯，找出最早讓系統偏離合法狀態的那一步。

換句話說，測試是在狀態空間裡布下偵測網，除錯是在轉移圖上反向走一條路。

用這個視角看，「不可重現的 bug」之所以難纏，正是因為導致非法狀態的那條轉移鏈依賴了難以還原的外部條件；而「加 log」的本質，就是把轉移鏈上的中間狀態記錄下來，好讓逆向回溯有跡可循。

等價變換工具箱#

抽象狀態的同時也提醒我們：同一份資訊可以有多種等價的表示，換一種表示常讓問題瞬間變簡單。 這裡點到為止地列幾個跨領域的例子：

• 不用暫存變數交換兩數：a ^= b; b ^= a; a ^= b;，用互逆運算把資訊在兩個變數間「搬移」而不需第三方——背後是 XOR 的可逆性，詳見位操作基礎。
• 傅立葉變換：把時域訊號換成頻域表示後，能量集中在少數頻率上，丟掉人眼不敏感的高頻成分就完成了壓縮——這正是 JPEG 的核心思路。
• Git 的歷史：不存每個版本的整份快照，而是記「初始狀態 + 每一步的增量（diff）」。任一歷史版本都能由初始狀態沿增量重放得到——本質上就是把「版本」抽象成狀態、把「commit」抽象成轉移。

小結#

「狀態 ➡️ 狀態圖 ➡️ 圖論」是一條能跨領域復用的解題管線。益智題、編譯器、測試除錯、訊號壓縮、版本控制，表面毫不相干，骨子裡都是在某個狀態空間上做轉移與走訪。下次卡關時，先別急著寫程式，先問自己：我的「狀態」是什麼？它們之間怎麼轉移？