1. 從“萬能鑰匙”到“特定扳手”重新審視動態(tài)規(guī)劃在算法和數(shù)學(xué)建模的世界里動態(tài)規(guī)劃Dynamic Programming, DP一度被奉為解決復(fù)雜優(yōu)化問題的“萬能鑰匙”。無論是經(jīng)典的背包問題、最短路徑問題還是復(fù)雜的資源調(diào)度、序列比對DP似乎總能提供一個清晰、優(yōu)雅的解決方案框架。很多初學(xué)者包括當(dāng)年的我都曾沉迷于其“狀態(tài)轉(zhuǎn)移方程”的魔力認為只要定義好狀態(tài)寫出方程問題就迎刃而解了。然而隨著處理的問題規(guī)模越來越大、約束條件越來越復(fù)雜這把“萬能鑰匙”開始頻頻卡殼甚至完全打不開鎖。你會發(fā)現(xiàn)DP并非無所不能它有著非常明確的適用邊界和內(nèi)在局限。今天我想從一個數(shù)學(xué)建模實踐者的角度拋開教科書式的贊美深入聊聊動態(tài)規(guī)劃在實際應(yīng)用中遇到的“天花板”以及我們有哪些思路可以嘗試去突破它。動態(tài)規(guī)劃的核心思想簡而言之就是將一個大問題分解為一系列相互重疊的子問題通過解決所有子問題并存儲其結(jié)果記憶化來避免重復(fù)計算最終高效地獲得原問題的最優(yōu)解。這個“最優(yōu)子結(jié)構(gòu)”和“重疊子問題”的特性是DP能夠高效工作的基石。但是正是這兩個特性也成為了它最大的限制來源。當(dāng)我們面對的問題不具備清晰的最優(yōu)子結(jié)構(gòu)或者子問題的數(shù)量隨著問題規(guī)模呈指數(shù)級爆炸時DP就會立刻顯得力不從心。更不用說在真實的數(shù)學(xué)建模場景中我們往往還要處理連續(xù)變量、不確定性、多目標(biāo)優(yōu)化等DP傳統(tǒng)框架難以直接容納的復(fù)雜因素。因此理解DP的局限性不是為了否定它而是為了更精準(zhǔn)地使用它并在它失效時知道該轉(zhuǎn)向何方。這就像工具箱里的工具你知道扳手擰螺絲最好但遇到釘子就得換錘子。2. 動態(tài)規(guī)劃的三重“天花板”維度、結(jié)構(gòu)與精確性動態(tài)規(guī)劃的局限性主要集中體現(xiàn)在三個維度上計算復(fù)雜度、問題結(jié)構(gòu)適應(yīng)性以及解的精確性要求。這三個方面相互關(guān)聯(lián)共同構(gòu)成了DP在實際應(yīng)用中的主要挑戰(zhàn)。2.1 維數(shù)災(zāi)難當(dāng)狀態(tài)空間爆炸時這是動態(tài)規(guī)劃最廣為人知也最致命的局限學(xué)術(shù)上稱為“維數(shù)災(zāi)難”。DP的效率嚴重依賴于狀態(tài)空間的大小。狀態(tài)通常由多個變量定義例如在資源分配問題中狀態(tài)可能是(剩余資源量 當(dāng)前階段)在路徑規(guī)劃中狀態(tài)可能是(當(dāng)前位置 已訪問節(jié)點集合)。問題規(guī)模一旦增大狀態(tài)的數(shù)量就會呈指數(shù)級增長。舉個例子一個經(jīng)典的旅行商問題需要訪問n個城市。如果使用DP中的“集合動態(tài)規(guī)劃”方法狀態(tài)定義為(當(dāng)前所在城市 已經(jīng)訪問過的城市集合)。那么狀態(tài)總數(shù)就是n * 2^n。當(dāng)n20時狀態(tài)數(shù)約為2000萬尚可勉強計算當(dāng)n30時狀態(tài)數(shù)就超過了300億即使是現(xiàn)代計算機也難以在合理時間內(nèi)完成遍歷。這里的“維數(shù)”指的就是定義狀態(tài)所需變量的個數(shù)每個變量可能的取值組合起來就構(gòu)成了龐大的狀態(tài)空間。注意在實際編程中即使使用了記憶化遞歸或自底向上的遞推維數(shù)災(zāi)難帶來的巨大內(nèi)存消耗和時間消耗也是無法回避的。你可能會想到用哈希表存儲狀態(tài)但哈希操作本身也有開銷且無法改變狀態(tài)數(shù)量指數(shù)增長的本質(zhì)。2.2 結(jié)構(gòu)之困當(dāng)問題不再“乖巧”動態(tài)規(guī)劃要求問題具備兩個關(guān)鍵性質(zhì)最優(yōu)子結(jié)構(gòu)和重疊子問題。很多現(xiàn)實問題并不滿足這些“乖巧”的假設(shè)。最優(yōu)子結(jié)構(gòu)缺失這意味著一個問題的最優(yōu)解無法由其子問題的最優(yōu)解簡單組合得到。例如在一些圖論問題中全局最優(yōu)路徑可能并不由局部最優(yōu)路徑組成貪心算法在此也會失效。更常見的場景是在帶有復(fù)雜約束或耦合關(guān)系的優(yōu)化問題中。假設(shè)一個生產(chǎn)調(diào)度問題機器A和機器B的生產(chǎn)任務(wù)相互影響比如共享一個預(yù)熱資源那么單獨優(yōu)化機器A的排產(chǎn)子問題得到的最優(yōu)解與機器B的最優(yōu)解組合起來很可能不是全局最優(yōu)解因為兩者之間存在耦合。這種情況下DP的分解策略就失效了。重疊子問題不明顯DP的優(yōu)勢在于避免重復(fù)計算。但如果一個問題分解后的子問題幾乎都是獨一無二的很少重復(fù)那么記憶化存儲帶來的收益就微乎其微反而增加了存儲開銷。例如某些決策樹搜索問題每條路徑都大相徑庭此時使用DP就和暴力搜索區(qū)別不大了。2.3 連續(xù)與不確定性的挑戰(zhàn)傳統(tǒng)的動態(tài)規(guī)劃框架天生適合離散、確定性的問題。然而數(shù)學(xué)建模中大量問題涉及連續(xù)變量或隨機性。連續(xù)狀態(tài)空間很多優(yōu)化問題的變量是連續(xù)的比如控制理論中的狀態(tài)變量、經(jīng)濟學(xué)中的資源投入量。DP需要離散化狀態(tài)空間將其劃分為有限的網(wǎng)格點。但這立即引入了兩個新問題1.離散化誤差解的質(zhì)量取決于網(wǎng)格的精細程度。網(wǎng)格太粗結(jié)果不精確網(wǎng)格太細又落入維數(shù)災(zāi)難的陷阱。2.維度放大對一個連續(xù)變量離散化為10個點如果狀態(tài)有3個這樣的連續(xù)變量狀態(tài)數(shù)就是10^31000。這進一步加劇了計算負擔(dān)。隨機性與不確定性現(xiàn)實世界充滿不確定性例如市場需求波動、設(shè)備隨機故障。這引出了隨機動態(tài)規(guī)劃。雖然理論上是DP的擴展但實踐難度陡增。狀態(tài)轉(zhuǎn)移不再是一個確定性的函數(shù)而是一個概率分布。計算期望值需要對所有可能的后繼狀態(tài)進行積分或求和這通常需要與蒙特卡洛模擬等方法結(jié)合計算量巨大。對于復(fù)雜系統(tǒng)要獲得準(zhǔn)確的轉(zhuǎn)移概率本身就是一個難題。3. 破局之道針對性的改進思路與替代方案認識到局限性之后我們不必拋棄動態(tài)規(guī)劃而是可以針對性地進行改進或者在DP完全不適合時明智地選擇其他工具。下面分享幾種在實踐中驗證過的思路。3.1 算法層面的優(yōu)化與時間與空間的博弈當(dāng)問題大體符合DP模型但受限于規(guī)模時我們可以嘗試以下算法優(yōu)化策略狀態(tài)壓縮這是減少存儲開銷的經(jīng)典技術(shù)。例如在很多DP問題中我們只需要前一個或前幾個階段的狀態(tài)來計算當(dāng)前狀態(tài)那么就可以用滾動數(shù)組只保留必要的狀態(tài)將空間復(fù)雜度從O(n)降低到O(1)或O(k)。在基于集合的狀態(tài)表示中如旅行商問題可以用位運算bitset來高效表示和操作集合一個32位整數(shù)就能表示32個元素的在/不在狀態(tài)極大壓縮了空間。剪枝與啟發(fā)式在搜索狀態(tài)空間時提前排除那些明顯不可能達到最優(yōu)解的狀態(tài)分支。例如如果當(dāng)前部分解的成本已經(jīng)超過了目前已知的最優(yōu)解成本那么從這個狀態(tài)出發(fā)的所有后續(xù)擴展都可以被“剪枝”掉。這需要設(shè)計有效的估價函數(shù)Heuristic雖然不能保證剪掉所有無效分支但能大幅提升搜索效率。A*算法就是DPDijkstra算法與啟發(fā)式搜索結(jié)合的典范。分解與降維審視狀態(tài)定義是否所有維度都是必需的能否通過問題本身的特性減少狀態(tài)維度例如在某些問題中兩個狀態(tài)變量可能具有某種單調(diào)性或依賴關(guān)系使得我們可以用一維的狀態(tài)間接表示二維的信息?；蛘邔⒃瓎栴}分解成幾個關(guān)聯(lián)較弱的子問題分別用DP求解再協(xié)調(diào)結(jié)果雖然可能損失最優(yōu)性但能換來可行性。3.2 模型重構(gòu)從精確到近似當(dāng)追求精確最優(yōu)解的計算代價無法承受時轉(zhuǎn)向近似算法或啟發(fā)式算法是更務(wù)實的選擇。在數(shù)學(xué)建模中我們常常需要在“最優(yōu)解”和“可計算的好解”之間權(quán)衡。近似動態(tài)規(guī)劃這是針對維數(shù)災(zāi)難和隨機性的重要研究方向。其核心思想是用函數(shù)來近似值函數(shù)而不是傻傻地存儲每一個狀態(tài)點的值。值函數(shù)是DP的核心它存儲了從某個狀態(tài)出發(fā)能達到的最佳收益。ADP通過一個參數(shù)化的函數(shù)如線性函數(shù)、神經(jīng)網(wǎng)絡(luò)來擬合這個值函數(shù)。在迭代過程中我們不再更新所有狀態(tài)的值而是采樣一部分狀態(tài)用這些樣本值來更新近似函數(shù)的參數(shù)。這樣存儲空間從狀態(tài)數(shù)量級降低到參數(shù)數(shù)量級極大地克服了維數(shù)災(zāi)難。深度強化學(xué)習(xí)中的DQN算法就可以看作是ADP與深度學(xué)習(xí)結(jié)合的成功案例。貪心與元啟發(fā)式算法對于不具備最優(yōu)子結(jié)構(gòu)或者我們只需求得一個滿意解的問題這類算法非常有效。貪心算法每一步做出局部最優(yōu)選擇。它速度快但通常無法保證全局最優(yōu)。然而對于許多特定類型的問題如最小生成樹、霍夫曼編碼貪心策略恰恰能得到最優(yōu)解這就需要我們對問題性質(zhì)有深刻理解。元啟發(fā)式算法如模擬退火、遺傳算法、蟻群算法等。它們不依賴于問題的精確數(shù)學(xué)模型而是通過模擬物理過程、生物進化等機制在解空間中進行全局搜索。這些算法適用于解空間復(fù)雜、非線性、多峰的問題。雖然不能保證找到最優(yōu)解也通常沒有理論上的最壞情況界限但在實際建模競賽和工程中往往能在合理時間內(nèi)找到質(zhì)量非常高的解。我的經(jīng)驗是對于復(fù)雜的組合優(yōu)化問題如車輛路徑規(guī)劃、車間調(diào)度在DP束手無策時遺傳算法或模擬退火通常是第一備選。3.3 框架擴展擁抱連續(xù)與隨機對于連續(xù)和隨機問題我們需要擴展或跳出經(jīng)典DP的離散確定框架。連續(xù)動態(tài)規(guī)劃與哈密頓-雅可比-貝爾曼方程對于連續(xù)時間、連續(xù)狀態(tài)的優(yōu)化問題最優(yōu)控制理論的核心DP思想演變成了求解HJB方程。這是一個偏微分方程其解就是值函數(shù)。雖然解析求解HJB方程極其困難但數(shù)值求解方法如有限差分法、水平集法為此類問題提供了途徑。這相當(dāng)于把離散的DP狀態(tài)網(wǎng)格擴展到了連續(xù)的時空域上。隨機動態(tài)規(guī)劃與仿真結(jié)合對于復(fù)雜的隨機系統(tǒng)純數(shù)學(xué)的SDP可能難以處理。一個實用的方法是仿真優(yōu)化。我們?nèi)匀槐Ａ鬌P的“階段”決策思想但在每個階段對于需要評估的決策我們不進行復(fù)雜的期望值積分計算而是通過運行大量快速的計算機仿真蒙特卡洛模擬來估計該決策的期望收益。然后基于這些仿真結(jié)果用策略迭代或值迭代的思路來改進決策。這種方法將DP的序貫決策框架與仿真處理隨機性的能力結(jié)合起來非常適用于供應(yīng)鏈、庫存管理等領(lǐng)域的隨機模型。4. 數(shù)學(xué)建模中的選型實戰(zhàn)以資源分配問題為例讓我們通過一個數(shù)學(xué)建模中常見的資源分配問題來具體感受一下這些局限性和改進思路的應(yīng)用。假設(shè)我們要將一個總額為M的資金分配給N個不同的投資項目。每個項目i如果獲得x單位的投資預(yù)計會產(chǎn)生收益f_i(x)。我們的目標(biāo)是最大化總收益。這看起來像一個標(biāo)準(zhǔn)的背包問題變種。經(jīng)典DP思路定義狀態(tài)dp[i][j]為考慮前i個項目總投入不超過j時能獲得的最大收益。狀態(tài)轉(zhuǎn)移方程為dp[i][j] max(dp[i-1][j], dp[i-1][j-k] f_i(k))其中k是為項目i分配的資金。這里j和k都是離散的比如以萬元為單位。遇到的局限維數(shù)災(zāi)難如果M很大比如上億即使以萬為單位離散狀態(tài)j的維度也很大。如果投資項目間有耦合比如項目A和項目B同時投資會有協(xié)同效應(yīng)狀態(tài)可能需要增加維度來描述這種耦合立刻導(dǎo)致狀態(tài)空間爆炸。連續(xù)變量收益函數(shù)f_i(x)可能是x的連續(xù)函數(shù)如S型增長曲線。DP的離散化會損失精度。如果我們想得到資金分配的精確比例比如投35.7%離散化網(wǎng)格必須非常細。不確定性每個項目的收益f_i(x)可能不是一個確定值而是一個隨機變量取決于市場情況。這變成了一個隨機資源分配問題。改進與替代方案針對大規(guī)模M如果項目數(shù)N不大但M很大我們可以嘗試對偶思想。不去枚舉資金j而是枚舉“邊際收益”。或者使用貪心算法按照“單位投資收益率”從高到低分配雖然不一定最優(yōu)但速度快對于某些收益函數(shù)性質(zhì)如凹函數(shù)可能是最優(yōu)的。針對連續(xù)變量如果f_i(x)形式良好比如是凹函數(shù)這是一個凸優(yōu)化問題。我們完全可以放棄DP直接使用拉格朗日乘子法或梯度下降法等連續(xù)優(yōu)化方法效率更高還能得到精確的連續(xù)解。這是模型重構(gòu)的典型例子——識別出問題更本質(zhì)的數(shù)學(xué)結(jié)構(gòu)選用更合適的工具。針對不確定性我們可以采用隨機規(guī)劃或魯棒優(yōu)化的框架。例如兩階段隨機規(guī)劃第一階段分配部分資金觀察到部分隨機收益實現(xiàn)后第二階段再分配剩余資金。這可以用隨機動態(tài)規(guī)劃來建模但計算復(fù)雜。更實用的方法可能是將隨機收益用幾個典型場景Scenario來近似然后轉(zhuǎn)化為一個大規(guī)模確定性線性/非線性規(guī)劃問題來求解。這個例子告訴我們在數(shù)學(xué)建模中看到“分配”、“優(yōu)化”就本能地套用DP可能是一條彎路。首先分析問題的結(jié)構(gòu)線性、非線性、連續(xù)、離散、確定、隨機再選擇最適配的模型和算法才是更專業(yè)的做法。5. 思維轉(zhuǎn)變從“套用算法”到“設(shè)計算法”最后我想分享一點比具體技術(shù)更重要的體會應(yīng)對DP的局限性最深層次的改進方向在于思維模式的轉(zhuǎn)變。我們不應(yīng)僅僅滿足于成為算法的“應(yīng)用者”更應(yīng)努力成為“設(shè)計者”或“適配者”。理解問題本質(zhì)優(yōu)先于套用算法模板接到一個建模問題第一反應(yīng)不應(yīng)該是“這用DP怎么做”而應(yīng)該是“這個問題的核心決策是什么變量是什么約束是什么目標(biāo)是什么”。先嘗試用自然語言或數(shù)學(xué)公式清晰地定義問題。很多時候清晰的定義本身就能提示你合適的解決方案。如果問題有明顯的階段性和重疊子結(jié)構(gòu)DP才進入候選名單?；旌喜呗猿蔀槌B(tài)在實際的復(fù)雜建模中純DP的解決方案越來越少。更多的是混合模型。例如DP 啟發(fā)式用啟發(fā)式方法如貪心、局部搜索快速生成一個較好的初始解或策略然后在這個解的鄰域內(nèi)用DP進行精細化的局部優(yōu)化。DP 約束規(guī)劃/整數(shù)規(guī)劃對于帶有復(fù)雜約束的DP問題可以用約束編程來剪枝狀態(tài)空間只生成可行的狀態(tài)轉(zhuǎn)移再結(jié)合DP求優(yōu)。仿真 優(yōu)化如前所述用仿真的方式處理隨機性嵌入一個優(yōu)化算法可能是DP也可能是元啟發(fā)式來尋找策略。這種“組合拳”要求我們對多種優(yōu)化范式都有所了解并能靈活地將它們銜接起來。這遠比精通單一算法要復(fù)雜但也更有價值。接受近似與滿意解在學(xué)術(shù)訓(xùn)練中我們總是追求最優(yōu)解。但在現(xiàn)實世界的數(shù)學(xué)建模中尤其是面對大規(guī)模、復(fù)雜、快速變化的問題時“足夠好”且“算得快”的解其價值往往遠超那個理論上最優(yōu)但無法在時限內(nèi)算出的解。管理好利益相關(guān)者對“最優(yōu)”的期望展示近似算法的有效性及其與計算成本的權(quán)衡本身就是建模能力的重要組成部分。動態(tài)規(guī)劃是一把極其鋒利的刀但它只適合切特定的食材。一個優(yōu)秀的“廚師”建模者不僅要會用這把刀更要清楚它的刀法局限并熟知其他刀具如連續(xù)優(yōu)化、隨機規(guī)劃、元啟發(fā)式的用法。當(dāng)問題來臨時根據(jù)食材問題特性選擇最合適的工具或者創(chuàng)造性地組合使用它們才能烹飪出滿意的作品。這個過程就是從算法使用者成長為問題解決者的關(guān)鍵一步。