資源簡介

(共18張PPT)
第13課
算法的設計
目錄
動態規劃算法
01
動態規劃算法的應用
02
動態規劃算法
01
Part One
【動態規劃算法】最優化原理
1951年美國數學家R．Bellman等人，根據一類多階段問題的特點，把“多階段決策”問題變換為一系列互相聯系的“單階段問題”，然后逐個加以解決。而且一些靜態模型，只要人為地引進“時間”因素，分成時段，就可以轉化成多階段的動態模型，用動態規劃方法去處理。
與此同時，他提出了解決這類問題的“最優化原理”(Principle of optimality)：“一個過程的最優決策具有這樣的性質：即無論其初始狀態和初始決策如何，其今后諸策略對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略”。簡言之，一個最優策略的子策略，對于它的初態和終態而言也必是最優的。
這個“最優化原理”如果用數學化一點的語言來描述的話，就是：假設為了解決某一優化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優的，對于任何一個整數k，1 \u003C k \u003C n，不論前面k個決策是怎樣的，以后的最優決策只取決于由前面決策所確定的當前狀態，即以后的決策Dk+1，Dk+2，…，Dn也是最優的。
最優化原理是動態規劃的基礎，任何一個問題，如果失去了這個最優化原理的支持，就不可能用動態規劃方法計算。能采用動態規劃求解的問題都需要滿足一定的條件。
(1) 問題中的狀態必須滿足最優化原理；
(2) 問題中的狀態必須滿足無后效性。所謂的無后效性是指：“下一時刻的狀態只與當前狀態有關，而和當前狀態之前的狀態無關，當前的狀態是對以往決策的總結”。
滿足條件：
問題求解模式
動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。
動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
(1)劃分階段：
按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
01
02
(2)確定狀態和狀態變量： 將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無后效性。
03
動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
（3）確定決策并寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態之間的關系來確定決策。
01
02
(4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
03
04
動態規劃算法的應用
02
動態規劃算法的應用：
最長公共子序列(LCS)
最長遞增子序列(LIS)
背包問題
用動態規劃實現導彈攔截
最大化投資回報問題的實現
矩陣連乘
走金字塔
凸多邊形最優三角剖分
雙調歐幾里得旅行商問題
小結
今天你學到了什么 說一說自己的收獲。
練習1
針對機器人畫正六邊形的問題,設計一個算法。
練習2
練習3
感謝聆聽

展開更多......

收起↑