第3章 動態(tài)規(guī)劃(part1).ppt

1、第三章動態(tài)規(guī)劃第一部分，上海大學計算機科學學院的沈云福，研究了動態(tài)規(guī)劃算法的關(guān)鍵點，理解了動態(tài)規(guī)劃算法的概念和基本思想。掌握動態(tài)規(guī)劃算法的兩個基本要素(1)最優(yōu)子結(jié)構(gòu)性質(zhì)(2)重疊子問題性質(zhì)，掌握設(shè)計動態(tài)規(guī)劃算法的求解步驟從上到下到上的4個步驟；Memo(制表)的應(yīng)用動態(tài)規(guī)劃的典型問題：矩陣乘法、最長公共子序列、0-1背包問題、最大分段和、流水車間調(diào)度(約翰遜調(diào)度規(guī)則)等。幾個典型問題的介紹，問題1:最短路徑，有一條棋盤街，有人從西南角O走到東北角U，想選一條路線走最短路徑，怎么去？o，b，a，C，d，e，f，g，h，I，n，k，l，m，p，q，r，s，t，u，1323，2214，2345，2

2、312，21223，34123，示例：有n=8個體積為54，45，43，29，23，21，14，1的對象和一個體積為C=110的背包，這些對象可以裝入背包問題4:文本相似性問題給定兩篇文章(或代碼)的文本x=和y=的情況下，它們之間公共部分的最長長度是多少？3.1矩陣乘法問題，3.1矩陣乘法問題，給定n個矩陣A1，A2和an，其中Ai和Aj 1是乘法的，i=1，2和n-l，現(xiàn)在我們需要計算這n個矩陣的連續(xù)乘積A1A2An。矩陣乘法問題：確定一個運算順序，使運算總數(shù)最小化。1。問題描述，矩陣乘法，A=(aij)mk，B=(bij)kn，C=(cij)mn計算C:每個元素需要k次乘法，k-1次加法

3、C有mn個元素：計算C需要mnk次乘法，mn(k-1)次加法示例：讓A1，A2，mn。矩陣乘法方法的數(shù)量和括號模式的數(shù)量之間是一一對應(yīng)的。全括號矩陣乘法乘積可以遞歸地定義為：(1)單個矩陣是全括號的；(2)如果矩陣連續(xù)乘積A完全被括號括起來，則A可以表示為兩個完全被括號括起來的矩陣連續(xù)乘積B和C的乘積，即A=(BC)。矩陣連續(xù)乘積被括起來。有四個矩陣A、B、C和D，它們的維數(shù)分別為：16000、10500、36000和87500，列出所有可能的計算順序，并計算每個計算順序所需的次數(shù)。所有可能的計算順序是什么？設(shè)矩陣序列的括號為P(n)，我們可以得到：1 (n=1)，p (n)=1，P(N)是加

4、泰羅尼亞數(shù)P(N)=1(4n/n3/2)。第二，算法分析一種新的思路，采用一種新的方法，(1)分析最優(yōu)解AI: I=AI，mii=0，問題變成：計算A1: N，求m1n，第二，算法分析一種新的思路，(2)建立遞歸關(guān)系，m1n=m1k mk 1n p0pkpn。一般來說，假設(shè)計算a1:J的最優(yōu)階來斷開矩陣ak和Ak 1之間的矩陣鏈，I KJ，MIJ=MikMK 11。假設(shè)計算a1: n的最優(yōu)階來斷開矩陣Ak和Ak 1之間的矩陣鏈，并分析最優(yōu)解的特征和結(jié)構(gòu)。特點：計算矩陣子鏈AI 3360 k和Ak 1:j的順序也是最優(yōu)的。矩陣乘法計算順序問題的最優(yōu)解包含其子問題的最優(yōu)解。這種性質(zhì)被稱為最優(yōu)子結(jié)構(gòu)

5、性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該算法可以解決的一個顯著特征。矩陣鏈問題的一般遞歸關(guān)系，mij=，0 i=j，(3)計算最優(yōu)值，1，簡單遞歸，2，動態(tài)規(guī)劃的求解方法是自下而上求解的，1ijn的不同有序?qū)?I，j)對應(yīng)不同的子問題。因此，不同子問題的數(shù)目只有，mij=，計算最優(yōu)值的程序，空矩陣鏈(int * p，int n，int * * m) int I，r，j，k，t；對于(I=1；I=n；I)MII=0；對于(r=2；r=n；r)為(I=1；I=n-r l；I)j=I r-1；mij=mi 1j pi-1 * pi * pj；對于(k=I 1；k . j .k)t=mik MK 1j pi 1

6、 * PK * pj；如果(t mij)mij=t；算法過程、算法復雜度分析以及算法矩陣鏈的主要計算量取決于算法中的三重循環(huán)。循環(huán)中的計算量為O(1)，三次循環(huán)的總數(shù)為O(n3)。因此，該算法的計算時間上限為O(n3)。該算法占用的空間顯然是O(n2)。(4)算法分析構(gòu)造最優(yōu)解，如果(I=j)返回，則使回溯(int I，int j，int * * s)無效；追溯(I，sij，s)；追溯(sij 1，j，s)；cout乘A i，sijCout和A (sij 1)，j endl，引入劃分標記sij，確定括號模式，構(gòu)造最優(yōu)解。3.2動態(tài)規(guī)劃算法的基本要素、動態(tài)規(guī)劃的基本思想以及算法的目標：解決具有某

7、些最優(yōu)性質(zhì)的問題。它可能有許多可行的解決方案，希望找到最有價值的解決方案。算法思想：動態(tài)規(guī)劃算法將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解中得到原問題的解。這些子問題通常不是相互獨立的。分解中可能有許多子問題，有些子問題已經(jīng)被重復計算過多次。自下而上和自上而下兩種方式都采用備忘錄法：在求解過程中需要保存已求解子問題的解，必要時可以找出已求解的解，避免大量重復計算，節(jié)省時間。動態(tài)規(guī)劃用表格記錄所有已解決的子問題的答案。無論子問題將來是否被使用，只要它已經(jīng)被計算，結(jié)果將被填入表中。動態(tài)規(guī)劃中的概念和術(shù)語(1)，1。階段：問題被分成幾個相互關(guān)聯(lián)的連續(xù)環(huán)節(jié)，這些環(huán)節(jié)被稱為階段。

8、2.狀態(tài)：某一階段的起始位置稱為狀態(tài)。通常，一個階段包含幾個狀態(tài)。3.決策：從一個階段的一個狀態(tài)到下一個階段的選擇。特點：前一階段的終點是后一階段的起點，前一階段的決定影響后一階段的狀態(tài)。4.策略：一個決策序列，由從開始到結(jié)束的整個過程中的每個決策組成。動態(tài)編程中的概念和術(shù)語(2)，5。狀態(tài)轉(zhuǎn)移方程：描述狀態(tài)從K階段到k 1階段的演化規(guī)律的方程稱為狀態(tài)轉(zhuǎn)移方程(用數(shù)學形式表示)。6.目標函數(shù)和優(yōu)化概念：目標函數(shù)是衡量多階段決策過程優(yōu)劣的標準。優(yōu)化的概念是在一定的條件下找到一種方法，根據(jù)課題的具體性質(zhì)確定操作后，使整個過程的總效益達到最佳。7.動態(tài)規(guī)劃：在多階段決策問題中，每個階段做出的決策取決

9、于當前狀態(tài)，并導致狀態(tài)轉(zhuǎn)換，以獲得最佳過程。最佳原則優(yōu)化策略的子策略總是最佳的。1.找出最優(yōu)解的性質(zhì)并描述其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值(寫動態(tài)規(guī)劃方程)3。自下而上(或自上而下)計算最佳值4。根據(jù)計算最優(yōu)值時獲得的信息構(gòu)造最優(yōu)解。注：1 .步驟1-3是動態(tài)編程算法的基本步驟。2.如果只尋求最佳值，則可以省略步驟4；3.如果您需要問題的最佳解決方案，您必須執(zhí)行步驟4，并且步驟3中記錄的信息必須足以構(gòu)建最佳解決方案。，動態(tài)規(guī)劃的求解方法，自下而上求解是一種動態(tài)規(guī)劃方法，所有子問題都計算一次，沒有遞歸代價。程序(下頁)，空矩陣鏈(int p，int n，int * * m，int * * s)為(i

10、nt I=1；I=n；I)MII=0；for(int r=2；r=n；r)for(int I=1；I=n-r l；I)int j=I r-1；mij=mi 1j Pi-1 * Pi * Pj；sij=I；for(int k=I 1；k . j .k)int t=mik MK 1j Pi 1 * PK * Pj；如果(t mij)mij=t；sij=k；Memo方法是動態(tài)規(guī)劃算法的基本元素，動態(tài)規(guī)劃算法的有效性取決于問題本身的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。1最優(yōu)子結(jié)構(gòu)：當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，表示該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。如何解釋問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)？使用反

11、證的方法：首先假設(shè)由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后試圖證明在這種假設(shè)下可以構(gòu)造出比原問題的最優(yōu)解更好的解，這導致矛盾。動態(tài)規(guī)劃算法的基本要素，2個重疊子問題：用遞歸算法自上而下求解問題時，每次生成的子問題并不總是新的，有些子問題是重復計算的。這個性質(zhì)稱為子問題的重疊性質(zhì)。矩陣計算順序、重疊子結(jié)構(gòu)性質(zhì)，動態(tài)規(guī)劃算法利用子問題的重疊性質(zhì)，每個子問題只求解一次，將解保存在表中，并在將來盡可能多地使用這些子問題的解。特征：不同子問題的數(shù)量隨著問題的大小呈指數(shù)增長。使用動態(tài)規(guī)劃算法只需要多項式時間，因此可以獲得較高的問題求解效率。動態(tài)規(guī)劃法和分治策略，通用性：都是通過子問題來解決原問題：分

12、治法將一個規(guī)模的問題分成幾個與原問題類型相同的較小的子問題，并通過求解子問題和合并子問題的解來構(gòu)造整個問題的解；動態(tài)規(guī)劃法也是先找到子問題的解，然后通過求解子問題來構(gòu)造原問題的解。動態(tài)規(guī)劃法和分治策略(續(xù))，區(qū)別：獨立性：分治法的每個子問題是相互獨立的，動態(tài)規(guī)劃法的每個子問題不能是獨立的。子問題數(shù)：動態(tài)規(guī)劃方法中涉及的子問題很多，它們不是獨立的，而是多項式級的；分而治之方法所涉及的子問題數(shù)量通常達到指數(shù)級。動態(tài)規(guī)劃方法將問題分成多個子問題，每個子問題的解都是局部最優(yōu)的；分治法不一定考慮最優(yōu)性。動態(tài)規(guī)劃法可以采用備忘錄法。Memo方法的控制結(jié)構(gòu)與直接遞歸方法相同，但不同之處在于，memo方法為每

13、個已解決的子問題建立備忘錄，以便在必要時查看，從而避免重復解決同一個子問題。int t，k，m=0；int lookupChain(int i，int j) if (mij 0)返回mij；如果(i=j)返回0；int u=lookupChain(i 1，j)pi-1 * pi * pj；/記住初始值sij=I；對于(k=I 1；k . j .k)，t=查找鏈(I，k)查找鏈(k 1，j)pi-1 * PK * pj；如果(t u)u=t；sij=k；mij=u；返回u；動態(tài)規(guī)劃概要，特征：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。最佳原理，動態(tài)規(guī)劃法和分治法的聯(lián)系和區(qū)別，動態(tài)規(guī)劃法的使用方法，作業(yè)和計

14、算機問題，1。分析問題3-1，實現(xiàn)問題3-4(數(shù)字三角形)2。(補充)讓A、B、C、D、E和F分別為5010、103、312、125 3。分析問題3-3，實現(xiàn)問題3-2(編輯距離)，3-6(游輪問題)，3-13(最大k產(chǎn)品)，實現(xiàn)3-7(汽車加油)。第四周上機：修改3.1節(jié)的算法，找出計算n個矩陣乘積的最小乘法數(shù)，完成加括號的過程。(12)-1611，動態(tài)規(guī)劃問題解決示例1。1.給出了一個m*n棋盤上的單側(cè)跳馬問題，以及一匹馬的最短路徑長度注意：在這個問題中，馬只能向右下走，但不能向左上走。輸入由空格分隔的兩個整數(shù)m，n，(1m，n19)，表示棋盤的大小。

15、輸出馬從棋盤左上角跳到右下角所需的最短路徑長度。如果它不能跳，直接輸出“不可能”。分析，讓f(i，j)是從(I，j)到(m，n)的最短距離?？梢詮?I，j)中選取兩個位置(i 1，j 2)和(i 2，j 1)。(m，n)，(1，1)，(I，j)，初始值：用動態(tài)規(guī)劃解決問題的例子2。在抄寫手稿之前，人們依靠抄寫員抄寫書籍。有一次，一家劇院想排練一出戲，希望能復制一份劇本。眾所周知，劇本由M卷組成，每卷都有pi頁(1=i=m)。使用k個抄寫員(1千米)，每個抄寫員只能被分配一個任務(wù)，即復制幾個連續(xù)的手稿。假設(shè)每個抄寫員都有相同的復印速度。完成任務(wù)所需的總時間由工作量最大的抄寫員決定，即抄寫員要復制的總頁數(shù)。找到一個分配方案，以盡量減少完成任務(wù)所需的總時間。輸入整數(shù)m和K.然后輸入m個整數(shù)p1、p2、p3、pm，用空格隔開。輸出完成任務(wù)所需的最短總時間。讓Fij成為第一批抄寫第一批j冊的人的最短完成時間。檢查第三個人的復制情況。讓我們假設(shè)第一批T書是由第一批i-1人復制的，第一批t 1、t 2和J書是由第一