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

1、第三章動態(tài)規(guī)劃第一部分，上海大學(xué)計(jì)算機(jī)科學(xué)學(xué)院的沈云福，研究了動態(tài)規(guī)劃算法的關(guān)鍵點(diǎn)，理解了動態(tài)規(guī)劃算法的概念和基本思想。掌握動態(tài)規(guī)劃算法的兩個基本要素(1)最優(yōu)子結(jié)構(gòu)性質(zhì)(2)重疊子問題性質(zhì)，掌握設(shè)計(jì)動態(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)在我們需要計(jì)算這n個矩陣的連續(xù)乘積A1A2An。矩陣乘法問題：確定一個運(yùn)算順序，使運(yùn)算總數(shù)最小化。1。問題描述，矩陣乘法，A=(aij)mk，B=(bij)kn，C=(cij)mn計(jì)算C:每個元素需要k次乘法，k-1次加法

3、C有mn個元素：計(jì)算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，列出所有可能的計(jì)算順序，并計(jì)算每個計(jì)算順序所需的次數(shù)。所有可能的計(jì)算順序是什么？設(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，問題變成：計(jì)算A1: N，求m1n，第二，算法分析一種新的思路，(2)建立遞歸關(guān)系，m1n=m1k mk 1n p0pkpn。一般來說，假設(shè)計(jì)算a1:J的最優(yōu)階來斷開矩陣ak和Ak 1之間的矩陣鏈，I KJ，MIJ=MikMK 11。假設(shè)計(jì)算a1: n的最優(yōu)階來斷開矩陣Ak和Ak 1之間的矩陣鏈，并分析最優(yōu)解的特征和結(jié)構(gòu)。特點(diǎn)：計(jì)算矩陣子鏈AI 3360 k和Ak 1:j的順序也是最優(yōu)的。矩陣乘法計(jì)算順序問題的最優(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)計(jì)算最優(yōu)值，1，簡單遞歸，2，動態(tài)規(guī)劃的求解方法是自下而上求解的，1ijn的不同有序?qū)?I，j)對應(yīng)不同的子問題。因此，不同子問題的數(shù)目只有，mij=，計(jì)算最優(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；算法過程、算法復(fù)雜度分析以及算法矩陣鏈的主要計(jì)算量取決于算法中的三重循環(huán)。循環(huán)中的計(jì)算量為O(1)，三次循環(huán)的總數(shù)為O(n3)。因此，該算法的計(jì)算時間上限為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，引入劃分標(biāo)記sij，確定括號模式，構(gòu)造最優(yōu)解。3.2動態(tài)規(guī)劃算法的基本要素、動態(tài)規(guī)劃的基本思想以及算法的目標(biāo)：解決具有某

7、些最優(yōu)性質(zhì)的問題。它可能有許多可行的解決方案，希望找到最有價值的解決方案。算法思想：動態(tài)規(guī)劃算法將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解中得到原問題的解。這些子問題通常不是相互獨(dú)立的。分解中可能有許多子問題，有些子問題已經(jīng)被重復(fù)計(jì)算過多次。自下而上和自上而下兩種方式都采用備忘錄法：在求解過程中需要保存已求解子問題的解，必要時可以找出已求解的解，避免大量重復(fù)計(jì)算，節(jié)省時間。動態(tài)規(guī)劃用表格記錄所有已解決的子問題的答案。無論子問題將來是否被使用，只要它已經(jīng)被計(jì)算，結(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)到下一個階段的選擇。特點(diǎn)：前一階段的終點(diǎn)是后一階段的起點(diǎn)，前一階段的決定影響后一階段的狀態(tài)。4.策略：一個決策序列，由從開始到結(jié)束的整個過程中的每個決策組成。動態(tài)編程中的概念和術(shù)語(2)，5。狀態(tài)轉(zhuǎn)移方程：描述狀態(tài)從K階段到k 1階段的演化規(guī)律的方程稱為狀態(tài)轉(zhuǎn)移方程(用數(shù)學(xué)形式表示)。6.目標(biāo)函數(shù)和優(yōu)化概念：目標(biāo)函數(shù)是衡量多階段決策過程優(yōu)劣的標(biāo)準(zhǔn)。優(yōu)化的概念是在一定的條件下找到一種方法，根據(jù)課題的具體性質(zhì)確定操作后，使整個過程的總效益達(dá)到最佳。7.動態(tài)規(guī)劃：在多階段決策問題中，每個階段做出的決策取決

9、于當(dāng)前狀態(tài)，并導(dǎo)致狀態(tài)轉(zhuǎn)換，以獲得最佳過程。最佳原則優(yōu)化策略的子策略總是最佳的。1.找出最優(yōu)解的性質(zhì)并描述其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值(寫動態(tài)規(guī)劃方程)3。自下而上(或自上而下)計(jì)算最佳值4。根據(jù)計(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ī)劃方法，所有子問題都計(jì)算一次，沒有遞歸代價。程序(下頁)，空矩陣鏈(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)：當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，表示該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。如何解釋問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)？使用反

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

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

13、個已解決的子問題建立備忘錄，以便在必要時查看，從而避免重復(fù)解決同一個子問題。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è)和計(jì)

14、算機(jī)問題，1。分析問題3-1，實(shí)現(xiàn)問題3-4(數(shù)字三角形)2。(補(bǔ)充)讓A、B、C、D、E和F分別為5010、103、312、125 3。分析問題3-3，實(shí)現(xiàn)問題3-2(編輯距離)，3-6(游輪問題)，3-13(最大k產(chǎn)品)，實(shí)現(xiàn)3-7(汽車加油)。第四周上機(jī)：修改3.1節(jié)的算法，找出計(jì)算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。在抄寫手稿之前，人們依靠抄寫員抄寫書籍。有一次，一家劇院想排練一出戲，希望能復(fù)制一份劇本。眾所周知，劇本由M卷組成，每卷都有pi頁(1=i=m)。使用k個抄寫員(1千米)，每個抄寫員只能被分配一個任務(wù)，即復(fù)制幾個連續(xù)的手稿。假設(shè)每個抄寫員都有相同的復(fù)印速度。完成任務(wù)所需的總時間由工作量最大的抄寫員決定，即抄寫員要復(fù)制的總頁數(shù)。找到一個分配方案，以盡量減少完成任務(wù)所需的總時間。輸入整數(shù)m和K.然后輸入m個整數(shù)p1、p2、p3、pm，用空格隔開。輸出完成任務(wù)所需的最短總時間。讓Fij成為第一批抄寫第一批j冊的人的最短完成時間。檢查第三個人的復(fù)制情況。讓我們假設(shè)第一批T書是由第一批i-1人復(fù)制的，第一批t 1、t 2和J書是由第一