第7章 離散結構的迭代#

章前言#

迭代不只是連續數值的事。圖、樹、狀態機、程式分析——這些離散結構上的計算同樣是「反覆套用轉換、直到穩定」的過程，只是此時「收斂」的意義變成到達不動點（有限格上的單調迭代必然有限步終止），而不再是無窮逼近。

本章三節各佔一個經典場景。7.1 節迭代加深搜尋（IDDFS）：用「由淺入深反覆做深度優先」的方式取得廣度優先的保證與深度優先的省空間，是西洋棋等遊戲 AI 的標準搜尋策略。7.2 節把動態規劃重新詮釋為迭代：遞迴＋備忘錄是「自上而下的迭代」，填表是「自下而上的迭代」，兩者只是同一個 DAG 上不動點計算的兩種遍歷順序。7.3 節迭代式資料流分析：編譯器反覆在控制流圖上傳播事實（活變數、可用表達式），直到所有節點的狀態不再改變——這是克萊尼不動點定理的工程應用，也是「迭代到不動點」最純粹的展示。

讀完本章你會看到：第 2 章的不動點思想在離散世界換了一副面孔——單調性取代壓縮性，有限格保證終止。同一套「初始值、更新規則、停止條件」的思考框架仍然暢通無阻。