1、算法設(shè)計(jì)分析,算法設(shè)計(jì)與分析復(fù)習(xí)總結(jié),算法設(shè)計(jì)分析,算法設(shè)計(jì)與分析課程是計(jì)算機(jī)專業(yè)本科的專業(yè)必修課。 這是一門面向設(shè)計(jì)的課程。 設(shè)立本課程的是為了適應(yīng)21世紀(jì)我國(guó)計(jì)算機(jī)科學(xué)技術(shù)及軟件工程人才培養(yǎng)的需要，培養(yǎng)學(xué)生設(shè)計(jì)和分析算法的能力。 通過學(xué)習(xí)本課程，應(yīng)該掌握計(jì)算機(jī)軟件常用的幾種算法。并可以對(duì)算法的復(fù)雜性進(jìn)行分析，從而能夠在實(shí)際工作中根據(jù)具體問題設(shè)計(jì)和優(yōu)化算法。,算法設(shè)計(jì)分析,算法設(shè)計(jì)分析正是一種面向設(shè)計(jì)，且處于計(jì)算機(jī)學(xué)科核心地位的教育課程。通過對(duì)計(jì)算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究。 掌握算法設(shè)計(jì)的主要方法。 培養(yǎng)對(duì)算法的計(jì)算復(fù)雜性正確分析的能力。 為獨(dú)立設(shè)計(jì)算法和對(duì)算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)

2、。 這對(duì)每一位從事計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件研究與開發(fā)的科技工作者都是非常重要和必不可少的。,算法設(shè)計(jì)分析,第一章 算法引論,一、學(xué)習(xí)要求 通過本章的學(xué)習(xí)，要求了解該課程的基本框架，理解算法的概念，如何來(lái)表達(dá)算法，同時(shí)還簡(jiǎn)要介紹如何使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)描述算法。 本章要了解算法與程序的區(qū)別，算法在計(jì)算機(jī)及軟件領(lǐng)域的作用和地位，理解使用抽象數(shù)據(jù)來(lái)表達(dá)算法，重點(diǎn)掌握如何使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)描述算法。 二、課程內(nèi)容 1算法的基本概念 2表達(dá)算法的抽象機(jī)制 3使用語(yǔ)言來(lái)描述算法 4算法的復(fù)雜性分析,算法設(shè)計(jì)分析,1.1算法特性,概括起來(lái)，算法有以下幾個(gè)特性：1確定性；2可實(shí)現(xiàn)性；3具有

3、數(shù)據(jù)輸入； 4具有數(shù)據(jù)輸出； 5有窮性。,算法設(shè)計(jì)分析,例：選擇題：下面對(duì)算法描述正確的一項(xiàng)是：(C ) A. 算法只能用自然語(yǔ)言來(lái)描述 B. 算法只能用圖形方式來(lái)表示 C. 同一問題可以有不同的算法 D. 同一問題的算法不同，結(jié)果必然不同,算法設(shè)計(jì)分析,程序與算法不同。 程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)4 。 例如操作系統(tǒng)，它是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。 然而我們可把操作系統(tǒng)的各種任務(wù)看成是一些單獨(dú)的問題，每一個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。,算法設(shè)計(jì)分析,算法指的是（B） A計(jì)算程序 B.

4、 解決問題的計(jì)算方法 C. 排序算法 D. 解決問題的有限運(yùn)算序列 計(jì)算機(jī)算法指的是解決問題的計(jì)算方法。描述算法可以有多種方式，如自然語(yǔ)言方式和表格方式等。 算法的實(shí)現(xiàn)工具的是語(yǔ)言。算法是對(duì)方法和步驟的描述。,算法設(shè)計(jì)分析,下面對(duì)算法描述正確的一項(xiàng)是：( C ) A. 算法只能用自然語(yǔ)言來(lái)描述 B. 算法只能用圖形方式來(lái)表示 C. 同一問題可以有不同的算法 D. 同一問題的算法不同，結(jié)果必然不同,算法設(shè)計(jì)分析,對(duì)于算法的概念，不同的教材敘述方式不盡相同，以下是常見的幾種說法。 算法就是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算 ThomasH.Cormen等人在“Introdu

5、ctiontoAlgorithms”一書中將算法描述為：算法是任何定義好了的計(jì)算程式，它取某些值或值的集合作為輸入，并產(chǎn)生某些值或值的集合作為輸出。,算法設(shè)計(jì)分析,算法的下五個(gè)特性 : 輸出一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是同輸入有某種特定關(guān)系的量。 確定性算法的每一種運(yùn)算（包括判斷）必須要有確切的定義，即每一種運(yùn)算應(yīng)該執(zhí)行何種動(dòng)作必須是相當(dāng)清楚的、無(wú)二義性的。 有限性算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限，因此一個(gè)算法總是在執(zhí)行了有窮步之后終止。,算法設(shè)計(jì)分析,可實(shí)現(xiàn)性（或可行性）此性質(zhì)是指算法中有待實(shí)現(xiàn)的運(yùn)算都是相當(dāng)基本的，每種運(yùn)算至少在原理上能由人用紙和筆在有限的時(shí)間內(nèi)完

6、成。其中這一條也是最重要的，一個(gè)算法沒有可實(shí)現(xiàn)性也就失去了存在的價(jià)值。,算法設(shè)計(jì)分析,1.2 算法復(fù)雜性分析,程序性能是指運(yùn)行一個(gè)程序所需的內(nèi)存大小和時(shí)間多少。 程序的性能一般指程序的空間復(fù)雜性和時(shí)間復(fù)雜性。 性能評(píng)估主要包含兩方面，即性能分析與性能測(cè)量measurement)前者采用分析的方法，后者采用實(shí)驗(yàn)的方法。,算法設(shè)計(jì)分析,算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，這個(gè)量應(yīng)該只依賴于算法要解的問題的 規(guī)模 、 算法的輸入 和 算法本身的函數(shù) 。 算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要的空間資源的量稱為空間復(fù)雜性。(),算法設(shè)計(jì)分析,算法分析的兩個(gè)主要方面是：( A ) A.

7、 空間復(fù)雜性和時(shí)間復(fù)雜性 B. 正確性和簡(jiǎn)明性 C可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性,算法設(shè)計(jì)分析,考慮時(shí)間復(fù)雜性的理由,某些計(jì)算機(jī)用戶需要提供程序運(yùn)行時(shí)間的上限。 所開發(fā)的程序需要提供一個(gè)滿意的實(shí)時(shí)反應(yīng)。,算法設(shè)計(jì)分析,程序=算法+數(shù)據(jù)結(jié)構(gòu),軟件：刻畫現(xiàn)實(shí)世界，解決現(xiàn)實(shí)世界中的問題。 語(yǔ)言：實(shí)現(xiàn)的工具。 算法：解的描述數(shù)據(jù)結(jié)構(gòu)：現(xiàn)實(shí)世界的數(shù)據(jù)模型。 程序=算法+數(shù)據(jù)結(jié)構(gòu),算法設(shè)計(jì)分析,1.3 時(shí)間復(fù)雜性,時(shí)間復(fù)雜性的構(gòu)成： 一個(gè)程序所占時(shí)間T (P)編輯時(shí)間+運(yùn)行時(shí)間: 編譯時(shí)間與實(shí)例特征無(wú)關(guān)，而且，一般情況下，一個(gè)編譯過的程序運(yùn)行若干次，所以，人們主要關(guān)注的是運(yùn)行時(shí)間，記做T (

8、P)實(shí)例特征) 如果了解所用編輯器的特征，就可以確定代碼P進(jìn)行加、減、乘、除、比較、讀、寫等所需的時(shí)間，從而得到計(jì)算T (P)的公式。 令n代表實(shí)例特征(這里主要是問題的規(guī)模)，則有如下的表示式:,算法設(shè)計(jì)分析,一個(gè)操作所需的時(shí)間取決于操作數(shù)的類型(int, float, double等等)，所以，有必要對(duì)操作按照數(shù)據(jù)類型進(jìn)行分類; 在構(gòu)思一個(gè)程序時(shí)，影響時(shí)間的許多因素還是未知的，所以，在多數(shù)情況下僅僅是對(duì)t進(jìn)行估計(jì)。 估算運(yùn)行時(shí)間的方法: A.找一個(gè)或多個(gè)關(guān)鍵操作，確定這些關(guān)鍵操作 所需要的執(zhí)行時(shí)間(對(duì)于前面所列舉的四種算術(shù)運(yùn)算及比較操作，一般被看作是基本操作，并約定所用的時(shí)間都是一個(gè)單位)

9、。 B.確定程序總的執(zhí)行步數(shù)。,算法設(shè)計(jì)分析,三種情況下的時(shí)間復(fù)雜性,本書只考慮三種情況下的時(shí)間復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性 以上三種情況下的時(shí)間復(fù)雜性從不同角度來(lái)反映算法的效率，各有其局限性，也各有各的用處。 實(shí)踐表明可操作性最好且最有實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜性。 本書對(duì)算法的時(shí)間復(fù)雜性分析的重點(diǎn)將放在這種情形上。,算法設(shè)計(jì)分析,設(shè)三個(gè)函數(shù)f，g，h分別為f(n)=100n3+n2+1000，g(n)=25n3+5000n2，h(n)=n1.5+5000nlgn，請(qǐng)判斷下列關(guān)系不成立的是：( C ) A. f(n)=O(g(n) B. g(n)=O(f(n)

10、Ch(n)=O(f(n) D h(n)=O(nlgn),算法設(shè)計(jì)分析,設(shè)T(n)是算法A的復(fù)雜性函數(shù)。一般說來(lái)，當(dāng)n單調(diào)增加趨于時(shí)，T(n)也將單調(diào)增加趨于。如果存在函數(shù)T(n)，使得當(dāng)n時(shí)有(T(n)T(n)/T(n)0，則稱T(n)是T(n)當(dāng)n時(shí)的漸近性態(tài)，或稱T(n)是算法A當(dāng)n的漸近復(fù)雜性。 因?yàn)樵跀?shù)學(xué)上，T(n)是T(n)當(dāng)n時(shí)的漸近表達(dá)式，T(n)是T(n)中略去低階項(xiàng)所留下的主項(xiàng)，所以它無(wú)疑比T(n)來(lái)得簡(jiǎn)單。 進(jìn)一步分析可知，要比較兩個(gè)算法的漸近復(fù)雜性的階不相同時(shí)，只要確定出各自的階，就可以哪一個(gè)算法的效率高。 換句話說，漸近復(fù)雜性分析只要關(guān)心T(n)的階就夠了，不必關(guān)心包含

11、在T(n)中的常數(shù)因子。,算法設(shè)計(jì)分析,當(dāng)問題的規(guī)模n趨向無(wú)窮大時(shí)， B 的數(shù)量級(jí)(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度。 A.空間復(fù)雜度 B.時(shí)間復(fù)雜度 C.冗余度 D.迭代次數(shù),算法設(shè)計(jì)分析,簡(jiǎn)化算法復(fù)雜性分析的方法,簡(jiǎn)化算法復(fù)雜性分析的方法即是只考慮當(dāng)問題的規(guī)模充分大時(shí)，算法復(fù)雜性在漸近意義下的階。,算法設(shè)計(jì)分析,在下面的討論中，用f (n)表示一個(gè)程序的時(shí)間或空間復(fù)雜性，它是實(shí)例特征n(一般是輸入規(guī)模)的函數(shù)。 對(duì)于一個(gè)程序的時(shí)間或空間需求是一個(gè)非負(fù)的實(shí)數(shù)，我們假定函數(shù)f (n)對(duì)于n的所有取值均為非負(fù)實(shí)數(shù)，而且n=0,算法設(shè)計(jì)分析,漸近符號(hào)O的定義,用f(n)表示一個(gè)程序的時(shí)間或空間復(fù)雜性，

12、它是實(shí)例特征n（一般是輸入規(guī)模）的函數(shù)。 由于一個(gè)程序的時(shí)間或空間需求是一個(gè)非負(fù)的實(shí)數(shù)，我們假定函數(shù)f(n)對(duì)于n的所有取值均為非負(fù)實(shí)數(shù)，而且還可假定n=0。 f(n)=O(g(n)當(dāng)且僅當(dāng)存在正的常數(shù)c和n0，使得對(duì)于所有的n=n0，有f(n)=cg(n)。此時(shí)，稱g(n)是f(n)的一個(gè)上界。,算法設(shè)計(jì)分析,漸近符號(hào)O的定義的注意事項(xiàng),用來(lái)作比較的函數(shù)g(n)應(yīng)該盡量接近所考慮的函數(shù)f(n). 3n+2=O(n的2次方)松散的界限； 3n+2=O(n)較好的界限。,算法設(shè)計(jì)分析,通常用來(lái)表示時(shí)間算法的有以下六種多項(xiàng)式： 按從小到大的順序排列 ：,算法設(shè)計(jì)分析,f(n)=O(g(n)不能寫成

13、g(n)=O(f(n)，因?yàn)閮烧卟⒉坏葍r(jià)。 實(shí)際上，這里的等號(hào)并不是通常相等的含義。 按照定義，用集合符號(hào)更準(zhǔn)確些：O(g(n)=f(n)|f(n)滿足：存在正的常數(shù)c和n0，使得當(dāng)n=n0時(shí)，f(n)=cg(n) 所以，人們常常把f(n)=O(g(n)讀作：“f(n)是g(n)的一個(gè)大O成員”。,算法設(shè)計(jì)分析,的漸近表達(dá)式是 或 下面程序段的時(shí)間復(fù)雜度是 for (i=0; in; i+) for (j=0; jn; j+) Aij=0;,算法設(shè)計(jì)分析,符號(hào)的定義,f(n)=(g(n)當(dāng)且僅當(dāng)存在正的常數(shù)c和0n，使得對(duì)于所有的Onn，有f(n)c(g(n)。 此時(shí)，稱g(n)是f(n)的一

14、個(gè)下界。 函數(shù)f至少是函數(shù)g的c倍，除非Onn。 即是說，當(dāng)n充分大時(shí)，g是f 的一個(gè)下界函數(shù)，在相差一個(gè)非零常數(shù)倍的情況下。,算法設(shè)計(jì)分析,O有如下運(yùn)算性質(zhì),算法設(shè)計(jì)分析,例如： 如果 那么：,算法設(shè)計(jì)分析,漸近意義下的五個(gè)記號(hào)的區(qū)別：、和,設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。 （1）如果存在正的常數(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)。 這時(shí)我們還說f(N)的階不高于g(N)的階。,算法設(shè)計(jì)分析,（2）如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(N)，則稱函數(shù)f

15、(N)當(dāng)N充分大時(shí)下有界，且g(N)是它的一個(gè)下界，記為f(N)=(g(N)。 這時(shí)我們還說f(N)的階不低于g(N)的階。,算法設(shè)計(jì)分析,（3）定義f(N)=(g(N)則f(N)=(g(N)且f(N)=(g(N)。這時(shí)，我們說f(N)與g(N)同階。 （4）如果對(duì)于任意給定的0，都存在非負(fù)整數(shù)N0，使得當(dāng)NN0時(shí)有f(N)g(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)比g(N)低階，記為f(N)=o(g(N)。 （5）f(N)=(g(N)定義為g(N)=o(f(N)。,算法設(shè)計(jì)分析,例： 的漸近表達(dá)式是。 按照漸近階比較大小 ,算法設(shè)計(jì)分析,第二章 遞歸與分治策略,一、學(xué)習(xí)要求：通過本章的學(xué)習(xí)，要求

16、學(xué)生了解遞歸與分治的概念及相互關(guān)系，理解遞歸與分治算法策略的基本思想，掌握使用遞歸與分治策略解決經(jīng)典的問題，并對(duì)算法進(jìn)行復(fù)雜性分析。 二、課程內(nèi)容 1遞歸的概念 遞歸的含義 使用遞歸的方法解決實(shí)際的問題 階乘函數(shù)的遞歸表達(dá)式 Fabonacci數(shù)列的遞歸表達(dá)式 使用遞歸方法解決Hanoi塔問題,算法設(shè)計(jì)分析,2分治法的基本思想 分治的含義 分治算法的設(shè)計(jì)模式 分治法的效率分析 3分治策略應(yīng)用實(shí)例 二分搜索算法 大整數(shù)的乘法 Stassen矩陣乘法 棋盤覆蓋游戲 合并排序算法 快速排序算法,算法設(shè)計(jì)分析,分治法的設(shè)計(jì)思想,分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問

17、題，以便各個(gè)擊破，分而治之。如果原問題可分割成k個(gè)子問題，1k=n且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。,算法設(shè)計(jì)分析,由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。 在這種情況下反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終位子問題縮小到很容易求出其解。 這樣，就自然導(dǎo)致遞歸算法的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。,算法設(shè)計(jì)分析,分治法的設(shè)計(jì)思想是： 將一個(gè)難以直接解決的大規(guī)模問題，分割成些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之 。 二分搜索

18、算法是運(yùn)用分治策略的典型例子。 （對(duì)）,算法設(shè)計(jì)分析,21 遞歸的概念,直接或間接地調(diào)用自身的算法稱為遞歸算法。一個(gè)使用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 在計(jì)算機(jī)算法設(shè)計(jì)與分析中，使用遞歸技術(shù)他往使函數(shù)的定義和算法的簡(jiǎn)潔且易于理解。 有些數(shù)據(jù)結(jié)構(gòu)如二又樹等，由于其本身的遞歸特性、特別適合用遞歸的形式來(lái)描述。 還有一些問題，雖然其本身并沒有明顯的遞歸結(jié)構(gòu)但用遞歸技術(shù)來(lái)求解使設(shè)計(jì)出的算法簡(jiǎn)潔易懂且易于分析。,算法設(shè)計(jì)分析,遞歸策略的注意幾點(diǎn),一個(gè)遞歸定義必須是有確切合義的，也就是說，必須一步比一步簡(jiǎn)單，最后是有終結(jié)的，決不能無(wú)限循環(huán)下去。 在f(n)的定義中，當(dāng)n為0時(shí)定義一個(gè)已知數(shù)a，是最簡(jiǎn)

19、單的情況，稱為遞歸邊界，它本身不再使用遞歸的定義。,算法設(shè)計(jì)分析,有如下遞歸過程： void reverse (int m) printf(“%d”,n%10); if(n/10!=0)reverse(n/10); 調(diào)用語(yǔ)句reverse(687)的結(jié)果是_7 8 6,算法設(shè)計(jì)分析,與遞推一樣，每一個(gè)遞歸定義都有其邊界條件。但不同的是，遞推是內(nèi)邊界條件出發(fā)通過遞推式求f(n)的值t從邊界到求解的全過程十分清楚 而遞歸則是從函數(shù)本身出發(fā)來(lái)達(dá)到邊界條件。,算法設(shè)計(jì)分析,在通往邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果(局部變量和返回地址值)保存起來(lái)，直至求出遞歸邊界值f(0)a，然后

20、返回調(diào)用函數(shù)。,算法設(shè)計(jì)分析,返回過程中，中間結(jié)果相繼出?；謴?fù)，f(1)g(1，a)，f(2)g(2f(1),直至求出f(n)g(n，f(n1)。 由此可見，遞歸算法的效率往往很低，費(fèi)時(shí)和費(fèi)內(nèi)存空間。 但是遞歸也有其長(zhǎng)處，能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡(jiǎn)潔精煉，增加可讀性。 特別是在難于找到從邊界到解的全過程的情況下，如果把問題推進(jìn)一步，其結(jié)果仍維持原問題的關(guān)系，則采用遞歸算法編程比較合適。,算法設(shè)計(jì)分析,回溯法對(duì)解空間進(jìn)行深度優(yōu)先搜索，一般使用遞歸方法實(shí)現(xiàn)回溯法： void backtrack (int t) if (tn) output(x); else for (int i=f(n

21、, t); i=g(n,t); i+) xt=h(i); if (constraint(t) A. backtrack(t+1) B. backtrack(t-1) C. backtrack(t) D. backtrack(t+2),算法設(shè)計(jì)分析,遞歸按其調(diào)用方式分：直接遞歸遞歸過程P直接自己調(diào)用自己； 間接通歸：即P包含另一過程D，而D又調(diào)用 直接或間接的調(diào)用自身的算法稱為A。 A遞歸算法 B 貪心算法 C迭代算法 D動(dòng)態(tài)規(guī)劃算法,算法設(shè)計(jì)分析,階乘函數(shù)用遞歸定義 Public static int factorial(int n) if(n=0) return 1; return B ;

22、A n*factorial(n) B n*factorial(n-1) C n*factorial(n-2) D n*factorial(n+1),算法設(shè)計(jì)分析,遞歸算法的優(yōu)點(diǎn)是結(jié)構(gòu)清晰，可讀性強(qiáng)，運(yùn)行效率高。（錯(cuò)） 直接或間接地調(diào)用自身的算法稱為 遞歸算法 。,算法設(shè)計(jì)分析,遞歸算法適用的場(chǎng)合,數(shù)據(jù)的定義形式按遞歸定義。如裴波那契數(shù)列的定義：fn=fn-1+fn-2,iff0=1,f1=2.這類遞歸問題可轉(zhuǎn)化為遞推算法，遞歸邊界作為遞推的邊界條件 數(shù)據(jù)之間的關(guān)系(即數(shù)據(jù)結(jié)構(gòu))按遞歸定義。如樹的遍歷圖的搜索等 以及問題解法按遞歸算法實(shí)現(xiàn)。例如回溯法等,算法設(shè)計(jì)分析,遞歸算法不能適用以下場(chǎng)合（B

23、）。 A.數(shù)據(jù)的定義形式按遞歸定義 B.數(shù)據(jù)之間的關(guān)系(即數(shù)據(jù)結(jié)構(gòu))按遞歸定義 C.問題解法按遞歸算法實(shí) D.概率問題,算法設(shè)計(jì)分析,分治法與遞歸法的聯(lián)系與區(qū)別,有許多算法在結(jié)構(gòu)是遞歸的：為了解決一個(gè)給定問題，算法要一次或多次地調(diào)用其自身來(lái)解決相關(guān)的子問題。 這些算法通常采用分治策略：將原問題分成n個(gè)規(guī)模較小而結(jié)構(gòu)結(jié)原問題相似的子問題。 遞歸地解這些子問題，然后合并其結(jié)果就得到原問題的解。 n2時(shí)的分治法又稱二分法。,算法設(shè)計(jì)分析,用分治法求解一個(gè)問題，所需的時(shí)間是由子問題的個(gè)數(shù)，大小以及把這個(gè)問題分解為子問題所需的工作總里來(lái)確定的。 一般來(lái)說，二分法(即把任意大小的問題盡可能地等分為兩個(gè)子問

24、題)較為有效。,算法設(shè)計(jì)分析,從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是一個(gè)遞歸過程。因此，分治法的計(jì)算效率通?？梢杂眠f歸方程來(lái)進(jìn)行分析。（對(duì)） 分治法算法的最關(guān)鍵步驟是分解。（錯(cuò)） 二分搜索算法運(yùn)用的是分治策略。 （對(duì)）,算法設(shè)計(jì)分析,分治法每一層遞歸上的三個(gè)步驟,簡(jiǎn)答： 分治法在每一層遞歸上都三個(gè)步驟？分解：將原問題分解成一系列子問題；解決：遞歸地解各子問題。若子問題足夠小，則直接解：合并：將子問題的結(jié)果合并成原問題的解； 快速排序算法是基于分治策略的一個(gè)算法。其基本思想是，對(duì)于輸入的子數(shù)組ap:r,按以下3個(gè)步驟進(jìn)行排序：分解、遞歸求解、合并。,算法設(shè)計(jì)分析,應(yīng)用分治法的兩個(gè)

25、前提是（A） A.問題的可分性和解的可歸并性 B.問題的可分性和解的存在性 C.問題的復(fù)雜性和解的可歸并性 D.問題的可分性和解的復(fù)雜性,算法設(shè)計(jì)分析,有的同學(xué)選擇為B。這道題仍然考察的對(duì)分治法基本思想的理解。分治法的基本思想任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模N有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算；n=2時(shí)，只要作一次比較即可排好序；n=3時(shí)只要作3次比較即可，。而當(dāng)n較大時(shí)，問題就不那么容易處理了。 要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的。,算法設(shè)計(jì)分析,分治法的設(shè)計(jì)思想是，將一個(gè)

26、難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。 如果原問題可分割成k個(gè)子問題（1kn），且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。,算法設(shè)計(jì)分析,在上述情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。,算法設(shè)計(jì)分析,就本題而言，分治法的適用條件 分治法的適用條件分治法所能解決的問題

27、一般具有以下幾個(gè)特征： 1）該問題的規(guī)模縮小到一定的程度就可以容易地解決；這一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加,算法設(shè)計(jì)分析,2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用 合并排序算法的基本思想是將待排序的元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。,算法設(shè)計(jì)分析,3）利用該問題分解出的子問題的解可以合并為該問題的解；這條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具

28、有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。,算法設(shè)計(jì)分析,4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。 因此本題的正確答案為：A.問題的可分性和解的可歸并性,算法設(shè)計(jì)分析,排序的分類,插入排序，交換排序，選擇排序，歸并排序和計(jì)數(shù)排序等等 復(fù)雜度分類 O(n2) O(nLogn) O(dn) 排序進(jìn)行的操作 比較和移動(dòng),第六章：排序和查找,算法設(shè)計(jì)分析,根據(jù)排序元素

29、所在位置不同，排序非內(nèi)排序和外排序。 （對(duì)）,算法設(shè)計(jì)分析,快速排序,基本思想 通過一趟排序?qū)⒓o(jì)錄分割，其中一部分關(guān)鍵字均比另一部分??；然后再分別對(duì)這兩部分進(jìn)行排序； 通常選取序列的第一個(gè)紀(jì)錄作為比較的參照（稱為支點(diǎn)Pivot），然后將關(guān)鍵字小的排在其前，大的排在其后，并以此時(shí)關(guān)鍵字的位置將序列分成兩部分，再對(duì)兩部分進(jìn)行快速排序； 因此快速排序是一個(gè)遞歸的算法,算法設(shè)計(jì)分析,實(shí)現(xiàn)快速排序算法如下： private static void quickSort(int p ,int r) if（pr)） int q=partition(p,r); /以確定的基準(zhǔn)元素ap對(duì)子數(shù)組ap;r進(jìn)行劃分 A

30、 /對(duì)左半段排序 quickSort(q+1,r); /對(duì)右半段排序 A. quickSort(p,q-1) B. quickSort(p+1,q-1) C. quickSort(p,q+1) D. quickSort(p,q-2),算法設(shè)計(jì)分析,.快速排序的平均復(fù)雜度為O(n2)。 （錯(cuò)） 快速排序的平均運(yùn)行時(shí)間為 ：( C ) A. O(n) B. O(n2) C. O(nlgn) D. O(lgn),算法設(shè)計(jì)分析,歸并排序,歸并的含義： 將兩個(gè)有序的序列合并形成一個(gè)新的有序序列 歸并排序的過程： 先將序列視為n個(gè)有序的子序列，進(jìn)行兩兩歸并，然后再兩兩進(jìn)行歸并，直至形成一個(gè)序列 歸并排序的

31、核心算法： 兩個(gè)有序序列合成一個(gè)序列 歸并排序 需要和待排記錄等量的空間 算法是遞歸的,算法設(shè)計(jì)分析,合并排序法的基本思想是：將待排序元素分成大小大致相同的C個(gè)子集合，分別對(duì)每個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 A . 4 B. 3 C. 2 D. 5,算法設(shè)計(jì)分析,合并排序算法是用 分支策略 實(shí)現(xiàn)對(duì)n各元素進(jìn)行排序的算法。,算法設(shè)計(jì)分析,三 動(dòng)態(tài)規(guī)劃算法,學(xué)習(xí)要求 通過本章的學(xué)習(xí)： 要求了解動(dòng)態(tài)規(guī)劃的基本思想； 掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟； 學(xué)會(huì)使用動(dòng)態(tài)規(guī)劃方法分析和解決實(shí)際的問題； 并對(duì)算法進(jìn)行復(fù)雜性分析。,算法設(shè)計(jì)分析,課程內(nèi)容,1動(dòng)態(tài)規(guī)劃算法介紹：（1

32、）動(dòng)態(tài)規(guī)劃算法的基本思想（2）動(dòng)態(tài)規(guī)劃算法與分治算法的區(qū)別（3）動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)步驟（4）動(dòng)態(tài)規(guī)劃算法的基本要素 2使用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問題：矩陣連乘問題最長(zhǎng)公共子序列問題凸多邊形最優(yōu)三角剖分多邊形游戲圖像壓縮0-1背包問題,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃算法基本概念,要了解動(dòng)態(tài)規(guī)劃的概念，首先要知道什么是多階段決策問題。 多階段決策問題如果一類活動(dòng)過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策(采取措施)，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動(dòng)路線，則稱它為多階段決策問題。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃算法基本思想,動(dòng)態(tài)規(guī)劃算法與分治法類似，其

33、基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。 與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。 若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費(fèi)指數(shù)時(shí)間。,算法設(shè)計(jì)分析,給定若干物品的重量和價(jià)值，以及一個(gè)背包的容量上限。求出一種方案使的背包中存放物品的價(jià)值最高。這個(gè)問題除了可以考慮回溯法和分支限界法之外，還可以用動(dòng)態(tài)規(guī)劃的方法解決。 （對(duì)）,算法設(shè)計(jì)分析,適合于用動(dòng)態(tài)規(guī)劃求解的問題經(jīng)過分解后得到子問題與分治法不同，它們往往是（ B ）。 A.互相獨(dú)立的 B.互相不獨(dú)立 C.互相

34、交叉的 D.任意的,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃算法可以有效地解0-1背包問題。(對(duì)) 動(dòng)態(tài)規(guī)劃算法 適用于解最優(yōu)化問題。,算法設(shè)計(jì)分析,不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。 如果能夠保存已解決的子問題的答案，所在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算從而得到多項(xiàng)式時(shí)間算法。 為了達(dá)到這個(gè)目的，可以用個(gè)表來(lái)記錄所有已解決的子問題的答案。 不管該于問題以后是否被用到只要它被計(jì)算過，就將其結(jié)果填人表中。這就是動(dòng)念規(guī)劃法的基本思想。具體的動(dòng)態(tài)規(guī)劃算法是多種多樣的，但它們具有相同的填表格式。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃的定義,我們將具有明顯的階段劃分和狀

35、態(tài)轉(zhuǎn)移方程的動(dòng)態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃。 這種標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃是在研究多階段決策問題時(shí)推導(dǎo)出來(lái)的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。 在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。 一般來(lái)說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃的實(shí)質(zhì),動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余 因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃法與其他算法的聯(lián)系,動(dòng)態(tài)規(guī)劃法

36、與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。 其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。,算法設(shè)計(jì)分析,因此貪心法自頂向下，一步一步地作出貪心選擇 而分治法中的各個(gè)子問題是獨(dú)立的（即不包含公共的子子問題） 因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。 但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解 如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃主要應(yīng)用方面,動(dòng)態(tài)規(guī)劃主

37、要應(yīng)用于最優(yōu)化問題 這類問題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。 若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解.,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃法的基本步驟是（D）。 （1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征； （2）遞歸地定義最優(yōu)值 （3）以自底向上的方式計(jì)算出最優(yōu)值 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解 A（1）（3） B.（1） C.（2）（4） D.（1）（4）,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃算法的基本要素是（A）。 （1）最優(yōu)子結(jié)構(gòu) （2）重疊子問題 （3）最優(yōu)解 （4）遞歸定義 A（

38、1）（2） B. （1）（3） C.（2）（4） D.（2）（3）,算法設(shè)計(jì)分析,與分治法和貪心法的不同,動(dòng)態(tài)規(guī)劃與分治法和貪心法不同的是： 動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇 該方法對(duì)每一個(gè)子問題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。,算法設(shè)計(jì)分析,對(duì)同一個(gè)問題，動(dòng)態(tài)規(guī)劃算法和分治算法的計(jì)算復(fù)雜性是一樣的。（錯(cuò)） 在動(dòng)態(tài)規(guī)劃算法中，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠以 D的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。 A.自左向右 B.自右向左 C.自上向下 D.自底向上,算法設(shè)計(jì)分析,與分治法不同的是

39、，適合于用動(dòng)態(tài)規(guī)劃求解的問題， D A經(jīng)分解得到子問題往往是任意的 B經(jīng)分解得到子問題往往是互相獨(dú)立的 C經(jīng)分解得到子問題往往是互相交叉的 D經(jīng)分解得到子問題往往不是互相獨(dú)立的,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式做出相繼的貪心選擇，每做出一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃法的關(guān)鍵,動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。 動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于：對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必

40、重新求解。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃算法的基本步驟,設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行： （1）劃分階段 （2）選擇狀態(tài) （3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程 （4）寫出規(guī)劃方程（包括邊界條件）,算法設(shè)計(jì)分析,（1）劃分階段,按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。 注意這若干個(gè)階段一定要是有序的或者是可排序的（即無(wú)后向性） 否則問題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。,算法設(shè)計(jì)分析,（2）選擇狀態(tài),將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。 當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。,算法設(shè)計(jì)分析,（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程,之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)

41、移有著天然的聯(lián)系： 狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。 所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來(lái)了。 但事實(shí)上，我們常常是反過來(lái)做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來(lái)確定決策。,算法設(shè)計(jì)分析,（4）寫出規(guī)劃方程（包括邊界條件）,動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。 一般說來(lái)，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡(jiǎn)單的。 動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。,算法設(shè)計(jì)分析,實(shí)際應(yīng)用中的幾個(gè)步驟,但是，實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)步驟進(jìn)行： （1）分析最優(yōu)解的性質(zhì)，并刻劃

42、其結(jié)構(gòu)特征。 （2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。,算法設(shè)計(jì)分析,步驟（1）（3）是動(dòng)態(tài)規(guī)劃算法的基本步驟。 在只需要求出最優(yōu)值的情形，步驟（4）可以省略 若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4） 此時(shí)，在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。,算法設(shè)計(jì)分析,動(dòng)態(tài)規(guī)劃的適用條件,任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。 同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。 適用動(dòng)態(tài)規(guī)劃的問題必須滿足： 最

43、優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） 無(wú)后向性 子問題的重疊性,算法設(shè)計(jì)分析,（1）最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）,最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。 簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。 一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì),算法設(shè)計(jì)分析,最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ) 任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。 根據(jù)最優(yōu)化原理導(dǎo)出的動(dòng)態(tài)規(guī)劃基本方程是解決一切動(dòng)態(tài)規(guī)劃問題的基本方法。,算法設(shè)計(jì)分析,（2）無(wú)后向性,各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀

44、態(tài)，它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策 而只能通過當(dāng)前的這個(gè)狀態(tài)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展 換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié) 這就是無(wú)后向性，又稱為無(wú)后效性。,算法設(shè)計(jì)分析,（3）子問題的重疊性,動(dòng)態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。 動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù) 它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。 選擇動(dòng)態(tài)規(guī)劃算法是因?yàn)閯?dòng)態(tài)規(guī)劃算法在空間上可以承受 而搜索算法在時(shí)間上卻無(wú)法承受，所以我們舍空間而取時(shí)間。,算法設(shè)計(jì)分析,能夠用動(dòng)態(tài)規(guī)劃解決問題的顯著特征,能夠用動(dòng)態(tài)規(guī)劃解決的問題有一個(gè)顯著

45、特征：子問題的重疊性。 這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件 但是如果該性質(zhì)無(wú)法滿足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。,算法設(shè)計(jì)分析,無(wú)后效性,我們要求狀態(tài)具有下面的性質(zhì)： 如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了 換句話說，過程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示,算法設(shè)計(jì)分析,在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。 從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時(shí)，不受以前線路（所通過的點(diǎn)）的影響 狀態(tài)的這個(gè)性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展

46、，這個(gè)性質(zhì)稱為無(wú)后效性。,算法設(shè)計(jì)分析,最優(yōu)性原理,作為整個(gè)過程的最優(yōu)策略，它滿足： 相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。 最優(yōu)性原理實(shí)際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。 讓我們通過對(duì)前面的例子再分析來(lái)具體說明這一點(diǎn)：從A到D，我們知道，最短路徑是AB1C2D，這些點(diǎn)的選擇構(gòu)成了這個(gè)例子的最優(yōu)策略 根據(jù)最優(yōu)性原理，這個(gè)策略的每個(gè)子策略應(yīng)是最優(yōu)：AB1C2是A到C2的最短路徑，B1C2D也是B1到D的最短路徑,算法設(shè)計(jì)分析,四 貪心算法,貪心算法的基本要求： 通過本章的學(xué)習(xí)，要求： 了解貪心法的基本思想 掌握貪婪算法的設(shè)計(jì)步驟 學(xué)會(huì)使用貪心算法分析和解決實(shí)際

47、的問題 并對(duì)算法進(jìn)行復(fù)雜性分析。,算法設(shè)計(jì)分析,主要內(nèi)容,使用貪心算法分析和解決具體問題： 活動(dòng)安排問題 最優(yōu)裝載問題 哈夫曼編碼 單源最短路徑 最小生成樹 多機(jī)調(diào)度問題,算法設(shè)計(jì)分析,貪心算法的基本內(nèi)容,貪心算法是這樣一種算法，其特點(diǎn)是: 所做的選擇都是目前最佳的 亦即，它期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個(gè)全局最優(yōu)解 這一章討論可由貪心算法解決的最優(yōu)化問題。,算法設(shè)計(jì)分析,適用于最優(yōu)化問題的算法往住包含一系列步驟，每一步都有一組選擇 對(duì)許多最優(yōu)化問題來(lái)說： 采用動(dòng)態(tài)程序設(shè)計(jì)方法來(lái)決定最佳選擇就有點(diǎn)“殺雞用牛刀”了，只要采用另一些更簡(jiǎn)單有效的算法就行了。,算法設(shè)計(jì)分析,貪心算法對(duì)大多數(shù)優(yōu)化問

48、題來(lái)說能產(chǎn)生最優(yōu)解，但也并不總是這樣 貪心方法是一種很有效的方法，適用于一大類問題。 后面的章節(jié)中將給出許多可被視為貪心法的應(yīng)用的算法，如最小生成樹算法，Dijkstra的單源最短路徑，以及貪心集合復(fù)合啟發(fā)式等等 最小生成樹是貪心法的一個(gè)經(jīng)典例子。,算法設(shè)計(jì)分析,貪心算法的基本思想,貪心算法是通過做一系列的選擇來(lái)給出某一問題的最優(yōu)解的 對(duì)算法中的每一決策點(diǎn)，做一個(gè)當(dāng)時(shí)(看起來(lái)像是)最佳的選擇。 這種啟發(fā)式策略并不是總能產(chǎn)生出最優(yōu)解，但正像我們?cè)诨顒?dòng)選擇問題中看到的那樣，它常常能給出最優(yōu)解。,算法設(shè)計(jì)分析,適宜貪心策略解的問題的兩個(gè)特點(diǎn),對(duì)一個(gè)最優(yōu)化問題，我們?cè)鯓硬拍苤烙靡粋€(gè)貪心算法來(lái)解它是否

49、合適呢?沒有一個(gè)通用的方法。 適宜于用貪心策略來(lái)解的大多數(shù)問題都有兩個(gè)特點(diǎn):貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。,算法設(shè)計(jì)分析,貪心選擇性質(zhì),第一個(gè)關(guān)鍵特點(diǎn)是貪心選擇性質(zhì):一個(gè)全局最優(yōu)解可通過做局部最優(yōu)(貪心)選擇來(lái)達(dá)到。 這一點(diǎn)是貪心算法不同于動(dòng)態(tài)程序設(shè)計(jì)方法之處，后者在每一步也要做選擇，但所做的選擇可能要依賴于子問題的解。 在一個(gè)貪心算法中，我們所做的總是當(dāng)前最佳的選擇。 然后再解決做了該選擇之后所出現(xiàn)的子間題。,算法設(shè)計(jì)分析,貪心算法所做的當(dāng)前選擇可能要依賴于已經(jīng)做出的所有選擇，但不依賴于有待于做出的選擇或子問題的解. 因?yàn)?，不像?dòng)態(tài)程序設(shè)計(jì)方法那樣自底向上地解決子問題，貪心策略通常是自頂向下地做

50、的 一個(gè)一個(gè)地做出貪心選擇，不斷地將給定的問題實(shí)例歸約為更小的問題。,算法設(shè)計(jì)分析,最優(yōu)子結(jié)構(gòu),最優(yōu)子結(jié)構(gòu) 一個(gè)問題呈現(xiàn)出最優(yōu)子結(jié)構(gòu)，如果它的一個(gè)最優(yōu)解包含了其子問題的最優(yōu)解 這個(gè)性質(zhì)是用來(lái)對(duì)某問題中動(dòng)態(tài)程序設(shè)計(jì)以及貪心算法的可應(yīng)用性進(jìn)行評(píng)價(jià)的關(guān)鍵一點(diǎn),算法設(shè)計(jì)分析,貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。這是兩類算法的一個(gè)共同點(diǎn)。 貪心算法能對(duì)所有問題都得到整體最優(yōu)解。（錯(cuò)）,算法設(shè)計(jì)分析,貪心算法不追求最優(yōu)解,貪心法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。 它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。 貪心法一般可以快速得到滿意的解 貪心法常以當(dāng)前情況為基礎(chǔ)作

51、最優(yōu)選擇 不考慮各種可能的整體情況，所以貪心法不要回溯。,算法設(shè)計(jì)分析,例如平時(shí)購(gòu)物找錢時(shí)，為使找回的零錢的硬幣數(shù)最少: 不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始 按遞減的順序考慮各幣種 先盡量用大面值的幣種 當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種 這就是在使用貪心法。,算法設(shè)計(jì)分析,貪心算法不一定能找到最優(yōu)解,貪心算法對(duì)大多數(shù)優(yōu)化問題來(lái)說能產(chǎn)生最優(yōu)解，但也并不總是這樣。 貪心算法是這樣一種算法，其特點(diǎn)是所做的選擇都是目前最佳的 亦即，它期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個(gè)全局最優(yōu)解。,算法設(shè)計(jì)分析,下面的例子說明該算法不一定能找到最優(yōu)解 設(shè)有6種物品，它們的體積

52、分別為：60、45、35、20、20和20單位體積，箱子的容積為100個(gè)單位體積。 按上述算法計(jì)算，需三只箱子，各箱子所裝物品分別為： 第一只箱子裝物品1、3；第二只箱子裝物品2、4、5；第三只箱子裝物品6。 而最優(yōu)解為兩只箱子，分別裝物品1、4、5和2、3、6。,算法設(shè)計(jì)分析,關(guān)于最優(yōu)子結(jié)構(gòu)性質(zhì),當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)稱此問題具有最優(yōu)子站構(gòu)性質(zhì)。 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征 一個(gè)問題呈現(xiàn)出最優(yōu)子結(jié)構(gòu)，如果它的一個(gè)最優(yōu)解包含了其子問題的最優(yōu)解，這個(gè)性質(zhì)是用來(lái)對(duì)某問題中動(dòng)態(tài)程序設(shè)計(jì)以及貪心算法的可應(yīng)用性進(jìn)行評(píng)價(jià)的關(guān)鍵一點(diǎn)。,算法設(shè)計(jì)分析

53、,貪心算法與動(dòng)態(tài)規(guī)劃的區(qū)別,因?yàn)樨澬姆ê蛣?dòng)態(tài)程序設(shè)計(jì)方法都利用了最優(yōu)子結(jié)構(gòu)性質(zhì) 故大家往往會(huì)在貪心解足以解決問題的場(chǎng)合下給出一個(gè)動(dòng)態(tài)程序設(shè)計(jì)解，或者正好相反 為說明這兩種技術(shù)之間的細(xì)微區(qū)別，我們來(lái)考察一個(gè)經(jīng)典優(yōu)化問題的兩種變形,算法設(shè)計(jì)分析,0-1背包問題,0-1背包問題是這樣的：有一個(gè)賊在偷竊一家商店時(shí)發(fā)現(xiàn)有n件物品;第1件物品值Vi元，重wi磅，此處vi和wi都是整數(shù) 他希望帶走的東西越值錢越好，但他的背包中至多只能裝下W磅的東西，W為一整數(shù)。 應(yīng)該帶走哪幾樣?xùn)|西呢? 這個(gè)問題被稱為0-1背包問題，因?yàn)槊考锲坊虮粠ё?，或被留?小偷不能只帶走某個(gè)物品的一部分或帶走兩次以上一個(gè)物品。,算法

54、設(shè)計(jì)分析,部分背包問題,在部分背包問題中，場(chǎng)景等與上面問題一樣，但是竊賊可以帶走物品的一部分，而不必做出0-1的二元選擇 可以把0-1背包問題的一件物品想像成像一個(gè)金錠，而部分背包問題中的一件物品則更像金粉,算法設(shè)計(jì)分析,兩種背包問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì) 對(duì)0-1問題，考慮重量至多為W磅的最值錢的一包東西. 如果我們從中去掉物品j，余下的必須是竊賊除j外的n1物品可以帶走的重量至多為Wwj的最值錢的一包東西。,算法設(shè)計(jì)分析,對(duì)部分背包問題： 考慮如果我們從最優(yōu)貨物中去掉某物品j的重量w，則余下的貨物必須是竊賊可以從nl件原有物品和物品j的wjw磅中可帶走的、重量至多為W-w的、最值錢的一包東西

55、. 雖然這兩個(gè)問題非常相似，但部分背包問題可用貪心策略來(lái)解決，而0-1背包問題卻不行。,算法設(shè)計(jì)分析,為解決部分背包問題，我們先對(duì)每件物品計(jì)算其每磅的價(jià)值vi/wi，按照一種貪心策略，竊賊開始時(shí)對(duì)具有最大每磅價(jià)值的物品盡量多拿一些。 如果他拿完了該物品而仍可以取一些其他物品時(shí)，他就再取具有次大的每磅價(jià)值的物品，一直繼續(xù)下去。直到不能再取了為止。 這樣，通過按每磅價(jià)值來(lái)對(duì)所有物品排序，貪心算法就可以O(shè)（nlgn）時(shí)間運(yùn)行。,算法設(shè)計(jì)分析,對(duì)于背包問題，貪心選擇最終可得到最優(yōu)解： 對(duì)于01背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)椋?在這種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使

56、每公斤背包空間的價(jià)值降低。 事實(shí)上，在考慮01背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終力案然后再做出最好選擇,算法設(shè)計(jì)分析,由此就導(dǎo)出許多互相重疊的子問題 這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解01背包問題。,算法設(shè)計(jì)分析,用貪心法解最優(yōu)裝載問題的時(shí)候，我們采用的貪心選擇的策略是C A.重量大者先裝 B.總價(jià)值大的先裝 C.重量輕者先裝 D.單位價(jià)值大的先裝,算法設(shè)計(jì)分析,貪心選擇性質(zhì)是 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇 。 .貪心算法不能都得到整體最優(yōu)解。 （對(duì)） 貪心算法總能求得問題的整體最優(yōu)解。（錯(cuò)） 貪

57、心算法它所作出的選擇都是在某種意義上的全局最優(yōu)選擇。 （錯(cuò)）,算法設(shè)計(jì)分析,貪心算法與動(dòng)態(tài)規(guī)劃算法的一個(gè)共同點(diǎn),貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個(gè)共同點(diǎn)。 但是，對(duì)于一個(gè)具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法來(lái)求解?是不是能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法來(lái)求解? 面我們來(lái)研究?jī)蓚€(gè)經(jīng)典的組合優(yōu)化問題，并以此來(lái)說明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。,算法設(shè)計(jì)分析,由此就導(dǎo)出許多互相重疊的子問題 這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征 動(dòng)態(tài)規(guī)劃算法的確可以有效地解01背包問題。,算法設(shè)計(jì)分析,Diskstra算法是解單源最短路徑問題的

58、貪心算法，其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來(lái)擴(kuò)充這個(gè)集合。 用貪心算法求解的問題中一般具有2個(gè)重要的性質(zhì)： 貪心選擇性質(zhì) 和最優(yōu)子結(jié)構(gòu)性質(zhì)。,算法設(shè)計(jì)分析,所謂寬度優(yōu)先搜索就是： 一種在無(wú)權(quán)圖上運(yùn)行的最短路徑算法 即在圖的邊都具有單位權(quán)值的圖上的一種算法。 因?yàn)橛嘘P(guān)寬度優(yōu)先搜索的許多概念都產(chǎn)生于對(duì)有權(quán)圖的最短路徑的研究。,算法設(shè)計(jì)分析,對(duì)于連通的帶權(quán)圖(連通網(wǎng))G，其生成樹也是帶權(quán)的。生成樹T各邊的權(quán)值總和稱為該樹的權(quán)，權(quán)最小的生成樹稱為G的最小生成樹。,算法設(shè)計(jì)分析,貪心算法解決問題的效果,貪心算法通過一系列的選擇來(lái)得到一個(gè)問題的解。它所作的每一個(gè)選擇都是當(dāng)前狀態(tài)下某種意義的最

59、好選擇，即貪心選擇。 希望通過每次所作的貪心選擇導(dǎo)致最終結(jié)果是問題的一個(gè)最優(yōu)解。 這種啟發(fā)式的策略并不總能奏效，然而在許多情況下確能達(dá)到頂期的目的。解活動(dòng)安排問題的貪心算法就是一個(gè)例子,算法設(shè)計(jì)分析,下面我們著重討論可以用貪心算法求解的問題的一般特征。對(duì)于一個(gè)具體的問題，我們?cè)趺粗朗欠窨捎秘澬乃惴▉?lái)解此問題，以及能否得到問題的個(gè)最優(yōu)解呢，這個(gè)問題很難給予肯定的回答 但是,從許多可以用貪心算法求解的問題中我們看到它們一般只有兩個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。,算法設(shè)計(jì)分析,貪婪算法之貨箱裝船,船可以分步裝載，每步裝一個(gè)貨箱，且需要考慮裝載哪一個(gè)貨箱 根據(jù)這種思想可利用如下貪婪準(zhǔn)則： 從剩下的貨箱中，選擇重量最小的貨箱。 這種選擇次序可以保證所選的貨箱總重量最小， 從而可以裝載更多的貨箱。 根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然 后選次輕的貨箱，如此下去直到所有貨箱均裝 上船或船上不能再容納其他任何一個(gè)