YI時間｜外刊｜MM-DFW｜機器學習系列
點選上方藍字，關注給你寫幹貨的松子茶
動态規劃的概述
動态規劃(Dynamic Programming), 在20世紀50年代由美國數學家Richard Bellman提出，作為多階段決策過程最優化的一種通用算法設計之一，不僅解決特定類型的最優化問題，也包括某些非最優化問題。多階段決策過程最優化諸多實際問題：有多個解，但要找到最優解。
動态規劃算法步驟
設計一個動态規劃算法，通常可以按以下幾個步驟進行：
- 刻畫最優解的結構特性；
- 遞歸定義最優解值；
- 以自底向上方式計算最優解值；
- 根據計算得到的資訊構造一個最優解。
其中，第1至2步是動态規劃算法的基本步驟。最優解值是最優解的目标函數的值。
動态規劃算法的基本步驟
- 劃分階段：按照問題的時間或空間特征，把問題分為若幹個階段。
- 選擇狀态：将問題發展到各個階段時所處于的各種客觀情況用不同的狀态表示出來。
- 确定決策并寫出狀态轉移方程：狀态轉移就是根據上一階段的狀态和決策來導出本階段的狀态。
- 寫出規劃方程(包括邊界條件)：動态規劃的基本方程是規劃方程的通用形式化表達式。
動态規劃的設計要素
-
最優化原理Principle of Optimality(最優子結構特性)指出：一個最優政策具有這樣的性質，不論過去狀态和決策如何，對前面的決策所形成的狀态而言，其餘決策必定構成最優政策。這便是最優決策序列的最優子結構特性。
無論過程的初始狀态和初始決策是什麼，其餘的決策都必須相對于初始決策所産生的狀态構成一個最優決策序列。原理告訴我們，一個最優問題的任何執行個體的最優解是由該執行個體的子執行個體的最優解組成的。
一般來說，如果所求解問題對于最優性原理成立，則說明用動态規劃方法有可能解決該問題。而解決問題的關鍵在于擷取各階段間的遞推關系式。
- 無後向性: 将各階段按照一定的次序排列好之後，對于某個給定的階段狀态，它以前各階段的狀态無法直接影響它未來的決策，而隻能通過目前的這個狀态。換句話說，每個狀态都是過去曆史的一個完整總結。這就是無後向性，又稱為無後效性。
- 重疊子問題: 動态規劃将原來具有指數級複雜度的搜尋算法改進成了具有多項式時間的算法,其中的關鍵在于解決備援，這是動态規劃算法的根本目的。動态規劃實質上是一種以空間換時間的技術，它在實作的過程中，不得不存儲産生過程中的各種狀态，是以它的空間複雜度要大于其它的算法。是以，能夠用動态規劃解決的問題還有一個顯著特征：子問題的重疊性。這個性質并不是動态規劃适用的必要條件，但是如果該性質無法滿足，動态規劃算法同其他算法相比就不具備優勢。
動态規劃的實質是分治政策和解決備援，是以，動态規劃是一種将問題執行個體分解為更小的、相似的子問題，并存儲子問題的解而避免計算重複的子問題，以解決最優化問題的算法政策。
動态規劃求解問題的步驟
- 劃分子問題：用參數表達子問題的邊界，将問題求解轉變成多步判斷的過程。
- 确定優化函數：以該函數的極大(或極小)作為判斷的依據，确定是否滿足優化原則。
- 列出關于優化函數的遞推方程(或不等式)和邊界條件。
- 考慮是否需要設立标記函數。
- 自底向上計算，以備忘錄方法(表格)存儲中間結果。
動态規劃算法的典型應用
- 投資問題
- 背包問題
- 最長公共子序列LCS
- 圖像壓縮
- 最大子段和
- 最優二分檢索樹
- 每對結點之間的最短路徑(Warshall和Floyd算法)
- ……
歡迎評論哦，糾錯評論建議均可
-THE END-
版權聲明：以上内容為松子茶公衆号原創作品，版權歸屬作者所有。未經作者授權，嚴禁轉載或鏡像，否則将依法追究相關行為主體的法律責任。歡迎各位朋友轉發朋友圈分享。