算法設(shè)計(jì)技巧與分析 第7章 動(dòng)態(tài)規(guī)劃.ppt

《算法設(shè)計(jì)技巧與分析 第7章 動(dòng)態(tài)規(guī)劃.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、算法設(shè)計(jì)技巧與分析AlgorithmsDesignTechniquesandAnalysis南方醫(yī)科大學(xué)醫(yī)工學(xué)院信息技術(shù)系第7章動(dòng)態(tài)規(guī)劃理解動(dòng)態(tài)規(guī)劃的基本原理掌握動(dòng)態(tài)規(guī)劃的算法實(shí)例（難點(diǎn)）掌握用動(dòng)態(tài)規(guī)劃設(shè)計(jì)算法的方法（重點(diǎn)）TeachingRequestContent動(dòng)態(tài)規(guī)劃原理算法實(shí)例最長(zhǎng)公共子序列問(wèn)題矩陣鏈相乘最短路徑問(wèn)題0-1背包問(wèn)題動(dòng)態(tài)規(guī)劃范式1n=0f(n)=1n=1f(n-1)+f(n-2)n>1F(4)F(3)F(2)F(2)F(1)F(1)F(0)FibonacciSerialProblemRecursionForm算法過(guò)程：1.proceduref(n)

2、2.if(n=1)or(n=2)thenreturn13.elsereturnf(n-1)+f(n-2)時(shí)間復(fù)雜性：1若n=1或n=2若n≥3DynamicProgrammingForm計(jì)算過(guò)程：從f1開(kāi)始，自底向上計(jì)算到fn。時(shí)間復(fù)雜性：Θ(n)空間復(fù)雜性：Θ(1)DynamicProgrammingPrinciple將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，再由子問(wèn)題的解得到原問(wèn)題的解。DifferencebetweenDCandDP都是分解成子問(wèn)題，由子問(wèn)題的解得到原問(wèn)題的解。分治中子問(wèn)題相互獨(dú)立，而動(dòng)態(tài)規(guī)劃中子問(wèn)題互相

3、有聯(lián)系，且存在重復(fù)計(jì)算，即存在重疊子問(wèn)題。7.2LongestCommonSerialProblem:給出兩個(gè)長(zhǎng)度為n和m的字符串A和B，A=a1a2…an，B=b1b2…bm，確定在A和B中最長(zhǎng)公共子序列的長(zhǎng)度。Example:若A=zxyxyz，B=xyyzx，則A和B的最長(zhǎng)公共子序列為xyyz，其長(zhǎng)度為4。令L[i,j]表示a1a2…ai和b1b2…bj的最長(zhǎng)公共子序列的長(zhǎng)度，如果i和j都大于0，那么若ai=bj，L[i,j]=L[i-1,j-1]+1若ai≠bj，L[i,j]=max{L[i,j-1]，L[i-1,j]}觀察結(jié)論7.1若i=0或j=0若i>0,j>

4、0和ai=bj若i>0,j>0和ai≠bj算法7.1　LCS輸入:字母表上的兩個(gè)字符串A和B，長(zhǎng)度分別為n和m。輸出:A和B最長(zhǎng)公共了序列的長(zhǎng)度。1.fori←0ton2.L[i，0]←03.endfor4.forj←0tom5.L[0，j]←06.endfor7.fori←1ton8.forj←1tom9.ifthenL[i，j]←L[i-1，j-1]+110.elseL[i，j]←max{[i，j-1]，L[i-1，j]}11.endif12.endfor13.endfor14.returnL[n，m]定理7.1最長(zhǎng)公共子序列問(wèn)題的最優(yōu)解能夠在時(shí)間和空間內(nèi)得到。7.3

5、MatrixChain給定n個(gè)矩陣{A1,A2,…,An}，其中Ai是一個(gè)ri-1×ri矩陣(1≤i≤n)，即Ai×Ai+1是可乘的，求出n個(gè)矩陣相乘的最優(yōu)計(jì)算次序，使得計(jì)算量最小。BasePrinciple考查兩個(gè)矩陣相乘的情形：C=AB。如果矩陣A,B分別是p×r和r×q矩陣，則它們的乘積C將是p×q矩陣，其(i,j)元素為則共需要prq次數(shù)乘。BaseAlgorithmvoidMatrixMultiply(int**a,int**b,int**c,intra,intca,intrb,intcb){if(ca!=rb)error(“矩陣不可乘”)；for(inti=0

6、;i

7、Bracket矩陣相乘滿足結(jié)合律，連乘積可以有許多不同的次序，可以用加括號(hào)的方式確定。設(shè)三個(gè)矩陣A1,A2,A3大小分別為2×10，10×2，2×10，考慮(A1(A2A3)),(A1A2)A3)的結(jié)果與相乘的次數(shù)。對(duì)于n個(gè)矩陣的連乘積，設(shè)有f(n)個(gè)計(jì)算次序。我們可以在第k個(gè)和第k＋1個(gè)矩陣之間將原矩陣劃分為兩個(gè)子矩陣序列，則：Catalan其中f(n)=C(n-1)，AnalyzethestructureoftheOptimizationResult設(shè)M[i:j]為矩陣連乘積MiMi+1···Mj。計(jì)算M[1:n]的最優(yōu)次