計(jì)算思維導(dǎo)論第3章課件

第三章11974年圖靈獎(jiǎng)獲得者DonaldErvinKnuth:計(jì)算機(jī)科學(xué)就是算法的研究TheArtofComputerProgramming3.1算法的概念計(jì)算機(jī)輸入輸出算法問(wèn)題算法與計(jì)算機(jī)之間的關(guān)系2一、算法的起源3.1算法的概念公元前300年：古希臘著名數(shù)學(xué)家歐幾里得提出求最大公約數(shù)的一種算法,即輾轉(zhuǎn)相除法又稱(chēng)歐幾里得算法。公元263年：三國(guó)魏人劉徽注釋《九章算術(shù)》中不僅對(duì)原書(shū)的方法、公式和定理進(jìn)行一般的解釋和推導(dǎo)，而且在其論述中多有創(chuàng)造。如他運(yùn)用割圓術(shù)得出圓周率的近似值3927/1250＝3.1416。公元825年：波斯數(shù)學(xué)家al-Khwarizmi撰寫(xiě)了著名的PersianTextbook中概括了進(jìn)行四則算術(shù)運(yùn)算的法則。Algorithm(算法)一詞就來(lái)源于這位數(shù)學(xué)家的名字。3二、算法的定義[算法3.1]歐幾里得算法。輸入：正整數(shù)m、n輸出：m、n的最大公約數(shù)①r＝mmodn②若r＝0，輸出最大公約數(shù)n③若r≠0，令m＝n，n＝r，轉(zhuǎn)①繼續(xù)

3.1算法的概念算法：是解決某一特定問(wèn)題的一組有窮規(guī)則的集合。算法：對(duì)特定問(wèn)題求解步驟的一種描述，是由若干條指令組成的有窮集合。4三、算法的特征確定性：算法中每一個(gè)步驟都是清晰的、無(wú)歧義有窮性：算法必須在有限步內(nèi)終止輸入：有零個(gè)或多個(gè)輸入，作為初始狀態(tài)輸出：有一個(gè)或多個(gè)輸出，作為計(jì)算結(jié)果可行性：算法中的操作可通過(guò)有限次基本運(yùn)算來(lái)實(shí)現(xiàn)3.1算法的概念判斷一個(gè)算法的好壞主要依據(jù)如下標(biāo)準(zhǔn)：正確性：在合理輸入下能在有限時(shí)間內(nèi)得出正確結(jié)果可讀性：算法主要是為了人的閱讀與交流，其次執(zhí)行健壯性：算法應(yīng)具備檢查錯(cuò)誤和對(duì)錯(cuò)誤進(jìn)行處理能力效率：算法執(zhí)行時(shí)所需計(jì)算機(jī)資源的多少5算法的描述目的記錄算法思想方便他人理解算法3.2算法的描述算法的描述方法自然語(yǔ)言流程圖偽代碼程序設(shè)計(jì)語(yǔ)言6一、自然語(yǔ)言3.2算法的描述自然語(yǔ)言是人們?nèi)粘＿M(jìn)行交流的語(yǔ)言，如漢語(yǔ)、英語(yǔ)等優(yōu)點(diǎn)：通俗易懂，即使沒(méi)有學(xué)過(guò)算法也能看懂算法執(zhí)行缺點(diǎn)：不夠嚴(yán)謹(jǐn)，容易出現(xiàn)歧義和錯(cuò)誤[例題]利用自然語(yǔ)言描述歐幾里得算法。①輸入m、n②判斷n是否為0，如果不為0，轉(zhuǎn)步驟③，否則轉(zhuǎn)④③m對(duì)n取余，其結(jié)果賦值給r，n賦給m，r賦給n，轉(zhuǎn)②④輸出m，算法結(jié)束7二、流程圖常用來(lái)描述算法的圖形工具有：流程圖或程序框圖、N-S圖和PAD圖。

優(yōu)點(diǎn)：直觀(guān)形象，簡(jiǎn)潔明了。

缺點(diǎn)：畫(huà)起來(lái)費(fèi)事，不易修改。3.2算法的描述常用的流程圖符號(hào)：8[例題]利用流程圖描述歐幾里得算法。3.2算法的描述9三、偽代碼3.2算法的描述偽代碼是由帶標(biāo)號(hào)的指令構(gòu)成，但是它不是C、C++、Java等通常使用的程序設(shè)計(jì)語(yǔ)言，而是算法步驟的描述。偽代碼介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間。偽代碼的具體表示：賦值語(yǔ)言：←分支語(yǔ)句：if…then…[else]循環(huán)語(yǔ)句：while,for,repeatuntil轉(zhuǎn)向語(yǔ)句：goto輸出語(yǔ)句：return調(diào)用：注釋?zhuān)?/…10[例題]利用偽代碼描述歐幾里得算法。3.2算法的描述輸入：正整數(shù)m、n輸出：m、n的最大公約數(shù)1repeat2r←mmodn3m←n4n←r5untilr=06returnm

11四、程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言是一個(gè)能完整、準(zhǔn)確和規(guī)則地表達(dá)人們的意圖，并用以指揮或控制計(jì)算機(jī)工作的符號(hào)系統(tǒng)，如C、C++、Java等程序設(shè)計(jì)語(yǔ)言可以描述算法。3.2算法的描述優(yōu)點(diǎn)：描述的算法能在計(jì)算機(jī)上直接執(zhí)行缺點(diǎn)：抽象性差、不易理解且有嚴(yán)格的語(yǔ)法限制等。12輸入：正整數(shù)m、n輸出：m、n的最大公約數(shù)int

gcd(intm,intn){int

r;do{r=m%n;m=n;n=r;}

while(r);returnm;}3.2算法的描述[例題]利用C語(yǔ)言描述歐幾里得算法。13算法是解決問(wèn)題的方案，由于實(shí)際問(wèn)題千奇百怪，因而制定出的解決方案也將千差萬(wàn)別。3.3算法的設(shè)計(jì)

算法設(shè)計(jì)的一般步驟：①理解待求解問(wèn)題解決問(wèn)題是設(shè)計(jì)算法的最終目標(biāo)。除了需要分析問(wèn)題的求解目標(biāo)、輸入數(shù)據(jù)和限制條件外，還要判斷清楚待求解問(wèn)題的種類(lèi)，是否有現(xiàn)成的算法可以直接應(yīng)用。②確定算法運(yùn)行的環(huán)境了解算法的運(yùn)行環(huán)境，才能設(shè)計(jì)出可行且高效的算法。比如在小型的嵌入式環(huán)境中只能運(yùn)行需要較小內(nèi)存的算法，而對(duì)于并行分布式的運(yùn)行環(huán)境，則要設(shè)計(jì)高效的并行算法。14③設(shè)計(jì)算法設(shè)計(jì)算法是將算法具體化，即設(shè)計(jì)出算法的詳細(xì)規(guī)格說(shuō)明。也就是，首先確定算法所需要的數(shù)據(jù)結(jié)構(gòu)，然后結(jié)合具體問(wèn)題的特性來(lái)選擇算法的設(shè)計(jì)策略，最后根據(jù)算法設(shè)計(jì)技術(shù)的原理描述算法的具體流程(流程圖、偽代碼和程序設(shè)計(jì)語(yǔ)言等)。④分析算法對(duì)所設(shè)計(jì)出的算法進(jìn)行復(fù)雜性分析，考察其在時(shí)間和空間方面的計(jì)算開(kāi)銷(xiāo)。若算法在某些環(huán)節(jié)的計(jì)算開(kāi)銷(xiāo)較大，可有針對(duì)性地改進(jìn)該環(huán)節(jié)，若整個(gè)算法的計(jì)算開(kāi)銷(xiāo)太大，則需要返回第③步重新考慮采用新的算法設(shè)計(jì)技術(shù)來(lái)求解該問(wèn)題。⑤編程實(shí)現(xiàn)采用某種程序設(shè)計(jì)語(yǔ)言將設(shè)計(jì)好的算法實(shí)現(xiàn)出來(lái)。3.3算法的設(shè)計(jì)15

算法分類(lèi)：

①數(shù)值算法

求解線(xiàn)性方程組、數(shù)值積分等，有特定的計(jì)算步驟

數(shù)值計(jì)算方法課程

②非數(shù)值算法

求解判定問(wèn)題、最優(yōu)化問(wèn)題等，需要掌握算法設(shè)計(jì)技術(shù)

算法設(shè)計(jì)與分析課程

③軟計(jì)算方法

遺傳算法、粒子群算法、蟻群算法、人工神經(jīng)網(wǎng)絡(luò)等

計(jì)算智能課程3.3算法的設(shè)計(jì)16一、窮舉法(又稱(chēng)蠻力算法)

窮舉法指在問(wèn)題的解空間范圍內(nèi)逐一測(cè)試，找出問(wèn)題的解。它是一種簡(jiǎn)單而有效的算法設(shè)計(jì)策略同時(shí)也是一種很容易應(yīng)用的方法。

3.3算法的設(shè)計(jì)窮舉法的應(yīng)用

國(guó)王的婚姻中國(guó)王使用的算法

旅行商問(wèn)題中逐條路線(xiàn)計(jì)算

密碼學(xué)中的暴力破解法

圖論中四色定理的證明

百錢(qián)買(mǎi)百雞問(wèn)題

17[案例一]暴力破解法是一種用窮舉法實(shí)現(xiàn)的密碼破譯方法。3.3算法的設(shè)計(jì)最原始、最基本的攻擊方式，對(duì)密碼進(jìn)行逐一測(cè)試直到找到真正的密碼。原則上可以破譯所有密碼，但費(fèi)時(shí)費(fèi)力。密碼暴力破解軟件：89Winrar

QQ密碼暴力破解軟件18[案例二]四色定理(又稱(chēng)四色問(wèn)題或四色猜想)。3.3算法的設(shè)計(jì)四色問(wèn)題描述：任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色。數(shù)學(xué)語(yǔ)言表示：將平面任意地細(xì)分為不相重疊的區(qū)域，每一個(gè)區(qū)域總可以用1、2、3、4這四個(gè)數(shù)字之一來(lái)標(biāo)記，而不會(huì)使相鄰的有公共邊界的兩個(gè)區(qū)域得到相同的數(shù)字。證明四色定理(窮舉法)：①利用數(shù)學(xué)理論推出證明所有例子可以歸約到證明有限個(gè)特例上；②利用計(jì)算機(jī)程序產(chǎn)生了所有特例(大約1700個(gè)例子)，通過(guò)窮舉發(fā)現(xiàn)所有特例都是四著色的。19[案例三]百錢(qián)買(mǎi)百雞問(wèn)題

百錢(qián)買(mǎi)百雞：雞翁一，值錢(qián)五雞母一，值錢(qián)三雞雛三，值錢(qián)一問(wèn)翁、母、雛各幾何？3.3算法的設(shè)計(jì)意思是：公雞每只5元、母雞每只3元、小雞3只1元，用100元錢(qián)買(mǎi)100只雞，求公雞、母雞、小雞的只數(shù)。20

設(shè)雞翁、雞母、雞雛的個(gè)數(shù)分別為x、y、z，根據(jù)題意可得如下方程組：

5x＋3y＋z/3＝100x＋y＋z＝1001≤x＜20,1≤y＜33,3≤z＜100,zmod3＝0測(cè)試集合：1≤x＜20,1≤y＜33，z=3,6,9,...,99測(cè)試條件：5x＋3y＋z/3＝100

x＋y＋z＝1003.3算法的設(shè)計(jì)21巧妙和高效的算法很少來(lái)自于窮舉法，但基于以下因素，窮舉法仍是一種重要的算法設(shè)計(jì)策略：①窮舉法幾乎可以通用于任何領(lǐng)域的問(wèn)題求解，可能是唯一一種解決所有問(wèn)題的一般性方法；②即使效率低下，仍可用窮舉法求解一些小規(guī)模的問(wèn)題實(shí)例；③如果解決的問(wèn)題實(shí)例不多，而窮舉法可用一種可接受的速度對(duì)問(wèn)題求解，那么花時(shí)間去設(shè)計(jì)一個(gè)更高效地算法是得不償失的。

3.3算法的設(shè)計(jì)[思考題]舉例說(shuō)明生活中的窮舉法應(yīng)用。22二、回溯法

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。在搜索過(guò)程中，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試，通過(guò)此種方式提高搜索效率，減少不必要的測(cè)試。3.3算法的設(shè)計(jì)回溯法的應(yīng)用迷宮問(wèn)題搜索引擎中的網(wǎng)絡(luò)爬蟲(chóng)八皇后問(wèn)題23[案例一]老鼠走迷宮3.3算法的設(shè)計(jì)老鼠從迷宮入口出發(fā)，任選一條路線(xiàn)向前走，在到達(dá)一個(gè)岔路口時(shí)，任選一個(gè)路線(xiàn)走下去…，如此繼續(xù)，直到前面沒(méi)有路可走時(shí)，老鼠退回到上一個(gè)岔路口，重新在沒(méi)有走過(guò)的路線(xiàn)中任選一條路線(xiàn)往前走。按這種方式走下去，直到走出迷宮。

24[案例二]搜索引擎中的網(wǎng)絡(luò)爬蟲(chóng)。3.3算法的設(shè)計(jì)

搜索引擎是指根據(jù)一定的策略、運(yùn)用特定的計(jì)算機(jī)程序從互聯(lián)網(wǎng)上搜集信息，在對(duì)信息進(jìn)行組織和處理后，為用戶(hù)提供檢索服務(wù)，將用戶(hù)檢索相關(guān)的信息展示給用戶(hù)的系統(tǒng)。百度和谷歌等是搜索引擎的代表。

搜索引擎的組成：下載、索引和查詢(xún)。25網(wǎng)絡(luò)爬蟲(chóng)：自動(dòng)下載互聯(lián)網(wǎng)所有網(wǎng)頁(yè)。網(wǎng)絡(luò)爬蟲(chóng)原理：圖的遍歷，從圖中某一頂點(diǎn)出發(fā)訪(fǎng)遍圖中所有頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次?；厮菟惴ǎ簣D的深度優(yōu)先遍歷（廣度優(yōu)先遍歷）。3.3算法的設(shè)計(jì)深度優(yōu)先遍歷順序：V1,V2,V4,V8,V5,V3,V6,V726[案例三]八皇后問(wèn)題。在8×8格國(guó)際象棋的棋盤(pán)上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線(xiàn)上問(wèn)有多少種擺法？3.3算法的設(shè)計(jì)27

回溯法解八皇后問(wèn)題思路：逐行擺放皇后。初始第1行皇后放第1列；擺放第i行皇后時(shí)，從第1列開(kāi)始，逐列判定是否與前i-1行皇后攻擊，直到找到一個(gè)不攻擊的位置，繼續(xù)第i+1行的擺放；若第i行無(wú)擺放位置，則拿掉該行皇后，回溯至第i-1行，第i-1行皇后從當(dāng)前位置的下一列開(kāi)始判定，繼續(xù)搜索。當(dāng)?shù)?行皇后的擺放位置超出棋盤(pán)時(shí)，全部求解過(guò)程結(jié)束。(92種)3.3算法的設(shè)計(jì)28回溯法有通用解法之稱(chēng)，當(dāng)一個(gè)問(wèn)題沒(méi)有顯而易見(jiàn)的解法時(shí)，可嘗試使用回溯法求解，這實(shí)際是與窮舉法一致的，因其本質(zhì)仍是窮舉。需要注意，回溯和窮舉雖然能解很多問(wèn)題，但其算法效率可能很低。3.3算法的設(shè)計(jì)

回溯法的基本思想是能進(jìn)則進(jìn)，不能進(jìn)則退。為了求得問(wèn)題的解，先選擇某一種可能情況向前探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或確定該問(wèn)題無(wú)解?；厮莘ㄊ乔蠼鈱?shí)際問(wèn)題的一個(gè)重要算法，很多無(wú)法使用貪心算法和動(dòng)態(tài)規(guī)劃算法進(jìn)行求解的問(wèn)題，都可以使用回溯算法進(jìn)行求解，并且可以保證得到問(wèn)題的最優(yōu)解。29三、遞歸算法

遞歸：直接或間接地調(diào)用自身的算法。遞歸思想就是用與自身問(wèn)題相似但規(guī)模較小的問(wèn)題來(lái)描述自己。3.3算法的設(shè)計(jì)遞歸算法的應(yīng)用盜夢(mèng)空間(美國(guó)影片)歐幾里得算法德羅斯特效應(yīng)(DrosteEffect)斐波納契數(shù)列(Fibonacci數(shù)列)30[案例一]德羅斯特效應(yīng)。遞歸的一種視覺(jué)形式，它指一張圖片的某個(gè)部分與整張圖片相同，如此產(chǎn)生無(wú)限循環(huán)。3.3算法的設(shè)計(jì)31[案例二]1202年，意大利數(shù)學(xué)家斐波納契出版了他的算盤(pán)全書(shū)。他在書(shū)中提出了一個(gè)關(guān)于兔子繁殖問(wèn)題：如果一對(duì)兔子每月能生一對(duì)小兔(一雄一雌)，而每對(duì)小兔在它們出生后的第三個(gè)月里，又能開(kāi)始生一對(duì)小兔，假定在不發(fā)生死亡的情況下，由一對(duì)出生的小兔開(kāi)始，50月后會(huì)有多少對(duì)兔子？分析：第一個(gè)月只有一對(duì)兔子，第二個(gè)月仍只有一對(duì)兔子，第三個(gè)月兔子對(duì)數(shù)為第二個(gè)月兔子對(duì)數(shù)加第一月兔子新生的對(duì)數(shù)。同理，第i個(gè)月兔子對(duì)數(shù)為第i-1月兔子對(duì)數(shù)加第i-2月兔子新生的對(duì)數(shù)。即從第一個(gè)月開(kāi)始計(jì)算，每月兔子對(duì)數(shù)依次為：1,1,2,3,5,8,13,21,34,55,89,144,233,…。

3.3算法的設(shè)計(jì)32兔子繁殖的規(guī)律3.3算法的設(shè)計(jì)月數(shù)小兔子對(duì)數(shù)中兔子對(duì)數(shù)老兔子對(duì)數(shù)兔子總數(shù)110012010131012411135212563238753513┆┆┆┆┆33遞歸過(guò)程3.3算法的設(shè)計(jì)F5=F4+F3F4=F3+F2F3=F2+F1F2=1F1=1F3=1+1=2F4=2+1=3F5=3+2=5回溯階段遞推階段34Fibonacci數(shù)列遞歸算法的偽代碼描述：Fibonacci數(shù)列的遞歸算法輸入：正整數(shù)n輸出：Fibonacci數(shù)列的第n項(xiàng)Fib(n)1IFn≤22 THENRETURN13RETURNFib(n-1)+Fib(n-2)//調(diào)用自身3.3算法的設(shè)計(jì)35

遞歸算法的主要優(yōu)點(diǎn)：結(jié)構(gòu)清晰、可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)了很大方便。

遞歸算法的主要缺點(diǎn)：遞歸算法的運(yùn)行效率相對(duì)較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。通常的解決方法是消除遞歸算法中的遞歸調(diào)用，使遞歸算法轉(zhuǎn)化為非遞歸算法。3.3算法的設(shè)計(jì)36四、分治法3.3算法的設(shè)計(jì)

分治算法：將一個(gè)難以直接解決的大問(wèn)題，分解成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。如果子問(wèn)題還比較大，可反復(fù)使用分治算法，直到最后的子問(wèn)題可以直接得出它們的結(jié)果。由于分治算法的子問(wèn)題類(lèi)型常與原來(lái)的相同，因而很自然地使用遞歸算法。分治法的應(yīng)用國(guó)王的婚姻中宰相的策略Google的MapReduce技術(shù)二分查找用于組織管理和軍事等領(lǐng)域37[案例一]Google的MapReduce技術(shù)3.3算法的設(shè)計(jì)谷歌在全球有36個(gè)數(shù)據(jù)中心，服務(wù)器不計(jì)其數(shù)。它的三大核心技術(shù)是：

GFS(GoogleFileSystem)：專(zhuān)用文件系統(tǒng)；

BigTable：分布式數(shù)據(jù)庫(kù)系統(tǒng)；

MapReduce：并行計(jì)算編程模型。38

MapReduce模型中兩項(xiàng)核心操作：Map→映射；Reduce→化簡(jiǎn)、歸約3.3算法的設(shè)計(jì)MapReduce處理大數(shù)據(jù)過(guò)程是由劃分、治理、合并三個(gè)步驟組成，是分治策略的完美應(yīng)用。

39[案例二]二分查找3.3算法的設(shè)計(jì)常用的二分查找是一個(gè)典型的分治算法。

二分查找基本原理：用于在n個(gè)元素的有序序列中查找指定元素e。將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取an/2與欲查找的e作比較，若e=an/2，則找到e，算法終止若e<an/2，則只需在數(shù)組a的前半部分繼續(xù)二分查找e若x>an/2，則只需在數(shù)組a的后半部分繼續(xù)二分查找e二分查找每次比較將數(shù)據(jù)減少一半，也稱(chēng)折半查找。

40二分查找在列表中查找John的計(jì)算過(guò)程

3.3算法的設(shè)計(jì)41分治策略是解決工作、學(xué)習(xí)和生活中常見(jiàn)問(wèn)題的一種思維方法，它在組織管理和軍事領(lǐng)域得到廣泛的應(yīng)用例如：某大企業(yè)的銷(xiāo)售公司，由于其許多產(chǎn)品優(yōu)質(zhì)而非常暢銷(xiāo)，總部會(huì)到各地建立分支機(jī)構(gòu)，這其中就蘊(yùn)涵著分治思想。3.3算法的設(shè)計(jì)再如：中國(guó)革命戰(zhàn)爭(zhēng)時(shí)期經(jīng)常遇到敵軍強(qiáng)大，因此采用集中優(yōu)勢(shì)兵力，逐個(gè)擊破的分治策略往往能產(chǎn)生以弱勝?gòu)?qiáng)的優(yōu)異戰(zhàn)果又如：各種大型體育賽事通常分為初賽和決賽，世界杯足球賽要從報(bào)名參賽的200多支球隊(duì)中選出成績(jī)最好的32支球隊(duì),難度很大，成本也高。因此通過(guò)分區(qū)預(yù)選賽選出成績(jī)最好的32支球隊(duì)進(jìn)入決賽圈，這種做法也包含分治思想并降低了難度和復(fù)雜度。42五、貪心法

1.問(wèn)題的提出3.3算法的設(shè)計(jì)假設(shè)有3種硬幣，它們的面值分別是1元、5角、1角?，F(xiàn)在有一個(gè)小孩買(mǎi)了價(jià)值6元2角的東西，并給售貨員10元錢(qián)。當(dāng)售貨員找給小孩零錢(qián)時(shí)，希望她找給小孩的硬幣數(shù)目最少。33103822223210381318這種簡(jiǎn)單地從具有最大面值的幣種開(kāi)始，按遞減的順序考慮各種幣種的方法稱(chēng)為貪心法，或啟發(fā)式搜索法。432.貪心算法3.3算法的設(shè)計(jì)

貪心法的基本思想：將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題進(jìn)行分步求解，且每一步總是做出當(dāng)前最好的選擇，即得到局部最優(yōu)解，再將各個(gè)局部最優(yōu)解整合成問(wèn)題的解。貪心法體現(xiàn)了一種快刀斬亂麻的思想，以當(dāng)前和局部利益最大化為導(dǎo)向的問(wèn)題求解策略。

利用貪心法求解問(wèn)題的過(guò)程：①分解：將原問(wèn)題分解為若干個(gè)相互獨(dú)立的階段；②解決：對(duì)每個(gè)階段求局部的最優(yōu)解，即進(jìn)行貪心選擇③合并：把各個(gè)階段的解合并為原問(wèn)題的一個(gè)可行解。44利用貪心法對(duì)問(wèn)題進(jìn)行求解的過(guò)程3.3算法的設(shè)計(jì)453.貪心法的應(yīng)用3.3算法的設(shè)計(jì)

[案例一]田忌賽馬戰(zhàn)國(guó)時(shí)期，齊威王與大將田忌賽馬，齊威王和田忌各有三匹好馬：上馬、中馬與下馬。比賽分三次進(jìn)行，每次賽馬以千金作賭。由于兩者的馬力相差無(wú)幾，而齊威王的馬分別比田忌相應(yīng)等級(jí)的馬要好，所以大家都認(rèn)為田忌必輸無(wú)疑。田忌采納了門(mén)客孫臏的意見(jiàn)，用下馬對(duì)齊威王的上馬，用上馬對(duì)齊威王的中馬，用中馬對(duì)齊威王的下馬，結(jié)果田忌以２比１勝齊威王而得千金。46將齊王的馬、田忌的馬均按上、中、下馬順序排列，齊王依次出馬，孫臏的貪心選擇策略：①若剩下的最強(qiáng)的馬都贏不了齊王剩下的最強(qiáng)的馬，選擇用最差的一匹馬對(duì)陣齊王最強(qiáng)的馬；②若剩下的最強(qiáng)的馬可以贏齊王剩下的最強(qiáng)的馬，選擇用這匹馬去贏齊王剩下的最強(qiáng)的馬；③若剩下的最強(qiáng)的馬和齊

王剩下的最強(qiáng)的馬打平的話(huà)，

可以選擇打平或者用最差的馬

輸?shù)舯荣悺?.3算法的設(shè)計(jì)47[案例二]電纜鋪設(shè)假設(shè)要在n個(gè)城市之間鋪設(shè)光纜,鋪設(shè)光纜費(fèi)用很高，且各個(gè)城市之間鋪設(shè)光纜的費(fèi)用不同，問(wèn)如何鋪設(shè),使得n個(gè)城市的任意兩個(gè)之間都可以通信，且使鋪設(shè)光纜的總費(fèi)用最低？3.3算法的設(shè)計(jì)可用圖論中的最小生成樹(shù)求解求解最小生成樹(shù)算法是貪心法

48

利用貪心法求解最小生成樹(shù)，其中一種貪心選擇策略是：貪心選擇權(quán)值最小的邊，若與之前加入的邊構(gòu)成回路，則放棄；否則，加入最小生成樹(shù)。3.3算法的設(shè)計(jì)電纜鋪設(shè)的最小生成樹(shù)49貪心算法是最接近于人類(lèi)日常思維的一種問(wèn)題求解方法，它已在人類(lèi)工作和生活的各個(gè)領(lǐng)域得到廣泛的應(yīng)用。例如：公司招聘新員工是從一批應(yīng)聘者中招收最能干的人。再如：學(xué)校招生是從眾多報(bào)考者中招收一批最好的學(xué)生。這種按照某種標(biāo)準(zhǔn)挑選最接近該標(biāo)準(zhǔn)的人或物的做法就是貪心算法。

3.3算法的設(shè)計(jì)50六、動(dòng)態(tài)規(guī)劃

1.問(wèn)題的提出3.3算法的設(shè)計(jì)動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問(wèn)題的一種方法。[案例一]GPS中的最優(yōu)路徑。全球定位系統(tǒng)GPS(GlobalPositioningSystem)可以為我們計(jì)算出滿(mǎn)足各種不同要求的、從出發(fā)地到目的地最優(yōu)路徑，可能是花費(fèi)時(shí)間最短，也可能是過(guò)路費(fèi)最少。GPS尋找最優(yōu)路徑的算法就是動(dòng)態(tài)規(guī)劃算法。51假設(shè)計(jì)算下圖中頂點(diǎn)0到頂點(diǎn)6的最短路徑。第0階段第1階段第2階段第3階段第4階段3.3算法的設(shè)計(jì)52定義cost[i]：從頂點(diǎn)0到頂點(diǎn)i的最短路徑。第0階段：cost[0]=0第1階段：cost[1]=cost[0]+4=4cost[2]=cost[0]+5=5第2階段：cost[3]=min{cost[0]+8,cost[1]+4,cost[2]+5}=8第3階段：cost[4]=min{cost[1]+6,cost[3]+8}=10

cost[5]=min{cost[2]+7,cost[3]+9}=12第4階段：cost[6]=min{cost[4]+5,cost[3]+9,cost[5]+4}=15根據(jù)計(jì)算，從頂點(diǎn)0到頂點(diǎn)6的最短路徑值為15。從頂點(diǎn)6向前回溯，最短路徑為0→1→4→6。3.3算法的設(shè)計(jì)53

2.動(dòng)態(tài)規(guī)劃算法3.3算法的設(shè)計(jì)動(dòng)態(tài)規(guī)劃是美國(guó)數(shù)學(xué)家R.Bellman等人于1951年在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)創(chuàng)立的一種解決問(wèn)題的新方法。在現(xiàn)實(shí)生活中，有一類(lèi)問(wèn)題可以將其活動(dòng)過(guò)程分解成若干個(gè)相互聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。這種將一個(gè)問(wèn)題看作是一個(gè)前后相互關(guān)聯(lián)且具有鏈狀結(jié)構(gòu)的多階段過(guò)程稱(chēng)為多階段決策過(guò)程將解決多階段決策的最優(yōu)化的過(guò)程稱(chēng)為動(dòng)態(tài)規(guī)劃算法。54

動(dòng)態(tài)規(guī)劃法主要適用于最優(yōu)化問(wèn)題的求解：這類(lèi)問(wèn)題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或最?。┲档慕?。若存在若干個(gè)最優(yōu)值的解的話(huà)，它只取其中的一個(gè)。3.3算法的設(shè)計(jì)

動(dòng)態(tài)規(guī)劃問(wèn)題求解的基本思想：將待求解的問(wèn)題分解為若干個(gè)互相聯(lián)系的子問(wèn)題，然后按自底向上的順序推導(dǎo)出原問(wèn)題的解。通過(guò)存儲(chǔ)子問(wèn)題的解，可以避免在求解過(guò)程中重復(fù)多次求解同一個(gè)子問(wèn)題，從而可以提高該算法的求解效率。動(dòng)態(tài)規(guī)劃算法實(shí)質(zhì)是分治思想和冗余解決方法的結(jié)合。

553.動(dòng)態(tài)規(guī)劃的應(yīng)用3.3算法的設(shè)計(jì)

[案例二]Fibonacci數(shù)列。

F[1]=1,F[2]=1,F[i]=F[i-1]+F[i-2],計(jì)算F[n](n≥3)動(dòng)態(tài)規(guī)劃求Fibonacci數(shù)列的偽代碼描述如下：輸入：正整數(shù)n輸出：Fibonacci數(shù)列的第n項(xiàng)Fib(n)1F[1]←