王曉東《算法設(shè)計(jì)與分析》課件

1,中國計(jì)算機(jī)學(xué)會(huì)“21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材”算法設(shè)計(jì)與分析,王曉東編著,2,主要內(nèi)容介紹,第1章算法引論 第2章遞歸與分治策略 第3章動(dòng)態(tài)規(guī)劃 第4章貪心算法 第5章回溯法 第6章分支限界法,3,主要內(nèi)容介紹（續(xù)）,第7章概率算法 第8章NP完全性理論 第9章近似算法 第10章算法優(yōu)化策略,4,第1章 算法引論,1.1算法與程序 1.2表達(dá)算法的抽象機(jī)制 1.3描述算法 1.4算法復(fù)雜性分析,本章主要知識(shí)點(diǎn)：,5,1.1算法與程序,輸 入：有零個(gè)或多個(gè)外部量作為算法的輸入。 輸 出：算法產(chǎn)生至少一個(gè)量作為輸出。 確定性：組成算法的每條指令清晰、無歧義。 有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。,是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。 程序可以不滿足算法的性質(zhì)(4)即有限性。,是滿足下述性質(zhì)的指令序列。,算法：,程序：,6,1.從機(jī)器語言到高級(jí)語言的抽象,1.2表達(dá)算法的抽象機(jī)制,高級(jí)程序設(shè)計(jì)語言的主要好處是：,（4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開發(fā)周期短，程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。,（1）高級(jí)語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需 要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；,（2）高級(jí)語言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；,（3）高級(jí)語言不依賴于機(jī)器語言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫出來的程序可植性好、重用率高；,7,2.抽象數(shù)據(jù)類型,1.2表達(dá)算法的抽象機(jī)制,抽象數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上 并作為算法構(gòu)件的一組運(yùn)算。,抽象數(shù)據(jù)類型帶給算法設(shè)計(jì)的好處有：,（1）算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離； （2）算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇； （3）數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便于空間和時(shí)間耗費(fèi)的折衷； （4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性； （5）算法自然呈現(xiàn)模塊化； （6）為自頂向下逐步求精和模塊化提供有效途徑和工具； （7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。,8,在本書中，采用Java語言描述算法。 1.Java程序結(jié)構(gòu),1.3描述算法,以下，對Java語言的若干重要特性作簡要概述。,（1）Java程序的兩種類型：應(yīng)用程序和applet 區(qū)別：應(yīng)用程序的主方法為main，其可在命令行中用命令 語句 java 應(yīng)用程序名 來執(zhí)行； applet的主方法為init，其必須嵌入HTML文件，由 Web瀏覽器或applet閱讀器來執(zhí)行。,（2）包：java程序和類可以包(packages)的形式組織管理。,（3）import語句：在java程序中可用import語句加載所需的包。 例如，import java.io.*;語句加載java.io包。,9,1.3描述算法,2.Java數(shù)據(jù)類型,Java對兩種數(shù)據(jù)類型的不同處理方式：,s = new String(“Welcome”); String s = new String(“Welcome”);,10,1.3描述算法,表格1-1 Java基本數(shù)據(jù)類型,11,1.3描述算法,3.方法,在Java中，執(zhí)行特定任務(wù)的函數(shù)或過程統(tǒng)稱為方法(methods) 。 例如，java的Math類給出的常見數(shù)學(xué)計(jì)算的方法如下表所示：,12,1.3描述算法,3.方法,計(jì)算表達(dá)式 值的自定義方法ab描述如下：,public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; ,（1）方法參數(shù)：Java中所有方法的參數(shù)均為值參數(shù)。上述方法ab中，a和b是形式參數(shù)，在調(diào)用方法時(shí)通過實(shí)際參數(shù)賦值。,（2）方法重載：Java允許方法重載，即允許定義有不同簽名的同名方法。 上述方法ab可重載為：,public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; ,13,1.3描述算法,4.異常,Java的異常提供了一種處理錯(cuò)誤的方法。當(dāng)程序發(fā)現(xiàn)一個(gè)錯(cuò)誤，就引發(fā)一個(gè)異常，以便在合適地方捕獲異常并進(jìn)行處理。,通常用try塊來定義異常處理。每個(gè)異常處理由一個(gè)catch語句組成。,public static void main(String args) try f ( ); catch (exception1) 異常處理; catch (exception2) 異常處理; finally finally塊; ,14,1.3描述算法,5.Java的類,(4)訪問修飾,Java的類一般由4個(gè)部分組成：,(1)類名,(2)數(shù)據(jù)成員,(3)方法,15,1.3描述算法,6.通用方法,下面的方法swap用于交換一維整型數(shù)組a的位置i和位置j處的值。,public static void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; ,public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; ,該方法只適用于 整型數(shù)組,該方法具有通用性，適用于Object類型及其所有子類,以上方法修改如下：,16,1.3描述算法,6.通用方法,（1）Computable界面,public static Computable sum(Computable a, int n) if (a.length = 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i < n; i+) sum.increment(ai); return sum; ,利用此界面使 方法sum通用化,17,1.3描述算法,6.通用方法,（2）java.lang.Comparable 界面,Java的Comparable 界面中惟一的方法頭compareTo用于比較 2個(gè)元素的大小。例如java.lang.CpareTo(y) 返回x-y的符號(hào)，當(dāng)xy時(shí)返 回正數(shù)。,（3）Operable 界面,有些通用方法同時(shí)需要Computable界面和Comparable 界面 的支持。為此可定義Operable界面如下:,public interface Operable extends Computable, Comparable ,（4）自定義包裝類,由于Java的包裝類如Integer等已定義為final型，因此無法 定義其子類，作進(jìn)一步擴(kuò)充。為了需要可自定義包裝類。,18,1.3描述算法,7.垃圾收集 8.遞歸,Java的new運(yùn)算用于分配所需的內(nèi)存空間。 例如， int a = new int500000; 分配2000000字節(jié)空間 給整型數(shù)組a。頻繁用new分配空間可能會(huì)耗盡內(nèi)存。Java的垃 圾收集器會(huì)適時(shí)掃描內(nèi)存，回收不用的空間（垃圾）給new重新 分配。,Java允許方法調(diào)用其自身。這類方法稱為遞歸方法。,public static int sum(int a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); ,計(jì)算一維整型數(shù)組前n個(gè)元素之和的遞歸方法,19,1.4算法復(fù)雜性分析,算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量， 需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的 量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問 題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用 N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法 本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。 一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來 表示，則有： T=T(N,I)和S=S(N,I) 。 （通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）,20,1.4算法復(fù)雜性分析,最壞情況下的時(shí)間復(fù)雜性：,最好情況下的時(shí)間復(fù)雜性：,平均情況下的時(shí)間復(fù)雜性：,其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N, I*) 達(dá)到Tmax(N)的合法輸入； 是中使T(N, )達(dá)到Tmin(N)的合法 輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。,21,1.4算法復(fù)雜性分析,算法復(fù)雜性在漸近意義下的階：,漸近意義下的記號(hào)：O、o 設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。,O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N)。即f(N)的階不高于g(N)的階。,根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則： (1)O(f)+O(g)=O(max(f,g)； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N)，則O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一個(gè)正的常數(shù)； (6)f=O(f)。,22,1.4算法復(fù)雜性分析,的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí) 有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是它 的一個(gè)下界，記為f(N)=(g(N)。即f(N)的階不低于g(N)的階。,的定義：定義f(N)= (g(N)當(dāng)且僅當(dāng)f(N)=O(g(N)且 f(N)= (g(N)。此時(shí)稱f(N)與g(N)同階。,o的定義：對于任意給定的0，都存在正整數(shù)N0，使得 當(dāng)NN0時(shí)有f(N)/Cg(N),則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比 g(N)低，記為f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。,23,第2章 遞歸與分治策略,24,將要求解的較大規(guī)模的問題分割成k個(gè)更小規(guī)模的子問題。,算法總體思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。,25,算法總體思想,對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。,n,T(n),=,將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。,26,算法總體思想,將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。,n,T(n),=,27,算法總體思想,將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。,分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題， 分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破， 分而治之。 凡治眾如治寡，分?jǐn)?shù)是也。 -孫子兵法,28,2.1 遞歸的概念,直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。,下面來看幾個(gè)實(shí)例。,29,2.1 遞歸的概念,例1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為：,邊界條件,遞歸方程,邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。,30,2.1 遞歸的概念,例2 Fibonacci數(shù)列 無窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：,邊界條件,遞歸方程,第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下： public static int fibonacci(int n) if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,31,32,2.1 遞歸的概念,例3 Ackerman函數(shù) 當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。 Ackerman函數(shù)A(n，m)定義如下：,33,2.1 遞歸的概念,例3 Ackerman函數(shù) 前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義：,但本例中的Ackerman函數(shù)卻無法找到非遞歸的定義。,34,2.1 遞歸的概念,例3 Ackerman函數(shù) A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)： M=0時(shí)，A(n,0)=n+2 M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。 M=3時(shí)，類似的可以推出 M=4時(shí)，A(n,4)的增長速度非?？欤灾劣跊]有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。,35,2.1 遞歸的概念,例3 Ackerman函數(shù) 定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。 定義其擬逆函數(shù)(n)為：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。 (n)在復(fù)雜度分析中常遇到。對于通常所見到的正整數(shù)n，有(n)4。但在理論上(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。,36,2.1 遞歸的概念,例4 排列問題 設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。,設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。 集合X中元素的全排列記為perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：,當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素； 當(dāng)n1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。,37,2.1 遞歸的概念,例5 整數(shù)劃分問題 將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk， 其中n1n2nk1，k1。 正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不 同劃分個(gè)數(shù)。 例如正整數(shù)6有如下11種不同的劃分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,38,(2) q(n,m)=q(n,n),mn; 最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。,(1) q(n,1)=1,n1; 當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式， 即,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和 n1n-1 的劃分組成。,(3) q(n,n)=1+q(n,n-1); 正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。,2.1 遞歸的概念,例5 整數(shù)劃分問題 前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。,39,2.1 遞歸的概念,例5 整數(shù)劃分問題 前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。,正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。,40,41,2.1 遞歸的概念,例6 Hanoi塔問題 設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則： 規(guī)則1：每次只能移動(dòng)1個(gè)圓盤； 規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。,42,在問題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個(gè)問題。,當(dāng)n=1時(shí)，問題比較簡單。此時(shí)，只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。 當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座c移至塔座b。 由此可見，n個(gè)圓盤的移動(dòng)問題可分為2次n-1個(gè)圓盤的移動(dòng)問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計(jì)出解Hanoi塔問題的遞歸算法如下。,2.1 遞歸的概念,例6 Hanoi塔問題,public static void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); ,思考題：如果塔的個(gè)數(shù)變?yōu)閍,b,c,d四個(gè)，現(xiàn)要將n個(gè)圓盤從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。,43,遞歸小結(jié),優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。 缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。,44,遞歸小結(jié),解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。 1.采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 2.用遞推來實(shí)現(xiàn)遞歸函數(shù)。 3.通過Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。,45,分治法的適用條件,分治法所能解決的問題一般具有以下幾個(gè)特征： 該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 利用該問題分解出的子問題的解可以合并為該問題的解； 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。,因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個(gè)特征。,這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用,能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。,這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。,46,分治法的基本步驟,divide-and-conquer(P) if ( | P | <= n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i<=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。即將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。,47,分治法的復(fù)雜性分析,一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有：,通過迭代法求得方程的解：,注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)min<mi+1時(shí)，T(mi)T(n)<T(mi+1)。,48,二分搜索技術(shù),分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問題滿足分治法的第一個(gè)適用條件,分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個(gè)和第三個(gè)適用條件。,分析：很顯然此問題分解出的子問題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個(gè)適用條件。,給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。 分析：,該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個(gè)規(guī)模較小的相同問題; 分解出的子問題的解可以合并為原問題的解； 分解出的各個(gè)子問題是相互獨(dú)立的。,49,二分搜索技術(shù),給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。,據(jù)此容易設(shè)計(jì)出二分搜索算法： public static int binarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x ,算法復(fù)雜度分析： 每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。,思考題：給定a，用二分法設(shè)計(jì)出求an的算法。,50,大整數(shù)的乘法,請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算,小學(xué)的方法：O(n2) 效率太低 分治法:,a,b,c,d,復(fù)雜度分析 T(n)=O(n2) 沒有改進(jìn),X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd,51,大整數(shù)的乘法,請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算,小學(xué)的方法：O(n2) 效率太低 分治法:,XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd,復(fù)雜度分析 T(n)=O(nlog3) =O(n1.59)較大的改進(jìn),細(xì)節(jié)問題：兩個(gè)XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。,52,大整數(shù)的乘法,請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算,小學(xué)的方法：O(n2) 效率太低 分治法: O(n1.59) 較大的改進(jìn) 更快的方法?,如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時(shí)間內(nèi)解決。 是否能找到線性時(shí)間的算法？目前為止還沒有結(jié)果。,53,Strassen矩陣乘法,A和B的乘積矩陣C中的元素Ci,j定義為:,若依此定義來計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素Cij，需要做n次乘法和n-1次加法。因此，算出矩陣C的 個(gè)元素所需的計(jì)算時(shí)間為O(n3),傳統(tǒng)方法：O(n3),54,Strassen矩陣乘法,使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫為：,傳統(tǒng)方法：O(n3) 分治法:,由此可得：,復(fù)雜度分析 T(n)=O(n3) 沒有改進(jìn),55,Strassen矩陣乘法,傳統(tǒng)方法：O(n3) 分治法:,為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。,復(fù)雜度分析 T(n)=O(nlog7) =O(n2.81)較大的改進(jìn),56,Strassen矩陣乘法,傳統(tǒng)方法：O(n3) 分治法: O(n2.81) 更快的方法?,Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。 在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是 O(n2.376) 是否能找到O(n2)的算法？目前為止還沒有結(jié)果。,57,棋盤覆蓋,在一個(gè)2k2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。,58,棋盤覆蓋,當(dāng)k0時(shí)，將2k2k棋盤分割為4個(gè)2k-12k-1 子棋盤(a)所示。 特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無特殊方格。為了將這3個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤11。,59,棋盤覆蓋,public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr = tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號(hào)L型骨牌覆蓋左下角,boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤 if (dr = tr + s ,復(fù)雜度分析 T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法,60,合并排序,基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。,public static void mergeSort(Comparable a, int left, int right) if (left<right) /至少有2個(gè)元素 int i=(left+right)/2; /取中點(diǎn) mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到數(shù)組b copy(a, b, left, right); /復(fù)制回?cái)?shù)組a ,復(fù)雜度分析 T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法,61,合并排序,算法mergeSort的遞歸過程可以消去。,62,合并排序,最壞時(shí)間復(fù)雜度：O(nlogn) 平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：O(n) 穩(wěn)定性：穩(wěn)定,思考題：給定有序表A1:n，修改合并排序算法，求出該有序表的逆序?qū)?shù)。,63,快速排序,在快速排序中，記錄的比較和交換是從兩端向中間 進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單 元，關(guān)鍵字較小的記錄一次就能交換到前面單元， 記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次 數(shù)較少。,private static void qSort(int p, int r) if (p<r) int q=partition(p,r); /以ap為基準(zhǔn)元素將ap:r劃分成3段ap:q-1,aq和aq+1:r，使得ap:q-1中任何元素小于等于aq，aq+1:r中任何元素大于等于aq。下標(biāo)q在劃分過程中確定。 qSort (p,q-1); /對左半段排序 qSort (q+1,r); /對右半段排序 ,快速排序是對氣泡排序的一種改進(jìn)方法 它是由C.A.R. Hoare于1962年提出的,64,快速排序,private static int partition (int p, int r) int i = p, j = r + 1; Comparable x = ap; / 將= x的元素交換到左邊區(qū)域 / 將 0); if (i = j) break; MyMath.swap(a, i, j); ap = aj; aj = x; return j; ,初始序列,j-;,5, 7, 5, 2, 6, 8,i+;,5, 6, 5, 2, 7, 8,j-;,5, 2, 5, 6, 7, 8,i+;,完成,5, 2, 5 6 7, 8,65,private static int randomizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); ,快速排序,快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對稱的。,最壞時(shí)間復(fù)雜度：O(n2) 平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：O(n)或O(logn) 穩(wěn)定性：不穩(wěn)定,66,線性時(shí)間選擇,給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素,private static Comparable randomizedSelect(int p,int r,int k) if (p=r) return ap; int i=randomizedpartition(p,r), j=i-p+1; if (k<=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); ,在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間 但可以證明，算法randomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。,67,線性時(shí)間選擇,如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長度都至少為原數(shù)組長度的倍(0<<1是某個(gè)正常數(shù))，那么就可以在最壞情況下用O(n)時(shí)間完成選擇任務(wù)。,例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。,68,將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。 遞歸調(diào)用select來找出這n/5個(gè)元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。,線性時(shí)間選擇,設(shè)所有元素互不相同。在這種情況下，找出的基準(zhǔn)x至少比3(n-5)/10個(gè)元素大，因?yàn)樵诿恳唤M中有2個(gè)元素小于本組的中位數(shù)，而n/5個(gè)中位數(shù)中又有(n-5)/10個(gè)小于基準(zhǔn)x。同理，基準(zhǔn)x也至少比3(n-5)/10個(gè)元素小。而當(dāng)n75時(shí)，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長度都至少縮短1/4。,69,private static Comparable select (int p, int r, int k) if (r-p<5) /用某個(gè)簡單排序算法對數(shù)組ap:r排序; bubbleSort(p,r); return ap+k-1; /將ap+5*i至ap+5*i+4的第3小元素 /與ap+i交換位置; /找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5 for ( int i = 0; i<=(r-p-4)/5; i+ ) int s=p+5*i, t=s+4; for (int j=0;j<3;j+) bubble(s,t-j); MyMath.swap(a, p+i, s+2); Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10); int i=partition(p,r,x), j=i-p+1; if (k<=j) return select(p,i,k); else return select(i+1,r,k-j); ,復(fù)雜度分析 T(n)=O(n),上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n/5+3n/4=19n/20=n，0<<1。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。,70,最接近點(diǎn)對問題,給定平面上n個(gè)點(diǎn)的集合S，找其中的一對點(diǎn)，使得在n個(gè)點(diǎn)組成的所有點(diǎn)對中，該點(diǎn)對間的距離最小。,71,最接近點(diǎn)對問題,如果S的最接近點(diǎn)對是p3,q3，即|p3-q3|<d，則p3和q3兩者與m的距離不超過d，即p3(m-d,m，q3(m,m+d。 由于在S1中，每個(gè)長度為d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于d），并且m是S1和S2的分割點(diǎn)，因此(m-d,m中至多包含S中的一個(gè)點(diǎn)。由圖可以看出，如果(m-d,m中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。 因此，我們用線性時(shí)間就能找到區(qū)間(m-d,m和(m,m+d中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。,能否在線性時(shí)間內(nèi)找到p3,q3？,72,最接近點(diǎn)對問題,下面來考慮二維的情形。,選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。 遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，S中的最接近點(diǎn)對或者是d，或者是某個(gè)p,q，其中pP1且qP2。 能否在線性時(shí)間內(nèi)找到p,q？,73,最接近點(diǎn)對問題,考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選者，則必有distance(p，q)d。滿足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)d2d的矩形R中 由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推出矩形R中最多只有6個(gè)S中的點(diǎn)。 因此，在分治法的合并步驟中最多只需要檢查6n/2=3n個(gè)候選者,能否在線性時(shí)間內(nèi)找到p3,q3？,證明:將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導(dǎo)出6個(gè)(d/2)(2d/3)的矩形。若矩形R中有多于6個(gè)S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè)(d/2)(2d/3)的小矩形中有2個(gè)以上S中的點(diǎn)。設(shè)u，v是位于同一小矩形中的2個(gè)點(diǎn)，則 distance(u,v)<d。這與d的意義相矛盾。,74,為了確切地知道要檢查哪6個(gè)點(diǎn)，可以將p和P2中所有S2的點(diǎn)投影到垂直線l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者的S2中點(diǎn)一定在矩形R中，所以它們在直線l上的投影點(diǎn)距p在l上投影點(diǎn)的距離小于d。由上面的分析可知，這種投影點(diǎn)最多只有6個(gè)。 因此，若將P1和P2中所有S中點(diǎn)按其y坐標(biāo)排好序，則對P1中所有點(diǎn)，對排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對的候選者。對P1中每一點(diǎn)最多只要檢查P2中排好序的相繼6個(gè)點(diǎn)。,最接近點(diǎn)對問題,75,最接近點(diǎn)對問題,public static double cpair2(S) n=|S|; if (n m 2. d1=cpair2(S1); d2=cpair2(S2); 3. dm=min(d1,d2);,4. 設(shè)P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點(diǎn)組成的集合； P2是S2中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合； 將P1和P2中點(diǎn)依其y坐標(biāo)值排序； 并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列； 5. 通過掃描X以及對于X中每個(gè)點(diǎn)檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)(最多6個(gè))可以完成合并； 當(dāng)X中的掃描指針逐次向上移動(dòng)時(shí)，Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動(dòng)； 設(shè)dl是按這種掃描方式找到的點(diǎn)對間的最小距離； 6. d=min(dm,dl); return d; ,復(fù)雜度分析 T(n)=O(nlogn),76,設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行n-1天。,按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。,77,循環(huán)賽日程表,設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行n-1天。,按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。,78,第3章 動(dòng)態(tài)規(guī)劃,79,動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題,80,算法總體思想,動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題,81,但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。,算法總體思想,82,如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。,算法總體思想,T(n),Those who cannot remember the past are doomed to repeat it. -George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),83,動(dòng)態(tài)規(guī)劃基本步驟,找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。,84,完全加括號(hào)的矩陣連乘積,（1）單個(gè)矩陣是完全加括號(hào)的； （2）矩陣連乘積 是完全加括號(hào)的，則 可 表示為2個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào)，即,16000, 10500, 36000, 87500, 34500,完全加括號(hào)的矩陣連乘積可遞歸地定義為： 設(shè)有四個(gè)矩陣 ，它們的維數(shù)分別是： 總共有五中完全加括號(hào)的方式,85,矩陣連乘問題,給定n個(gè)矩陣 ， 其中 與 是可乘的， ?？疾爝@n個(gè)矩陣的連乘積 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。 若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,86,矩陣連乘問題,給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2 ,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。,窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。,算法復(fù)雜度分析： 對于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：,87,矩陣連乘問題,窮舉法 動(dòng)態(tài)規(guī)劃,將矩陣連乘積 簡記為Ai:j ，這里ij,考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和Ak+1之間將矩陣鏈斷開，ik<j，則其相應(yīng)完全 加括號(hào)方式為,計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上 Ai:k和Ak+1:j相乘的計(jì)算量,88,分析最優(yōu)解的結(jié)構(gòu),特征：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。 矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。,89,建立遞歸關(guān)系,設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n 當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,n 當(dāng)i<j時(shí)， 可以遞歸地定義mi,j為：,這里 的維數(shù)為,的位置只有 種可能,90,計(jì)算最優(yōu)值,對于1ijn不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有 由此可見，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。 用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法,91,用動(dòng)態(tài)規(guī)劃法求最優(yōu)解,public static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i <= n; i+) mii = 0; for (int r = 2; r <= n; r+) for (int i = 1; i <= n - r+1; 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; if (t < mij) mij = t; sij = k; ,算法復(fù)雜度分析： 算法matrixChain的主要計(jì)算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。,92,動(dòng)態(tài)規(guī)劃算法的基本要素,一、最優(yōu)子結(jié)構(gòu),矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。 在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。,注意：同一個(gè)問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）,93,二、重疊子問題,遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。 動(dòng)態(tài)規(guī)劃算法，對每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡單地用常數(shù)時(shí)間查看一下結(jié)果。 通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。,94,三、備忘錄方法,備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。,m0 private static int lookupChain(int i, int j) if (mij 0) return mij; if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k < j; k+) int t = lookupChain(i,k) + lookupChain(k+1,j) + pi-1*pk*pj; if (t < u) u = t; sij = k; mij = u; return u; ,95,最長公共子序列,若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。 給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。 給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。,96,最長公共子序列的結(jié)構(gòu),設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則 (1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。 (2)若xmyn且zkxm，則Z是xm-1和Y的最長公共子序列。 (3)若xmyn且zkyn，則Z是X和yn-1的最長公共子序列。,由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,97,子問題的遞歸結(jié)構(gòu),由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)Cij=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：